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
[j30]Andreas Björklund, Petteri Kaski, Ryan Williams:
Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants. Algorithmica 81(10): 4010-4028 (2019)- [j29]
Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, Ryan Williams:
Completeness for First-order Properties on Sparse Structures with Algorithmic Applications. ACM Trans. Algorithms 15(2): 23:1-23:35 (2019) - [c80]
Lijie Chen, R. Ryan Williams:
Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity. CCC 2019: 19:1-19:43 - [c79]
Lijie Chen, Dylan M. McKay, Cody D. Murray, R. Ryan Williams:
Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. CCC 2019: 30:1-30:21 - [c78]
Andreas Björklund, Ryan Williams:
Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors. ICALP 2019: 25:1-25:14 - [c77]
Andreas Björklund, Petteri Kaski, Ryan Williams:
Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction. ICALP 2019: 26:1-26:13 - [c76]
Daniel M. Kane, Richard Ryan Williams:
The Orthogonal Vectors Conjecture for Branching Programs and Formulas. ITCS 2019: 48:1-48:15 - [c75]
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 - [c74]
Nikhil Vyas, R. Ryan Williams:
On Super Strong ETH. SAT 2019: 406-423 - [c73]
Lijie Chen, Ryan Williams:
An Equivalence Class for Orthogonal Vectors. SODA 2019: 21-40 - [c72]
Dylan M. McKay, Cody D. Murray, R. Ryan Williams:
Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. STOC 2019: 1215-1225 - [p1]
R. Ryan Williams:
Some Estimated Likelihoods for Computational Complexity. Computing and Software Science 2019: 9-26 - [i40]
Lijie Chen, Dylan M. McKay, Cody Murray, R. Ryan Williams:
Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. Electronic Colloquium on Computational Complexity (ECCC) 26: 75 (2019) - 2018
- [j28]
Virginia Vassilevska Williams, R. Ryan Williams:
Subcubic Equivalences Between Path, Matrix, and Triangle Problems. J. ACM 65(5): 27:1-27:38 (2018) - [j27]
R. Ryan Williams:
Faster All-Pairs Shortest Paths via Circuit Complexity. SIAM J. Comput. 47(5): 1965-1985 (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]
R. Ryan Williams:
Counting Solutions to Polynomial Systems via Reductions. SOSA@SODA 2018: 6:1-6:15 - [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]
Lijie Chen, Ryan Williams:
An Equivalence Class for Orthogonal Vectors. CoRR abs/1811.12017 (2018) - 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]
Josh Alman, R. Ryan Williams:
Probabilistic rank and matrix rigidity. STOC 2017: 641-652 - [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]
R. Ryan Williams:
Natural Proofs versus Derandomization. SIAM J. Comput. 45(2): 497-529 (2016) - [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]
Josh Alman, Ryan Williams:
Probabilistic Rank and Matrix Rigidity. CoRR abs/1611.05558 (2016) - [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]
R. Ryan Williams:
Thinking Algorithmically About Impossibility (Invited Talk). CSL 2015: 14-23 - [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]
Ryan Williams:
Nonuniform ACC Circuit Lower Bounds. J. ACM 61(1): 2:1-2:32 (2014) - [c44]
Ryan Williams:
Algorithms for Circuits and Circuits for Algorithms. IEEE Conference on Computational Complexity 2014: 248-261 - [c43]
Ryan Williams:
Faster decision of first-order graph properties. CSL-LICS 2014: 80:1-80:6 - [c42]
Amir Abboud, Kevin Lewi, Ryan Williams:
Losing Weight by Gaining Edges. ESA 2014: 1-12 - [c41]
Richard Ryan Williams:
The Polynomial Method in Circuit Complexity Applied to Algorithm Design (Invited Talk). FSTTCS 2014: 47-60 - [c40]
Ryan Williams, Huacheng Yu:
Finding orthogonal vectors in discrete structures. SODA 2014: 1867-1877 - [c39]
Ryan Williams:
New algorithms and lower bounds for circuits with linear threshold gates. STOC 2014: 194-202 - [c38]
Ryan Williams:
Faster all-pairs shortest paths via circuit complexity. STOC 2014: 664-673 - [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]
Ryan Williams:
Towards NEXP versus BPP? CSR 2013: 174-182 - [c35]
Brendan Juba, Ryan Williams:
Massive online teaching to bounded learners. ITCS 2013: 1-10 - [c34]
Ryan Williams:
Natural proofs versus derandomization. STOC 2013: 21-30 - [i20]
Amir Abboud, Kevin Lewi, Ryan Williams:
On the parameterized complexity of k-SUM. CoRR abs/1311.3054 (2013) - [i19]
Ryan Williams:
Faster all-pairs shortest paths via circuit complexity. CoRR abs/1312.6680 (2013) - [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]
Ryan Williams:
Natural Proofs Versus Derandomization. CoRR abs/1212.1891 (2012) - [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]
Ryan Williams:
Connecting SAT Algorithms and Complexity Lower Bounds. SAT 2011: 1-2 - [i12]
Ryan Williams:
A Casual Tour Around a Circuit Complexity Bound. CoRR abs/1111.1261 (2011) - [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]
Mihai Patrascu, Ryan Williams:
On the Possibility of Faster SAT Algorithms. SODA 2010: 1065-1075 - [c22]
Ryan Williams:
Alternation-Trading Proofs, Linear Programming, and Lower Bounds. STACS 2010: 669-680 - [c21]
Ryan Williams:
Improving exhaustive search implies superpolynomial lower bounds. STOC 2010: 231-240 - [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]
Ryan Williams:
Finding paths of length k in O*(2k) time. Inf. Process. Lett. 109(6): 315-318 (2009) - [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]
Nikhil Bansal, Ryan Williams:
Regularity Lemmas and Combinatorial Algorithms. FOCS 2009: 745-754 - [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]
Ryan Williams:
Applying practice to theory. SIGACT News 39(4): 37-52 (2008) - [c15]
Guy E. Blelloch, Virginia Vassilevska, Ryan Williams:
A New Combinatorial Approach for Sparse Graph Problems. ICALP (1) 2008: 108-120 - [r1]
Ryan Williams:
Maximum Two-Satisfiability. Encyclopedia of Algorithms 2008 - [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]
Ryan Williams:
Finding paths of length k in O*(2^k) time. CoRR abs/0807.3026 (2008) - [i5]
Ryan Williams:
Applying Practice to Theory. CoRR abs/0811.1305 (2008) - [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]