R. Ryan Williams

Publication Activity (10 Years)

Years Active: 2008-2024
Publications (10 Years): 62

Top Topics

Related Problems

Computational Complexity

Linear Threshold

Top Venues

Publications

R. Ryan Williams
Self-Improvement for Circuit-Analysis Problems. STOC (2024)
Marco Carmosino, Ronald Fagin, Neil Immerman, Phokion G. Kolaitis, Jonathan Lenchner, Rik Sengupta, R. Ryan Williams
Parallel Play Saves Quantifiers. CoRR (2024)
Ce Jin, R. Ryan Williams, Nathaniel Young
A VLSI Circuit Model Accounting for Wire Delay. ITCS (2024)
Gabriel Bathie, R. Ryan Williams
Towards Stronger Depth Lower Bounds. ITCS (2024)
Shuichi Hirahara, Rahul Ilango, R. Ryan Williams
Beating Brute Force for Compression Problems. STOC (2024)
Rahul Ilango, Jiatu Li, R. Ryan Williams
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic. STOC (2023)
Shyan Akmal, Virginia Vassilevska Williams, R. Ryan Williams, Zixuan Xu
Faster Detours in Undirected Graphs. CoRR (2023)
Nikhil Vyas, R. Ryan Williams
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms. Theory Comput. Syst. 67 (1) (2023)
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) (2023)
Lijie Chen, Ce Jin, R. Ryan Williams, Hongxun Wu
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions. SODA (2022)
Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams
Constructive Separations and Their Consequences. CoRR (2022)
Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams
Constructive Separations and Their Consequences. FOCS (2022)
Ronald Fagin, Jonathan Lenchner, Nikhil Vyas, R. Ryan Williams
On the Number of Quantifiers as a Complexity Measure. MFCS (2022)
Brynmor Chapman, R. Ryan Williams
Smaller ACC0 Circuits for Symmetric Functions. ITCS (2022)
Lijie Chen, Ce Jin, R. Ryan Williams, Hongxun Wu
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions. CoRR (2021)
Abhijit Mudigonda, R. Ryan Williams
Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers. ITCS (2021)
R. Ryan Williams
Complexity Lower Bounds from Algorithm Design. LICS (2021)
Brynmor Chapman, R. Ryan Williams
Smaller ACC0 Circuits for Symmetric Functions. CoRR (2021)
Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams
Constructive Separations and Their Consequences. FOCS (2021)
Brynmor Chapman, R. Ryan Williams
Black-Box Hypotheses and Lower Bounds. MFCS (2021)
Shyan Akmal, R. Ryan Williams
MAJORITY-3SAT (and Related Problems) in Polynomial Time. CoRR (2021)
Nikhil Vyas, R. Ryan Williams
On Super Strong ETH. J. Artif. Intell. Res. 70 (2021)
Timothy M. Chan, R. Ryan Williams
Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. ACM Trans. Algorithms 17 (1) (2021)
R. Ryan Williams
From Circuit Complexity to Faster All-Pairs Shortest Paths. SIAM Rev. 63 (3) (2021)
Alexander Golovnev, Alexander S. Kulikov, R. Ryan Williams
Circuit Depth Reductions. ITCS (2021)
Lijie Chen, Xin Lyu, R. Ryan Williams
Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization. FOCS (2020)
Josh Alman, Timothy M. Chan, R. Ryan Williams
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions. SODA (2020)
Lijie Chen, Ce Jin, R. Ryan Williams
Sharp threshold results for computational complexity. STOC (2020)
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)
Lijie Chen, Ce Jin, R. Ryan Williams
Sharp Threshold Results for Computational Complexity. Electron. Colloquium Comput. Complex. 27 (2020)
Nikhil Vyas, R. Ryan Williams
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms. STACS (2020)
Abhijit Mudigonda, R. Ryan Williams
Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers. CoRR (2020)
Lijie Chen, Ce Jin, R. Ryan Williams
Hardness Magnification for all Sparse NP Languages. FOCS (2019)
Dylan M. McKay, Cody D. Murray, R. Ryan Williams
Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. STOC (2019)
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. 26 (2019)
Lijie Chen, R. Ryan Williams
Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity. Computational Complexity Conference (2019)
Nikhil Vyas, R. Ryan Williams
On Super Strong ETH. SAT (2019)
Lijie Chen, Dylan M. McKay, Cody D. Murray, R. Ryan Williams
Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. Computational Complexity Conference (2019)
Virginia Vassilevska Williams, R. Ryan Williams
Subcubic Equivalences Between Path, Matrix, and Triangle Problems. J. ACM 65 (5) (2018)
R. Ryan Williams
Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials. CoRR (2018)
Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs. SODA (2018)
R. Ryan Williams
New Algorithms and Lower Bounds for Circuits With Linear Threshold Gates. Theory Comput. 14 (1) (2018)
R. Ryan Williams
Faster All-Pairs Shortest Paths via Circuit Complexity. SIAM J. Comput. 47 (5) (2018)
Cody Murray, R. Ryan Williams
Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP. STOC (2018)
R. Ryan Williams
Counting Solutions to Polynomial Systems via Reductions. SOSA (2018)
Cody Murray, R. Ryan Williams
Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP. Electron. Colloquium Comput. Complex. 24 (2017)
Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, R. Ryan Williams, Huacheng Yu
Beating Brute Force for Systems of Polynomial Equations over Finite Fields. SODA (2017)
Kasper Green Larsen, R. Ryan Williams
Faster Online Matrix-Vector Multiplication. SODA (2017)
Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs. CoRR (2017)
Cody D. Murray, R. Ryan Williams
Easiness Amplification and Uniform Circuit Lower Bounds. Computational Complexity Conference (2017)
R. Ryan Williams
Some ways of thinking algorithmically about impossibility. ACM SIGLOG News 4 (3) (2017)
Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, R. Ryan Williams
Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications. SODA (2017)
Daniel M. Kane, R. Ryan Williams
The Orthogonal Vectors Conjecture for Branching Programs and Formulas. CoRR (2017)
Andreas Björklund, Petteri Kaski, R. Ryan Williams
Generalized Kakeya Sets for Polynomial Evaluation and Faster Computation of Fermionants. IPEC (2017)
Amir Abboud, Aviad Rubinstein, R. Ryan Williams
Distributed PCP Theorems for Hardness of Approximation in P. FOCS (2017)
R. Ryan Williams
On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry. CoRR (2017)
Josh Alman, R. Ryan Williams
Probabilistic rank and matrix rigidity. STOC (2017)
Cody D. Murray, R. Ryan Williams
On the (Non) NP-Hardness of Computing Circuit Complexity. Theory Comput. 13 (1) (2017)
R. Ryan Williams
Natural Proofs versus Derandomization. SIAM J. Comput. 45 (2) (2016)
Josh Alman, Timothy M. Chan, R. Ryan Williams
Polynomial Representations of Threshold Functions and Algorithmic Applications. FOCS (2016)
Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, R. Ryan Williams
Deterministic Time-Space Trade-Offs for k-SUM. ICALP (2016)
Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, R. Ryan Williams
Deterministic Time-Space Tradeoffs for k-SUM. CoRR (2016)
R. Ryan Williams
Thinking Algorithmically About Impossibility (Invited Talk). CSL (2015)
R. Ryan Williams
Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. Comput. Complex. 17 (2) (2008)