Google
Google Scholar
MS Academic
CiteSeerX
CORE
Semantic ScholarR. Ryan Williams
Richard Ryan Williams – Ryan Williams 0001
Person information
- affiliation: MIT, CSAIL, USA
- affiliation: Stanford University, Computer Science Department
- affiliation: Carnegie Mellon University, Computer Science Department
Other persons with the same name
- Ryan Williams
- Ryan Williams 0002 — MIT Media Lab, Cambridge, MA, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2010 – today
- 2019
[c74]Daniel M. Kane, Richard Ryan Williams:
The Orthogonal Vectors Conjecture for Branching Programs and Formulas. ITCS 2019: 48:1-48:15- [c73]Dylan M. McKay, Richard Ryan Williams:
Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle. ITCS 2019: 56:1-56:20 - [c72]
- 2018
- [j27]Virginia Vassilevska Williams, R. Ryan Williams:
Subcubic Equivalences Between Path, Matrix, and Triangle Problems. J. ACM 65(5): 27:1-27:38 (2018) - [j26]R. Ryan Williams:
New Algorithms and Lower Bounds for Circuits With Linear Threshold Gates. Theory of Computing 14(1): 1-25 (2018) - [c71]Richard Ryan Williams:
Limits on Representing Boolean Functions by Linear Combinations of Simple Functions: Thresholds, ReLUs, and Low-Degree Polynomials. CCC 2018: 6:1-6:24 - [c70]Richard Ryan Williams:
Lower Bounds by Algorithm Design: A Progress Report (Invited Paper). ICALP 2018: 4:1-4:1 - [c69]
- [c68]Ryan Williams:
On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity. SODA 2018: 1207-1215 - [c67]Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams:
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs. SODA 2018: 1236-1252 - [c66]Cody Murray, R. Ryan Williams:
Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP. STOC 2018: 890-901 - [i39]R. Ryan Williams:
Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials. CoRR abs/1802.09121 (2018) - [i38]
- 2017
- [j25]R. Ryan Williams:
Some ways of thinking algorithmically about impossibility. SIGLOG News 4(3): 28-40 (2017) - [j24]Cody D. Murray, R. Ryan Williams:
On the (Non) NP-Hardness of Computing Circuit Complexity. Theory of Computing 13(1): 1-22 (2017) - [c65]Cody D. Murray, R. Ryan Williams:
Easiness Amplification and Uniform Circuit Lower Bounds. Computational Complexity Conference 2017: 8:1-8:21 - [c64]Amir Abboud, Aviad Rubinstein, R. Ryan Williams:
Distributed PCP Theorems for Hardness of Approximation in P. FOCS 2017: 25-36 - [c63]Andreas Björklund, Petteri Kaski, R. Ryan Williams:
Generalized Kakeya Sets for Polynomial Evaluation and Faster Computation of Fermionants. IPEC 2017: 6:1-6:13 - [c62]Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, R. Ryan Williams:
Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications. SODA 2017: 2162-2181 - [c61]Kasper Green Larsen, R. Ryan Williams:
Faster Online Matrix-Vector Multiplication. SODA 2017: 2182-2189 - [c60]Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, R. Ryan Williams, Huacheng Yu:
Beating Brute Force for Systems of Polynomial Equations over Finite Fields. SODA 2017: 2190-2202 - [c59]
- [i37]R. Ryan Williams:
On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry. CoRR abs/1709.05282 (2017) - [i36]Daniel M. Kane, R. Ryan Williams:
The Orthogonal Vectors Conjecture for Branching Programs and Formulas. CoRR abs/1709.05294 (2017) - [i35]Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams:
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs. CoRR abs/1712.08147 (2017) - [i34]Cody Murray, R. Ryan Williams:
Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP. Electronic Colloquium on Computational Complexity (ECCC) 24: 188 (2017) - 2016
- [j23]Ioannis Koutis, Ryan Williams:
Algebraic fingerprints for faster algorithms. Commun. ACM 59(1): 98-105 (2016) - [j22]
- [j21]Ioannis Koutis, Ryan Williams:
LIMITS and Applications of Group Algebras for Parameterized Problems. ACM Trans. Algorithms 12(3): 31:1-31:18 (2016) - [c58]Richard Ryan Williams:
Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation. Conference on Computational Complexity 2016: 2:1-2:17 - [c57]Josh Alman, Timothy M. Chan, R. Ryan Williams:
Polynomial Representations of Threshold Functions and Algorithmic Applications. FOCS 2016: 467-476 - [c56]Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, R. Ryan Williams:
Deterministic Time-Space Trade-Offs for k-SUM. ICALP 2016: 58:1-58:14 - [c55]Timothy M. Chan, Ryan Williams:
Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. SODA 2016: 1246-1255 - [c54]Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Ryan Williams:
Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. STOC 2016: 375-388 - [c53]Daniel M. Kane, Ryan Williams:
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. STOC 2016: 633-643 - [r3]Joshua R. Wang, Richard Ryan Williams:
Exact Algorithms and Strong Exponential Time Hypothesis. Encyclopedia of Algorithms 2016: 657-661 - [r2]Ryan Williams:
Exact Algorithms for Maximum Two-Satisfiability. Encyclopedia of Algorithms 2016: 683-688 - [i33]Ryan Williams:
Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation. CoRR abs/1601.04743 (2016) - [i32]Kasper Green Larsen, Ryan Williams:
Faster Online Matrix-Vector Multiplication. CoRR abs/1605.01695 (2016) - [i31]Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, R. Ryan Williams:
Deterministic Time-Space Tradeoffs for k-SUM. CoRR abs/1605.07285 (2016) - [i30]Josh Alman, Timothy M. Chan, Ryan Williams:
Polynomial Representations of Threshold Functions and Algorithmic Applications. CoRR abs/1608.04355 (2016) - [i29]
- [i28]Ryan Williams:
Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation. Electronic Colloquium on Computational Complexity (ECCC) 23: 2 (2016) - 2015
- [j20]Samuel R. Buss, Ryan Williams:
Limits on Alternation Trading Proofs for Time-Space Lower Bounds. Computational Complexity 24(3): 533-600 (2015) - [c52]Cody D. Murray, Richard Ryan Williams:
On the (Non) NP-Hardness of Computing Circuit Complexity. Conference on Computational Complexity 2015: 365-380 - [c51]
- [c50]Josh Alman, Ryan Williams:
Probabilistic Polynomials and Hamming Nearest Neighbors. FOCS 2015: 136-150 - [c49]Brynmor Chapman, Ryan Williams:
The Circuit-Input Game, Natural Proofs, and Testing Circuits With Data. ITCS 2015: 263-270 - [c48]Dirk Van Gucht, Ryan Williams, David P. Woodruff, Qin Zhang:
The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication. PODS 2015: 199-212 - [c47]Amir Abboud, Richard Ryan Williams, Huacheng Yu:
More Applications of the Polynomial Method to Algorithm Design. SODA 2015: 218-230 - [c46]Rahul Santhanam, Richard Ryan Williams:
Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity. SODA 2015: 231-241 - [c45]Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams, Huacheng Yu:
Finding Four-Node Subgraphs in Triangle Time. SODA 2015: 1671-1680 - [i27]Josh Alman, Ryan Williams:
Probabilistic Polynomials and Hamming Nearest Neighbors. CoRR abs/1507.05106 (2015) - [i26]Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Ryan Williams:
Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made. CoRR abs/1511.06022 (2015) - [i25]Daniel M. Kane, Ryan Williams:
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits. CoRR abs/1511.07860 (2015) - [i24]Armin Biere, Vijay Ganesh, Martin Grohe, Jakob Nordström, Ryan Williams:
Theory and Practice of SAT Solving (Dagstuhl Seminar 15171). Dagstuhl Reports 5(4): 98-122 (2015) - [i23]Daniel M. Kane, Ryan Williams:
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits. Electronic Colloquium on Computational Complexity (ECCC) 22: 188 (2015) - 2014
- [j19]Rahul Santhanam, Ryan Williams:
On Uniformity and Circuit Lower Bounds. Computational Complexity 23(2): 177-205 (2014) - [j18]
- [c44]Ryan Williams:
Algorithms for Circuits and Circuits for Algorithms. IEEE Conference on Computational Complexity 2014: 248-261 - [c43]
- [c42]
- [c41]Richard Ryan Williams:
The Polynomial Method in Circuit Complexity Applied to Algorithm Design (Invited Talk). FSTTCS 2014: 47-60 - [c40]
- [c39]Ryan Williams:
New algorithms and lower bounds for circuits with linear threshold gates. STOC 2014: 194-202 - [c38]
- [i22]Ryan Williams:
New algorithms and lower bounds for circuits with linear threshold gates. CoRR abs/1401.2444 (2014) - [i21]Cody Murray, Ryan Williams:
On the (Non) NP-Hardness of Computing Circuit Complexity. Electronic Colloquium on Computational Complexity (ECCC) 21: 164 (2014) - 2013
- [j17]Richard J. Lipton, Ryan Williams:
Amplifying circuit lower bounds against polynomial time, with applications. Computational Complexity 22(2): 311-343 (2013) - [j16]Virginia Vassilevska Williams, Ryan Williams:
Finding, Minimizing, and Counting Weighted Subgraphs. SIAM J. Comput. 42(3): 831-854 (2013) - [j15]Ryan Williams:
Improving Exhaustive Search Implies Superpolynomial Lower Bounds. SIAM J. Comput. 42(3): 1218-1244 (2013) - [j14]Ryan Williams:
Alternation-Trading Proofs, Linear Programming, and Lower Bounds. TOCT 5(2): 6:1-6:49 (2013) - [c37]Rahul Santhanam, Ryan Williams:
On Medium-Uniformity and Circuit Lower Bounds. IEEE Conference on Computational Complexity 2013: 15-23 - [c36]
- [c35]
- [c34]
- [i20]Amir Abboud, Kevin Lewi, Ryan Williams:
On the parameterized complexity of k-SUM. CoRR abs/1311.3054 (2013) - [i19]
- [i18]Thore Husfeldt, Ramamohan Paturi, Gregory B. Sorkin, Ryan Williams:
Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331). Dagstuhl Reports 3(8): 40-72 (2013) - [i17]Rahul Santhanam, Ryan Williams:
New Algorithms for QBF Satisfiability and Implications for Circuit Complexity. Electronic Colloquium on Computational Complexity (ECCC) 20: 108 (2013) - 2012
- [j13]Lane A. Hemaspaandra, Ryan Williams:
SIGACT News Complexity Theory Column 76: an atypical survey of typical-case heuristic algorithms. SIGACT News 43(4): 70-89 (2012) - [j12]Nikhil Bansal, Ryan Williams:
Regularity Lemmas and Combinatorial Algorithms. Theory of Computing 8(1): 69-94 (2012) - [j11]Benny Kimelfeld, Jan Vondrák, Ryan Williams:
Maximizing Conjunctive Views in Deletion Propagation. ACM Trans. Database Syst. 37(4): 24:1-24:37 (2012) - [c33]Richard J. Lipton, Ryan Williams:
Amplifying Circuit Lower Bounds against Polynomial Time with Applications. IEEE Conference on Computational Complexity 2012: 1-9 - [c32]Samuel R. Buss, Ryan Williams:
Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. IEEE Conference on Computational Complexity 2012: 181-191 - [i16]Lane A. Hemaspaandra, Ryan Williams:
An Atypical Survey of Typical-Case Heuristic Algorithms. CoRR abs/1210.8099 (2012) - [i15]
- [i14]Rahul Santhanam, Ryan Williams:
Uniform Circuits, Lower Bounds, and QBF Algorithms. Electronic Colloquium on Computational Complexity (ECCC) 19: 59 (2012) - [i13]Brendan Juba, Ryan Williams:
Massive Online Teaching to Bounded Learners. Electronic Colloquium on Computational Complexity (ECCC) 19: 107 (2012) - 2011
- [j10]Scott Diehl, Dieter van Melkebeek, Ryan Williams:
An improved time-space lower bound for tautologies. J. Comb. Optim. 22(3): 325-338 (2011) - [j9]Ryan Williams:
Parallelizing Time with Polynomial Circuits. Theory Comput. Syst. 48(1): 150-169 (2011) - [j8]Ryan Williams:
Guest column: a casual tour around a circuit complexity bound. SIGACT News 42(3): 54-76 (2011) - [c31]Ryan Williams:
Non-uniform ACC Circuit Lower Bounds. IEEE Conference on Computational Complexity 2011: 115-125 - [c30]Ryan Williams:
Diagonalization Strikes Back: Some Recent Lower Bounds in Complexity Theory. COCOON 2011: 237-239 - [c29]Eun Jung Kim, Ryan Williams:
Improved Parameterized Algorithms for above Average Constraint Satisfaction. IPEC 2011: 118-131 - [c28]Benny Kimelfeld, Jan Vondrák, Ryan Williams:
Maximizing conjunctive views in deletion propagation. PODS 2011: 187-198 - [c27]
- [i12]
- [i11]Sam Buss, Ryan Williams:
Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. Electronic Colloquium on Computational Complexity (ECCC) 18: 31 (2011) - 2010
- [j7]Virginia Vassilevska, Ryan Williams, Raphael Yuster:
Finding heaviest H-subgraphs in real weighted graphs, with applications. ACM Trans. Algorithms 6(3): 44:1-44:23 (2010) - [c26]Russell Impagliazzo, Ryan Williams:
Communication Complexity with Synchronized Clocks. IEEE Conference on Computational Complexity 2010: 259-269 - [c25]Virginia Vassilevska Williams, Ryan Williams:
Subcubic Equivalences between Path, Matrix and Triangle Problems. FOCS 2010: 645-654 - [c24]Jeremiah Blocki, Ryan Williams:
Resolving the Complexity of Some Data Privacy Problems. ICALP (2) 2010: 393-404 - [c23]
- [c22]Ryan Williams:
Alternation-Trading Proofs, Linear Programming, and Lower Bounds. STACS 2010: 669-680 - [c21]
- [i10]Ryan Williams:
Alternation-Trading Proofs, Linear Programming, and Lower Bounds. CoRR abs/1001.0746 (2010) - [i9]Jeremiah Blocki, Ryan Williams:
Resolving the Complexity of Some Data Privacy Problems. CoRR abs/1004.3811 (2010) - [i8]Eun Jung Kim, Ryan Williams:
Improved Parameterized Algorithms for Constraint Satisfaction. CoRR abs/1008.0213 (2010)
2000 – 2009
- 2009
- [j6]
- [j5]Virginia Vassilevska, Ryan Williams, Raphael Yuster:
All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time. Theory of Computing 5(1): 173-189 (2009) - [c20]Lance Fortnow, Rahul Santhanam, Ryan Williams:
Fixed-Polynomial Size Circuit Bounds. IEEE Conference on Computational Complexity 2009: 19-26 - [c19]Scott Diehl, Dieter van Melkebeek, Ryan Williams:
An Improved Time-Space Lower Bound for Tautologies. COCOON 2009: 429-438 - [c18]
- [c17]Ioannis Koutis, Ryan Williams:
Limits and Applications of Group Algebras for Parameterized Problems. ICALP (1) 2009: 653-664 - [c16]Virginia Vassilevska, Ryan Williams:
Finding, minimizing, and counting weighted subgraphs. STOC 2009: 455-464 - 2008
- [j4]R. Ryan Williams:
Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. Computational Complexity 17(2): 179-219 (2008) - [j3]
- [c15]Guy E. Blelloch, Virginia Vassilevska, Ryan Williams:
A New Combinatorial Approach for Sparse Graph Problems. ICALP (1) 2008: 108-120 - [r1]
- [i7]Fedor V. Fomin, Kazuo Iwama, Dieter Kratsch, Petteri Kaski, Mikko Koivisto, Lukasz Kowalik, Yoshio Okamoto, Johan M. M. van Rooij, Ryan Williams:
08431 Open Problems - Moderately Exponential Time Algorithms. Moderately Exponential Time Algorithms 2008 - [i6]
- [i5]
- [i4]Ryan Williams:
Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas. Electronic Colloquium on Computational Complexity (ECCC) 15(076) (2008) - 2007
- [c14]Ryan Williams:
Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. IEEE Conference on Computational Complexity 2007: 70-82 - [c13]Ryan Williams:
Matrix-vector multiplication in sub-quadratic time: (some preprocessing required). SODA 2007: 995-1001 - [c12]Virginia Vassilevska, Ryan Williams, Raphael Yuster:
All-pairs bottleneck paths for general graphs in truly sub-cubic time. STOC 2007: 585-589 - [i3]Ryan Williams:
Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. Electronic Colloquium on Computational Complexity (ECCC) 14(036) (2007) - 2006
- [j2]Ryan Williams:
Inductive Time-Space Lower Bounds for Sat and Related Problems. Computational Complexity 15(4): 433-470 (2006) - [c11]Virginia Vassilevska, Ryan Williams, Raphael Yuster:
Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems. ICALP (1) 2006: 262-273 - [c10]