default search action
R. Ryan Williams
Richard Ryan Williams – Ryan Williams 0001
Person information
- affiliation: MIT, CSAIL, USA
- affiliation (former): Stanford University, Computer Science Department
- affiliation (former): Carnegie Mellon University, Computer Science Department
Other persons with the same name
- Ryan Williams — disambiguation page
- 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
2020 – today
- 2024
- [j37]Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams:
Constructive Separations and Their Consequences. TheoretiCS 3 (2024) - [c106]Gabriel Bathie
, R. Ryan Williams
Towards Stronger Depth Lower Bounds. ITCS 2024: 10:1-10:24 - [c105]Ce Jin, R. Ryan Williams, Nathaniel Young:
A VLSI Circuit Model Accounting for Wire Delay. ITCS 2024: 66:1-66:22 - [c104]Shuichi Hirahara
Beating Brute Force for Compression Problems. STOC 2024: 659-670 - [c103]R. Ryan Williams
Self-Improvement for Circuit-Analysis Problems. STOC 2024: 1374-1385 - [i63]Marco Carmosino, Ronald Fagin, Neil Immerman, Phokion G. Kolaitis, Jonathan Lenchner, Rik Sengupta, R. Ryan Williams:
Parallel Play Saves Quantifiers. CoRR abs/2402.10293 (2024) - [i62]Nikhil Vyas, Ryan Williams:
On Oracles and Algorithmic Methods for Proving Lower Bounds. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [j36]Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, R. Ryan Williams:
Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity. Algorithmica 85(8): 2395-2426 (2023) - [j35]Nikhil Vyas
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms. Theory Comput. Syst. 67(1): 149-177 (2023) - [c102]Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams, Zixuan Xu:
Faster Detours in Undirected Graphs. ESA 2023: 7:1-7:17 - [c101]Lijie Chen, Roei Tell, Ryan Williams
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization. FOCS 2023: 1008-1047 - [c100]Lijie Chen, Ryan Williams, Tianqi Yang:
Black-Box Constructive Proofs Are Unavoidable. ITCS 2023: 35:1-35:24 - [c99]Nikhil Vyas, Ryan Williams
On Oracles and Algorithmic Methods for Proving Lower Bounds. ITCS 2023: 99:1-99:26 - [c98]Rahul Ilango, Jiatu Li, R. Ryan Williams
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic. STOC 2023: 1076-1089 - [i61]Shyan Akmal, Virginia Vassilevska Williams, R. Ryan Williams, Zixuan Xu:
Faster Detours in Undirected Graphs. CoRR abs/2307.01781 (2023) - [i60]Ce Jin, Ryan Williams, Nathaniel Young:
A VLSI Circuit Model Accounting For Wire Delay. Electron. Colloquium Comput. Complex. TR23 (2023) - [i59]Ryan Williams:
Self-Improvement for Circuit-Analysis Problems. Electron. Colloquium Comput. Complex. TR23 (2023) - [i58]Lijie Chen, Roei Tell, Ryan Williams:
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization. Electron. Colloquium Comput. Complex. TR23 (2023) - [i57]Gabriel Bathie, Ryan Williams:
Towards Stronger Depth Lower Bounds. Electron. Colloquium Comput. Complex. TR23 (2023) - [i56]Shuichi Hirahara, Rahul Ilango, Ryan Williams:
Beating Brute Force for Compression Problems. Electron. Colloquium Comput. Complex. TR23 (2023) - [i55]Rahul Ilango, Jiatu Li, Ryan Williams:
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [c97]Shyan Akmal
Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity. ITCS 2022: 3:1-3:25 - [c96]Brynmor Chapman, R. Ryan Williams:
Smaller ACC0 Circuits for Symmetric Functions. ITCS 2022: 38:1-38:19 - [c95]Ronald Fagin
On the Number of Quantifiers as a Complexity Measure. MFCS 2022: 48:1-48:14 - [c94]Lijie Chen, Ce Jin, R. Ryan Williams, Hongxun Wu:
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions. SODA 2022: 1661-1678 - [i54]Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams:
Constructive Separations and Their Consequences. CoRR abs/2203.14379 (2022) - [i53]Ronald Fagin, Jonathan Lenchner, Nikhil Vyas, Ryan Williams:
On the Number of Quantifiers as a Complexity Measure. CoRR abs/2207.00104 (2022) - 2021
- [j34]Nikhil Vyas, R. Ryan Williams
On Super Strong ETH. J. Artif. Intell. Res. 70: 473-495 (2021) - [j33]R. Ryan Williams
From Circuit Complexity to Faster All-Pairs Shortest Paths. SIAM Rev. 63(3): 559-582 (2021) - [j32]Timothy M. Chan
Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. ACM Trans. Algorithms 17(1): 2:1-2:14 (2021) - [c93]Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams
Constructive Separations and Their Consequences. FOCS 2021: 646-657 - [c92]Shyan Akmal
MAJORITY-3SAT (and Related Problems) in Polynomial Time. FOCS 2021: 1033-1043 - [c91]Alexander Golovnev, Alexander S. Kulikov, R. Ryan Williams
Circuit Depth Reductions. ITCS 2021: 24:1-24:20 - [c90]Abhijit Mudigonda
Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers. ITCS 2021: 50:1-50:20 - [c89]R. Ryan Williams:
Complexity Lower Bounds from Algorithm Design. LICS 2021: 1-3 - [c88]Brynmor Chapman, R. Ryan Williams
Black-Box Hypotheses and Lower Bounds. MFCS 2021: 29:1-29:22 - [c87]Ce Jin, Nikhil Vyas, Ryan Williams:
Fast Low-Space Algorithms for Subset Sum. SODA 2021: 1757-1776 - [i52]Shyan Akmal, R. Ryan Williams:
MAJORITY-3SAT (and Related Problems) in Polynomial Time. CoRR abs/2107.02748 (2021) - [i51]Brynmor Chapman, R. Ryan Williams:
Smaller ACC0 Circuits for Symmetric Functions. CoRR abs/2107.04706 (2021) - [i50]Lijie Chen, Ce Jin, R. Ryan Williams, Hongxun Wu:
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions. CoRR abs/2111.01759 (2021) - [i49]Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams:
Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity. Electron. Colloquium Comput. Complex. TR21 (2021) - [i48]Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams:
Constructive Separations and Their Consequences. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [j31]Cody D. Murray, R. Ryan Williams
Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma. SIAM J. Comput. 49(5) (2020) - [c86]Nikhil Vyas, Ryan Williams:
Results on a Super Strong Exponential Time Hypothesis. AAAI 2020: 13700-13703 - [c85]Lijie Chen, Xin Lyu, R. Ryan Williams
Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization. FOCS 2020: 1-12 - [c84]Josh Alman, Timothy M. Chan, R. Ryan Williams:
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions. SODA 2020: 637-649 - [c83]Nikhil Vyas
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms. STACS 2020: 59:1-59:17 - [c82]Lijie Chen, Ce Jin, R. Ryan Williams:
Sharp threshold results for computational complexity. STOC 2020: 1335-1348 - [i47]Nikhil Vyas, Ryan Williams:
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of $\#$SAT Algorithms. CoRR abs/2001.07788 (2020) - [i46]Ce Jin, Nikhil Vyas, Ryan Williams:
Fast Low-Space Algorithms for Subset Sum. CoRR abs/2011.03819 (2020) - [i45]Abhijit Mudigonda, R. Ryan Williams:
Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers. CoRR abs/2012.00330 (2020) - [i44]Lijie Chen, Ce Jin, R. Ryan Williams:
Sharp Threshold Results for Computational Complexity. Electron. Colloquium Comput. Complex. TR20 (2020) - [i43]Lijie Chen, Xin Lyu, Ryan Williams:
Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization. Electron. Colloquium Comput. Complex. TR20 (2020) - [i42]Benjamin Wesolowski, Ryan Williams:
Lower bounds for the depth of modular squaring. IACR Cryptol. ePrint Arch. 2020: 1461 (2020)
2010 – 2019
- 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
Completeness for First-order Properties on Sparse Structures with Algorithmic Applications. ACM Trans. Algorithms 15(2): 23:1-23:35 (2019) - [c81]Lijie Chen, R. Ryan Williams
Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity. CCC 2019: 19:1-19:43 - [c80]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 - [c79]Lijie Chen, Ce Jin, R. Ryan Williams
Hardness Magnification for all Sparse NP Languages. FOCS 2019: 1240-1255 - [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 - [i41]Lijie Chen, Ce Jin, Ryan Williams:
Hardness Magnification for all Sparse NP Languages. Electron. Colloquium Comput. Complex. TR19 (2019) - [i40]Lijie Chen, Dylan M. McKay, Cody Murray, R. Ryan Williams:
Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. Electron. Colloquium Comput. Complex. TR19 (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 Comput. 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 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
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. ACM SIGLOG News 4(3): 28-40 (2017) - [j24]Cody D. Murray, R. Ryan Williams
On the (Non) NP-Hardness of Computing Circuit Complexity. Theory Comput. 13(1): 1-22 (2017) - [c65]Cody D. Murray, R. Ryan Williams
Easiness Amplification and Uniform Circuit Lower Bounds. CCC 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
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
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. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j23]Ioannis Koutis
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. CCC 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
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. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j20]Samuel R. Buss, Ryan Williams
Limits on Alternation Trading Proofs for Time-Space Lower Bounds. Comput. Complex. 24(3): 533-600 (2015) - [c52]Cody D. Murray, Richard Ryan Williams
On the (Non) NP-Hardness of Computing Circuit Complexity. CCC 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
The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication. PODS 2015: 199-212 - [c47]Amir Abboud, Richard Ryan Williams
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
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. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j19]Rahul Santhanam, Ryan Williams
On Uniformity and Circuit Lower Bounds. Comput. Complex. 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. CCC 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
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. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j17]Richard J. Lipton, Ryan Williams
Amplifying circuit lower bounds against polynomial time, with applications. Comput. Complex. 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. ACM Trans. Comput. Theory 5(2): 6:1-6:49 (2013) - [c37]Rahul Santhanam, Ryan Williams
On Medium-Uniformity and Circuit Lower Bounds. CCC 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. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j13]Lane A. Hemaspaandra
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 Comput. 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. CCC 2012: 1-9 - [c32]Samuel R. Buss, Ryan Williams
Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. CCC 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]Brendan Juba, Ryan Williams:
Massive Online Teaching to Bounded Learners. Electron. Colloquium Comput. Complex. TR12 (2012) - [i13]Rahul Santhanam, Ryan Williams:
Uniform Circuits, Lower Bounds, and QBF Algorithms. Electron. Colloquium Comput. Complex. TR12 (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. CCC 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. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j7]Virginia Vassilevska, Ryan Williams
Finding heaviest H-subgraphs in real weighted graphs, with applications. ACM Trans. Algorithms 6(3): 44:1-44:23 (2010) - [c26]Russell Impagliazzo
Communication Complexity with Synchronized Clocks. CCC 2010: 259-269 - [c25]Virginia Vassilevska Williams, Ryan Williams
Subcubic Equivalences between Path, Matrix and Triangle Problems. FOCS 2010: 645-654 - [c24]Jeremiah Blocki
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 Comput. 5(1): 173-189 (2009) - [c20]Lance Fortnow, Rahul Santhanam, Ryan Williams
Fixed-Polynomial Size Circuit Bounds. CCC 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. Comput. Complex. 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. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [c14]Ryan Williams
Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. CCC 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
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. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j2]Ryan Williams
Inductive Time-Space Lower Bounds for Sat and Related Problems. Comput. Complex. 15(4): 433-470 (2006) - [c11]Virginia Vassilevska, Ryan Williams
Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems. ICALP (1) 2006: 262-273 - [c10]Yannet Interian, Gabriel Corvera, Bart Selman, Ryan Williams:
Finding Small Unsatisfiable Cores to Prove Unsatisfiability of QBFs. AI&M 2006 - [c9]Virginia Vassilevska, Ryan Williams, Shan Leung Maverick Woo:
Confronting hardness using a hybrid approach. SODA 2006: 1-10 - [c8]Virginia Vassilevska, Ryan Williams
Finding a maximum weight triangle in n3-Delta time, with applications. STOC 2006: 225-231 - [i2]Virginia Vassilevska, Ryan Williams, Raphael Yuster:
Finding heaviest H-subgraphs in real weighted graphs, with applications. CoRR abs/cs/0609009 (2006) - 2005
- [j1]Ryan Williams
A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2-3): 357-365 (2005) - [c7]Ryan Williams
Better Time-Space Lower Bounds for SAT and Related Problems. CCC 2005: 40-49 - [c6]Ryan Williams
Parallelizing time with polynomial circuits. SPAA 2005: 171-175 - 2004
- [c5]Ryan Williams
A New Algorithm for Optimal Constraint Satisfaction and Its Implications. ICALP 2004: 1227-1237 - [c4]Adam Meyerson, Ryan Williams
On the Complexity of Optimal K-Anonymity. PODS 2004: 223-228 - [i1]Ryan Williams:
A new algorithm for optimal constraint satisfaction and its implications. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [c3]Ryan Williams, Carla P. Gomes, Bart Selman:
Backdoors To Typical Case Complexity. IJCAI 2003: 1173-1178 - [c2]Ryan Williams:
On Computing k-CNF Formula Properties. SAT 2003: 330-340 - 2002
- [c1]Ryan Williams:
Algorithms for quantified Boolean formulas. SODA 2002: 299-307
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-10 21:48 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: