Ryan Williams - RankMe

144 papers A* 32A 21B 2Misc 3Journal 77Unranked 7

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	A Theory for Probabilistic Polynomial-Time Reasoning. CoRR Lijie Chen, Jiatu Li, Igor C. Oliveira, Ryan Williams
2026	J	`jnl`	A Theory for Probabilistic Polynomial-Time Reasoning. Electron. Colloquium Comput. Complex. Lijie Chen, Jiatu Li, Igor C. Oliveira, Ryan Williams
2025	A	`conf`	New Algorithms for Pigeonhole Equal Subset Sum. ESA Ce Jin, Ryan Williams, Stan Zhang
2025	J	`jnl`	Simulating Time in Square-Root Space. Electron. Colloquium Comput. Complex. Ryan Williams
2025	A	`conf`	Sparsity Lower Bounds for Probabilistic Polynomials. ITCS Josh Alman, Arkadev Chattopadhyay, Ryan Williams
2025	J	`jnl`	When Connectivity Is Hard, Random Walks Are Easy With Non-Determinism. Electron. Colloquium Comput. Complex. Dean Doron, Edward Pyne, Roei Tell, Ryan Williams
2024	J	`jnl`	Constructive Separations and Their Consequences. TheoretiCS Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams
2024	J	`jnl`	On Oracles and Algorithmic Methods for Proving Lower Bounds. Electron. Colloquium Comput. Complex. Nikhil Vyas, Ryan Williams
2024	A*	`conf`	The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds. FOCS Ryan Williams
2024	J	`jnl`	The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds. Electron. Colloquium Comput. Complex. Ryan Williams
2023	J	`jnl`	A VLSI Circuit Model Accounting For Wire Delay. Electron. Colloquium Comput. Complex. Ce Jin, Ryan Williams, Nathaniel Young
2023	J	`jnl`	Beating Brute Force for Compression Problems. Electron. Colloquium Comput. Complex. Shuichi Hirahara, Rahul Ilango, Ryan Williams
2023	A	`conf`	Black-Box Constructive Proofs Are Unavoidable. ITCS Lijie Chen, Ryan Williams, Tianqi Yang
2023	A*	`conf`	Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization. FOCS Lijie Chen, Roei Tell, Ryan Williams
2023	J	`jnl`	Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization. Electron. Colloquium Comput. Complex. Lijie Chen, Roei Tell, Ryan Williams
2023	A	`conf`	Faster Detours in Undirected Graphs. ESA Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams, Zixuan Xu
2023	J	`jnl`	Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic. Electron. Colloquium Comput. Complex. Rahul Ilango, Jiatu Li, Ryan Williams
2023	A	`conf`	On Oracles and Algorithmic Methods for Proving Lower Bounds. ITCS Nikhil Vyas, Ryan Williams
2023	J	`jnl`	Self-Improvement for Circuit-Analysis Problems. Electron. Colloquium Comput. Complex. Ryan Williams
2023	J	`jnl`	The Power of Constructing Bad Inputs. Bull. EATCS Ryan Williams
2023	J	`jnl`	Towards Stronger Depth Lower Bounds. Electron. Colloquium Comput. Complex. Gabriel Bathie, Ryan Williams
2022	A	`conf`	Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity. ITCS Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams
2022	J	`jnl`	On the Number of Quantifiers as a Complexity Measure. CoRR Ronald Fagin, Jonathan Lenchner, Nikhil Vyas, Ryan Williams
2021	J	`jnl`	Constructive Separations and Their Consequences. Electron. Colloquium Comput. Complex. Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams
2021	A*	`conf`	Fast Low-Space Algorithms for Subset Sum. SODA Ce Jin, Nikhil Vyas, Ryan Williams
2021	J	`jnl`	Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity. Electron. Colloquium Comput. Complex. Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams
2021	A*	`conf`	MAJORITY-3SAT (and Related Problems) in Polynomial Time. FOCS Shyan Akmal, Ryan Williams
2020	J	`jnl`	Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization. Electron. Colloquium Comput. Complex. Lijie Chen, Xin Lyu, Ryan Williams
2020	J	`jnl`	Fast Low-Space Algorithms for Subset Sum. CoRR Ce Jin, Nikhil Vyas, Ryan Williams
2020	J	`jnl`	Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of $\#$SAT Algorithms. CoRR Nikhil Vyas, Ryan Williams
2020	J	`jnl`	Lower bounds for the depth of modular squaring. IACR Cryptol. ePrint Arch. Benjamin Wesolowski, Ryan Williams
2020	A*	`conf`	Results on a Super Strong Exponential Time Hypothesis. AAAI Nikhil Vyas, Ryan Williams
2019	A*	`conf`	An Equivalence Class for Orthogonal Vectors. SODA Lijie Chen, Ryan Williams
2019	J	`jnl`	Completeness for First-order Properties on Sparse Structures with Algorithmic Applications. ACM Trans. Algorithms Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, Ryan Williams
2019	A*	`conf`	Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors. ICALP Andreas Björklund, Ryan Williams
2019	J	`jnl`	Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants. Algorithmica Andreas Björklund, Petteri Kaski, Ryan Williams
2019	J	`jnl`	Hardness Magnification for all Sparse NP Languages. Electron. Colloquium Comput. Complex. Lijie Chen, Ce Jin, Ryan Williams
2019	A*	`conf`	Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction. ICALP Andreas Björklund, Petteri Kaski, Ryan Williams
2018	J	`jnl`	An Equivalence Class for Orthogonal Vectors. CoRR Lijie Chen, Ryan Williams
2018	A*	`conf`	On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity. SODA Ryan Williams
2016	J	`jnl`	Algebraic fingerprints for faster algorithms. Commun. ACM Ioannis Koutis, Ryan Williams
2016	A*	`conf`	Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. SODA Timothy M. Chan, Ryan Williams
2016	—	`ch.`	Exact Algorithms for Maximum Two-Satisfiability. Encyclopedia of Algorithms Ryan Williams
2016	J	`jnl`	Faster Online Matrix-Vector Multiplication. CoRR Kasper Green Larsen, Ryan Williams
2016	J	`jnl`	LIMITS and Applications of Group Algebras for Parameterized Problems. ACM Trans. Algorithms Ioannis Koutis, Ryan Williams
2016	J	`jnl`	Polynomial Representations of Threshold Functions and Algorithmic Applications. CoRR Josh Alman, Timothy M. Chan, Ryan Williams
2016	J	`jnl`	Probabilistic Rank and Matrix Rigidity. CoRR Josh Alman, Ryan Williams
2016	A*	`conf`	Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. STOC Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Ryan Williams
2016	J	`jnl`	Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation. CoRR Ryan Williams
2016	J	`jnl`	Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation. Electron. Colloquium Comput. Complex. Ryan Williams
2016	A*	`conf`	Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. STOC Daniel M. Kane, Ryan Williams
2015	J	`jnl`	Limits on Alternation Trading Proofs for Time-Space Lower Bounds. Comput. Complex. Samuel R. Buss, Ryan Williams
2015	A*	`conf`	Probabilistic Polynomials and Hamming Nearest Neighbors. FOCS Josh Alman, Ryan Williams
2015	J	`jnl`	Probabilistic Polynomials and Hamming Nearest Neighbors. CoRR Josh Alman, Ryan Williams
2015	J	`jnl`	Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made. CoRR Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Ryan Williams
2015	J	`jnl`	Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits. CoRR Daniel M. Kane, Ryan Williams
2015	J	`jnl`	Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits. Electron. Colloquium Comput. Complex. Daniel M. Kane, Ryan Williams
2015	A	`conf`	The Circuit-Input Game, Natural Proofs, and Testing Circuits With Data. ITCS Brynmor Chapman, Ryan Williams
2015	A*	`conf`	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication. PODS Dirk Van Gucht, Ryan Williams, David P. Woodruff, Qin Zhang
2015	J	`jnl`	Theory and Practice of SAT Solving (Dagstuhl Seminar 15171). Dagstuhl Reports Armin Biere, Vijay Ganesh, Martin Grohe, Jakob Nordström, Ryan Williams
2014	A	`conf`	Algorithms for Circuits and Circuits for Algorithms. CCC Ryan Williams
2014	A*	`conf`	Faster all-pairs shortest paths via circuit complexity. STOC Ryan Williams
2014	—	`conf`	Faster decision of first-order graph properties. CSL-LICS Ryan Williams
2014	A*	`conf`	Finding orthogonal vectors in discrete structures. SODA Ryan Williams, Huacheng Yu
2014	A	`conf`	Losing Weight by Gaining Edges. ESA Amir Abboud, Kevin Lewi, Ryan Williams
2014	A*	`conf`	New algorithms and lower bounds for circuits with linear threshold gates. STOC Ryan Williams
2014	J	`jnl`	New algorithms and lower bounds for circuits with linear threshold gates. CoRR Ryan Williams
2014	J	`jnl`	Nonuniform ACC Circuit Lower Bounds. J. ACM Ryan Williams
2014	J	`jnl`	On Uniformity and Circuit Lower Bounds. Comput. Complex. Rahul Santhanam, Ryan Williams
2014	J	`jnl`	On the (Non) NP-Hardness of Computing Circuit Complexity. Electron. Colloquium Comput. Complex. Cody Murray, Ryan Williams
2013	J	`jnl`	Alternation-Trading Proofs, Linear Programming, and Lower Bounds. ACM Trans. Comput. Theory Ryan Williams
2013	J	`jnl`	Amplifying circuit lower bounds against polynomial time, with applications. Comput. Complex. Richard J. Lipton, Ryan Williams
2013	J	`jnl`	Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331). Dagstuhl Reports Thore Husfeldt, Ramamohan Paturi, Gregory B. Sorkin, Ryan Williams
2013	J	`jnl`	Faster all-pairs shortest paths via circuit complexity. CoRR Ryan Williams
2013	J	`jnl`	Finding, Minimizing, and Counting Weighted Subgraphs. SIAM J. Comput. Virginia Vassilevska Williams, Ryan Williams
2013	J	`jnl`	Improving Exhaustive Search Implies Superpolynomial Lower Bounds. SIAM J. Comput. Ryan Williams
2013	A	`conf`	Massive online teaching to bounded learners. ITCS Brendan Juba, Ryan Williams
2013	A*	`conf`	Natural proofs versus derandomization. STOC Ryan Williams
2013	J	`jnl`	New Algorithms for QBF Satisfiability and Implications for Circuit Complexity. Electron. Colloquium Comput. Complex. Rahul Santhanam, Ryan Williams
2013	A	`conf`	On Medium-Uniformity and Circuit Lower Bounds. CCC Rahul Santhanam, Ryan Williams
2013	J	`jnl`	On the parameterized complexity of k-SUM. CoRR Amir Abboud, Kevin Lewi, Ryan Williams
2013	Misc	`conf`	Towards NEXP versus BPP? CSR Ryan Williams
2012	A	`conf`	Amplifying Circuit Lower Bounds against Polynomial Time with Applications. CCC Richard J. Lipton, Ryan Williams
2012	J	`jnl`	An Atypical Survey of Typical-Case Heuristic Algorithms CoRR Lane A. Hemaspaandra, Ryan Williams
2012	A	`conf`	Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. CCC Samuel R. Buss, Ryan Williams
2012	J	`jnl`	Massive Online Teaching to Bounded Learners. Electron. Colloquium Comput. Complex. Brendan Juba, Ryan Williams
2012	J	`jnl`	Maximizing Conjunctive Views in Deletion Propagation. ACM Trans. Database Syst. Benny Kimelfeld, Jan Vondrák, Ryan Williams
2012	J	`jnl`	Natural Proofs Versus Derandomization CoRR Ryan Williams
2012	J	`jnl`	Regularity Lemmas and Combinatorial Algorithms. Theory Comput. Nikhil Bansal, Ryan Williams
2012	J	`jnl`	SIGACT News Complexity Theory Column 76: an atypical survey of typical-case heuristic algorithms. SIGACT News Lane A. Hemaspaandra, Ryan Williams
2012	J	`jnl`	Uniform Circuits, Lower Bounds, and QBF Algorithms. Electron. Colloquium Comput. Complex. Rahul Santhanam, Ryan Williams
2011	J	`jnl`	A Casual Tour Around a Circuit Complexity Bound CoRR Ryan Williams
2011	J	`jnl`	An improved time-space lower bound for tautologies. J. Comb. Optim. Scott Diehl, Dieter van Melkebeek, Ryan Williams
2011	A	`conf`	Connecting SAT Algorithms and Complexity Lower Bounds. SAT Ryan Williams
2011	Misc	`conf`	Diagonalization Strikes Back: Some Recent Lower Bounds in Complexity Theory. COCOON Ryan Williams
2011	J	`jnl`	Guest column: a casual tour around a circuit complexity bound. SIGACT News Ryan Williams
2011	B	`conf`	Improved Parameterized Algorithms for above Average Constraint Satisfaction. IPEC Eun Jung Kim, Ryan Williams
2011	J	`jnl`	Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. Electron. Colloquium Comput. Complex. Sam Buss, Ryan Williams
2011	A*	`conf`	Maximizing conjunctive views in deletion propagation. PODS Benny Kimelfeld, Jan Vondrák, Ryan Williams
2011	A	`conf`	Non-uniform ACC Circuit Lower Bounds. CCC Ryan Williams
2011	J	`jnl`	Parallelizing Time with Polynomial Circuits. Theory Comput. Syst. Ryan Williams
2010	J	`jnl`	Alternation-Trading Proofs, Linear Programming, and Lower Bounds CoRR Ryan Williams
2010	A	`conf`	Alternation-Trading Proofs, Linear Programming, and Lower Bounds. STACS Ryan Williams
2010	A	`conf`	Communication Complexity with Synchronized Clocks. CCC Russell Impagliazzo, Ryan Williams
2010	J	`jnl`	Finding heaviest ACM Trans. Algorithms Virginia Vassilevska, Ryan Williams, Raphael Yuster
2010	J	`jnl`	Improved Parameterized Algorithms for Constraint Satisfaction CoRR Eun Jung Kim, Ryan Williams
2010	A*	`conf`	Improving exhaustive search implies superpolynomial lower bounds. STOC Ryan Williams
2010	A*	`conf`	On the Possibility of Faster SAT Algorithms. SODA Mihai Patrascu, Ryan Williams
2010	J	`jnl`	Resolving the Complexity of Some Data Privacy Problems CoRR Jeremiah Blocki, Ryan Williams
2010	—	`conf`	Resolving the Complexity of Some Data Privacy Problems. ICALP (2) Jeremiah Blocki, Ryan Williams
2010	A*	`conf`	Subcubic Equivalences between Path, Matrix and Triangle Problems. FOCS Virginia Vassilevska Williams, Ryan Williams
2009	J	`jnl`	All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time. Theory Comput. Virginia Vassilevska, Ryan Williams, Raphael Yuster
2009	Misc	`conf`	An Improved Time-Space Lower Bound for Tautologies. COCOON Scott Diehl, Dieter van Melkebeek, Ryan Williams
2009	J	`jnl`	Finding paths of length k in O Inf. Process. Lett. Ryan Williams
2009	A*	`conf`	Finding, minimizing, and counting weighted subgraphs. STOC Virginia Vassilevska, Ryan Williams
2009	A	`conf`	Fixed-Polynomial Size Circuit Bounds. CCC Lance Fortnow, Rahul Santhanam, Ryan Williams
2009	—	`conf`	Limits and Applications of Group Algebras for Parameterized Problems. ICALP (1) Ioannis Koutis, Ryan Williams
2009	A*	`conf`	Regularity Lemmas and Combinatorial Algorithms. FOCS Nikhil Bansal, Ryan Williams
2008	—	`conf`	08431 Open Problems - Moderately Exponential Time Algorithms. Moderately Exponential Time Algorithms Fedor V. Fomin, Kazuo Iwama, Dieter Kratsch, Petteri Kaski, Mikko Koivisto, Lukasz Kowalik, Yoshio Okamoto, Johan M. M. van Rooij, Ryan Williams
2008	—	`conf`	A New Combinatorial Approach for Sparse Graph Problems. ICALP (1) Guy E. Blelloch, Virginia Vassilevska, Ryan Williams
2008	J	`jnl`	Applying Practice to Theory CoRR Ryan Williams
2008	J	`jnl`	Applying practice to theory. SIGACT News Ryan Williams
2008	J	`jnl`	Finding paths of length k in O*(2^k) time CoRR Ryan Williams
2008	—	`ch.`	Maximum Two-Satisfiability. Encyclopedia of Algorithms Ryan Williams
2008	J	`jnl`	Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas. Electron. Colloquium Comput. Complex. Ryan Williams
2007	A*	`conf`	All-pairs bottleneck paths for general graphs in truly sub-cubic time. STOC Virginia Vassilevska, Ryan Williams, Raphael Yuster
2007	A*	`conf`	Matrix-vector multiplication in sub-quadratic time: (some preprocessing required). SODA Ryan Williams
2007	A	`conf`	Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. CCC Ryan Williams
2007	J	`jnl`	Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. Electron. Colloquium Comput. Complex. Ryan Williams
2006	A*	`conf`	Confronting hardness using a hybrid approach. SODA Virginia Vassilevska, Ryan Williams, Shan Leung Maverick Woo
2006	—	`conf`	Finding Small Unsatisfiable Cores to Prove Unsatisfiability of QBFs. AI&M Yannet Interian, Gabriel Corvera, Bart Selman, Ryan Williams
2006	A*	`conf`	Finding a maximum weight triangle in n STOC Virginia Vassilevska, Ryan Williams
2006	J	`jnl`	Finding heaviest H-subgraphs in real weighted graphs, with applications CoRR Virginia Vassilevska, Ryan Williams, Raphael Yuster
2006	—	`conf`	Finding the Smallest ICALP (1) Virginia Vassilevska, Ryan Williams, Raphael Yuster
2006	J	`jnl`	Inductive Time-Space Lower Bounds for Sat and Related Problems. Comput. Complex. Ryan Williams
2005	J	`jnl`	A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. Ryan Williams
2005	A	`conf`	Better Time-Space Lower Bounds for SAT and Related Problems. CCC Ryan Williams
2005	B	`conf`	Parallelizing time with polynomial circuits. SPAA Ryan Williams
2004	A*	`conf`	A New Algorithm for Optimal Constraint Satisfaction and Its Implications. ICALP Ryan Williams
2004	J	`jnl`	A new algorithm for optimal constraint satisfaction and its implications Electron. Colloquium Comput. Complex. Ryan Williams
2004	A*	`conf`	On the Complexity of Optimal K-Anonymity. PODS Adam Meyerson, Ryan Williams
2003	A*	`conf`	Backdoors To Typical Case Complexity. IJCAI Ryan Williams, Carla P. Gomes, Bart Selman
2003	A	`conf`	On Computing k-CNF Formula Properties. SAT Ryan Williams
2002	A*	`conf`	Algorithms for quantified Boolean formulas. SODA Ryan Williams