Ryan Williams

ORCID

Publication Activity (10 Years)

Years Active: 2002-2024
Publications (10 Years): 40

Top Venues

Electron. Colloquium Comput. Complex.

CoRR

SODA

STOC

Publications

Nikhil Vyas, Ryan Williams
On Oracles and Algorithmic Methods for Proving Lower Bounds. Electron. Colloquium Comput. Complex. (2024)
Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams
Constructive Separations and Their Consequences. TheoretiCS 3 (2024)
Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams, Zixuan Xu
Faster Detours in Undirected Graphs. ESA (2023)
Ce Jin, Ryan Williams, Nathaniel Young
A VLSI Circuit Model Accounting For Wire Delay. Electron. Colloquium Comput. Complex. (2023)
Nikhil Vyas, Ryan Williams
On Oracles and Algorithmic Methods for Proving Lower Bounds. ITCS (2023)
Lijie Chen, Roei Tell, Ryan Williams
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization. Electron. Colloquium Comput. Complex. (2023)
Rahul Ilango, Jiatu Li, Ryan Williams
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic. Electron. Colloquium Comput. Complex. (2023)
Shuichi Hirahara, Rahul Ilango, Ryan Williams
Beating Brute Force for Compression Problems. Electron. Colloquium Comput. Complex. (2023)
Ryan Williams
Self-Improvement for Circuit-Analysis Problems. Electron. Colloquium Comput. Complex. (2023)
Gabriel Bathie, Ryan Williams
Towards Stronger Depth Lower Bounds. Electron. Colloquium Comput. Complex. (2023)
Lijie Chen, Roei Tell, Ryan Williams
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization. FOCS (2023)
Lijie Chen, Ryan Williams, Tianqi Yang
Black-Box Constructive Proofs Are Unavoidable. ITCS (2023)
Ronald Fagin, Jonathan Lenchner, Nikhil Vyas, Ryan Williams
On the Number of Quantifiers as a Complexity Measure. CoRR (2022)
Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams
Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity. ITCS (2022)
Ce Jin, Nikhil Vyas, Ryan Williams
Fast Low-Space Algorithms for Subset Sum. SODA (2021)
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. 28 (2021)
Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams
Constructive Separations and Their Consequences. Electron. Colloquium Comput. Complex. 28 (2021)
Nikhil Vyas, Ryan Williams
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of $\#$SAT Algorithms. CoRR (2020)
Lijie Chen, Xin Lyu, Ryan Williams
Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization. Electron. Colloquium Comput. Complex. 27 (2020)
Ce Jin, Nikhil Vyas, Ryan Williams
Fast Low-Space Algorithms for Subset Sum. CoRR (2020)
Benjamin Wesolowski, Ryan Williams
Lower bounds for the depth of modular squaring. IACR Cryptol. ePrint Arch. 2020 (2020)
Nikhil Vyas, Ryan Williams
Results on a Super Strong Exponential Time Hypothesis. AAAI (2020)
Lijie Chen, Ryan Williams
An Equivalence Class for Orthogonal Vectors. SODA (2019)
Andreas Björklund, Petteri Kaski, Ryan Williams
Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants. Algorithmica 81 (10) (2019)
Lijie Chen, Ce Jin, Ryan Williams
Hardness Magnification for all Sparse NP Languages. Electron. Colloquium Comput. Complex. 26 (2019)
Andreas Björklund, Ryan Williams
Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors. ICALP (2019)
Andreas Björklund, Petteri Kaski, Ryan Williams
Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction. ICALP (2019)
Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, Ryan Williams
Completeness for First-order Properties on Sparse Structures with Algorithmic Applications. ACM Trans. Algorithms 15 (2) (2019)
Ryan Williams
On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity. SODA (2018)
Lijie Chen, Ryan Williams
An Equivalence Class for Orthogonal Vectors. CoRR (2018)
Daniel M. Kane, Ryan Williams
Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. STOC (2016)
Kasper Green Larsen, Ryan Williams
Faster Online Matrix-Vector Multiplication. CoRR (2016)
Ioannis Koutis, Ryan Williams
Algebraic fingerprints for faster algorithms. Commun. ACM 59 (1) (2016)
Josh Alman, Ryan Williams
Probabilistic Rank and Matrix Rigidity. CoRR (2016)
Ryan Williams
Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation. Electron. Colloquium Comput. Complex. 23 (2016)
Josh Alman, Timothy M. Chan, Ryan Williams
Polynomial Representations of Threshold Functions and Algorithmic Applications. CoRR (2016)
Ioannis Koutis, Ryan Williams
LIMITS and Applications of Group Algebras for Parameterized Problems. ACM Trans. Algorithms 12 (3) (2016)
Ryan Williams
Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation. CoRR (2016)
Timothy M. Chan, Ryan Williams
Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. SODA (2016)
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)
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 (2015)
Josh Alman, Ryan Williams
Probabilistic Polynomials and Hamming Nearest Neighbors. CoRR (2015)
Daniel M. Kane, Ryan Williams
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits. CoRR (2015)
Samuel R. Buss, Ryan Williams
Limits on Alternation Trading Proofs for Time-Space Lower Bounds. Comput. Complex. 24 (3) (2015)
Brynmor Chapman, Ryan Williams
The Circuit-Input Game, Natural Proofs, and Testing Circuits With Data. ITCS (2015)
Armin Biere, Vijay Ganesh, Martin Grohe, Jakob Nordström, Ryan Williams
Theory and Practice of SAT Solving (Dagstuhl Seminar 15171). Dagstuhl Reports 5 (4) (2015)
Dirk Van Gucht, Ryan Williams, David P. Woodruff, Qin Zhang
The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication. PODS (2015)
Josh Alman, Ryan Williams
Probabilistic Polynomials and Hamming Nearest Neighbors. FOCS (2015)
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. 22 (2015)
Ryan Williams, Huacheng Yu
Finding orthogonal vectors in discrete structures. SODA (2014)
Ryan Williams
Faster decision of first-order graph properties. CSL-LICS (2014)
Cody Murray, Ryan Williams
On the (Non) NP-Hardness of Computing Circuit Complexity. Electron. Colloquium Comput. Complex. 21 (2014)
Rahul Santhanam, Ryan Williams
On Uniformity and Circuit Lower Bounds. Comput. Complex. 23 (2) (2014)
Ryan Williams
Faster all-pairs shortest paths via circuit complexity. STOC (2014)
Ryan Williams
Nonuniform ACC Circuit Lower Bounds. J. ACM 61 (1) (2014)
Ryan Williams
Algorithms for Circuits and Circuits for Algorithms. Computational Complexity Conference (2014)
Amir Abboud, Kevin Lewi, Ryan Williams
Losing Weight by Gaining Edges. ESA (2014)
Ryan Williams
New algorithms and lower bounds for circuits with linear threshold gates. STOC (2014)
Ryan Williams
New algorithms and lower bounds for circuits with linear threshold gates. CoRR (2014)
Thore Husfeldt, Ramamohan Paturi, Gregory B. Sorkin, Ryan Williams
Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331). Dagstuhl Reports 3 (8) (2013)
Rahul Santhanam, Ryan Williams
On Medium-Uniformity and Circuit Lower Bounds. Computational Complexity Conference (2013)
Richard J. Lipton, Ryan Williams
Amplifying circuit lower bounds against polynomial time, with applications. Comput. Complex. 22 (2) (2013)
Brendan Juba, Ryan Williams
Massive online teaching to bounded learners. ITCS (2013)
Virginia Vassilevska Williams, Ryan Williams
Finding, Minimizing, and Counting Weighted Subgraphs. SIAM J. Comput. 42 (3) (2013)
Ryan Williams
Natural proofs versus derandomization. STOC (2013)
Ryan Williams
Alternation-Trading Proofs, Linear Programming, and Lower Bounds. ACM Trans. Comput. Theory 5 (2) (2013)
Amir Abboud, Kevin Lewi, Ryan Williams
On the parameterized complexity of k-SUM. CoRR (2013)
Ryan Williams
Improving Exhaustive Search Implies Superpolynomial Lower Bounds. SIAM J. Comput. 42 (3) (2013)
Ryan Williams
Towards NEXP versus BPP? CSR (2013)
Rahul Santhanam, Ryan Williams
New Algorithms for QBF Satisfiability and Implications for Circuit Complexity. Electron. Colloquium Comput. Complex. 20 (2013)
Ryan Williams
Faster all-pairs shortest paths via circuit complexity. CoRR (2013)
Rahul Santhanam, Ryan Williams
Uniform Circuits, Lower Bounds, and QBF Algorithms. Electron. Colloquium Comput. Complex. 19 (2012)
Lane A. Hemaspaandra, Ryan Williams
SIGACT News Complexity Theory Column 76: an atypical survey of typical-case heuristic algorithms. SIGACT News 43 (4) (2012)
Richard J. Lipton, Ryan Williams
Amplifying Circuit Lower Bounds against Polynomial Time with Applications. Computational Complexity Conference (2012)
Benny Kimelfeld, Jan Vondrák, Ryan Williams
Maximizing Conjunctive Views in Deletion Propagation. ACM Trans. Database Syst. 37 (4) (2012)
Brendan Juba, Ryan Williams
Massive Online Teaching to Bounded Learners. Electron. Colloquium Comput. Complex. 19 (2012)
Samuel R. Buss, Ryan Williams
Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. Computational Complexity Conference (2012)
Nikhil Bansal, Ryan Williams
Regularity Lemmas and Combinatorial Algorithms. Theory Comput. 8 (1) (2012)
Lane A. Hemaspaandra, Ryan Williams
An Atypical Survey of Typical-Case Heuristic Algorithms CoRR (2012)
Ryan Williams
Natural Proofs Versus Derandomization CoRR (2012)
Benny Kimelfeld, Jan Vondrák, Ryan Williams
Maximizing conjunctive views in deletion propagation. PODS (2011)
Ryan Williams
Non-uniform ACC Circuit Lower Bounds. Computational Complexity Conference (2011)
Ryan Williams
A Casual Tour Around a Circuit Complexity Bound CoRR (2011)
Eun Jung Kim, Ryan Williams
Improved Parameterized Algorithms for above Average Constraint Satisfaction. IPEC (2011)
Ryan Williams
Guest column: a casual tour around a circuit complexity bound. SIGACT News 42 (3) (2011)
Ryan Williams
Connecting SAT Algorithms and Complexity Lower Bounds. SAT (2011)
Sam Buss, Ryan Williams
Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. Electron. Colloquium Comput. Complex. 18 (2011)
Ryan Williams
Parallelizing Time with Polynomial Circuits. Theory Comput. Syst. 48 (1) (2011)
Scott Diehl, Dieter van Melkebeek, Ryan Williams
An improved time-space lower bound for tautologies. J. Comb. Optim. 22 (3) (2011)
Ryan Williams
Diagonalization Strikes Back: Some Recent Lower Bounds in Complexity Theory. COCOON (2011)
Virginia Vassilevska, Ryan Williams, Raphael Yuster
-subgraphs in real weighted graphs, with applications. ACM Trans. Algorithms 6 (3) (2010)
Eun Jung Kim, Ryan Williams
Improved Parameterized Algorithms for Constraint Satisfaction CoRR (2010)
Mihai Patrascu, Ryan Williams
On the Possibility of Faster SAT Algorithms. SODA (2010)
Virginia Vassilevska Williams, Ryan Williams
Subcubic Equivalences between Path, Matrix and Triangle Problems. FOCS (2010)
Ryan Williams
Alternation-Trading Proofs, Linear Programming, and Lower Bounds CoRR (2010)
Ryan Williams
Alternation-Trading Proofs, Linear Programming, and Lower Bounds. STACS (2010)
Russell Impagliazzo, Ryan Williams
Communication Complexity with Synchronized Clocks. Computational Complexity Conference (2010)
Jeremiah Blocki, Ryan Williams
Resolving the Complexity of Some Data Privacy Problems CoRR (2010)
Jeremiah Blocki, Ryan Williams
Resolving the Complexity of Some Data Privacy Problems. ICALP (2) (2010)
Ryan Williams
Improving exhaustive search implies superpolynomial lower bounds. STOC (2010)

Ryan Williams.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Ryan Williams