R. Ryan Williams

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