R. Ryan Williams
Orcid: 0000-0003-2326-2233Affiliations:
- MIT, CSAIL, USA
- Stanford University, Computer Science Department (former)
- Carnegie Mellon University, Computer Science Department (former)
According to our database1,
R. Ryan Williams
authored at least 140 papers
between 2002 and 2024.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis Dataset OtherLinks
Online presence:
-
on zbmath.org
-
on scopus.com
-
on twitter.com
-
on orcid.org
-
on id.loc.gov
-
on dl.acm.org
On csauthors.net:
Bibliography
2024
2023
Algorithmica, August, 2023
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.
Theory Comput. Syst., February, 2023
Electron. Colloquium Comput. Complex., 2023
Electron. Colloquium Comput. Complex., 2023
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization.
Electron. Colloquium Comput. Complex., 2023
Electron. Colloquium Comput. Complex., 2023
Electron. Colloquium Comput. Complex., 2023
Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023
Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023
Proceedings of the 31st Annual European Symposium on Algorithms, 2023
2022
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022
Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022
2021
Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky.
ACM Trans. Algorithms, 2021
Electron. Colloquium Comput. Complex., 2021
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021
Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021
Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021
Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021
2020
Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma.
SIAM J. Comput., 2020
Electron. Colloquium Comput. Complex., 2020
Electron. Colloquium Comput. Complex., 2020
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020
Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020
2019
Proceedings of the Computing and Software Science - State of the Art and Perspectives, 2019
Completeness for First-order Properties on Sparse Structures with Algorithmic Applications.
ACM Trans. Algorithms, 2019
Electron. Colloquium Comput. Complex., 2019
Electron. Colloquium Comput. Complex., 2019
Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants.
Algorithmica, 2019
Weak lower bounds on resource-bounded compression imply strong separations of complexity classes.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019
Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019
Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019
Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity.
Proceedings of the 34th Computational Complexity Conference, 2019
2018
Theory Comput., 2018
Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018
On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018
Limits on Representing Boolean Functions by Linear Combinations of Simple Functions: Thresholds, ReLUs, and Low-Degree Polynomials.
Proceedings of the 33rd Computational Complexity Conference, 2018
2017
Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP.
Electron. Colloquium Comput. Complex., 2017
On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry.
CoRR, 2017
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017
Proceedings of the 32nd Computational Complexity Conference, 2017
2016
Encyclopedia of Algorithms, 2016
ACM Trans. Algorithms, 2016
Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation.
Electron. Colloquium Comput. Complex., 2016
Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016
2015
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits.
Electron. Colloquium Comput. Complex., 2015
Comput. Complex., 2015
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015
Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015
The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication.
Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015
Proceedings of the 24th EACSL Annual Conference on Computer Science Logic, 2015
2014
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014
The Polynomial Method in Circuit Complexity Applied to Algorithm Design (Invited Talk).
Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014
Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2014
Proceedings of the IEEE 29th Conference on Computational Complexity, 2014
2013
ACM Trans. Comput. Theory, 2013
SIAM J. Comput., 2013
Electron. Colloquium Comput. Complex., 2013
Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331).
Dagstuhl Reports, 2013
Comput. Complex., 2013
Proceedings of the Computer Science - Theory and Applications, 2013
Proceedings of the 28th Conference on Computational Complexity, 2013
2012
ACM Trans. Database Syst., 2012
SIGACT News Complexity Theory Column 76: an atypical survey of typical-case heuristic algorithms.
SIGACT News, 2012
Electron. Colloquium Comput. Complex., 2012
Electron. Colloquium Comput. Complex., 2012
2011
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2011, 2011
Proceedings of the Parameterized and Exact Computation - 6th International Symposium, 2011
Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011
Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011
2010
ACM Trans. Algorithms, 2010
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010
2009
Theory Comput., 2009
Inf. Process. Lett., 2009
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009
2008
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008
Electron. Colloquium Comput. Complex., 2008
Comput. Complex., 2008
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008
Proceedings of the Moderately Exponential Time Algorithms, 19.10. - 24.10.2008, 2008
2007
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007
2006
Comput. Complex., 2006
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006
Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2006
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006
2005
Theor. Comput. Sci., 2005
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005
2004
Electron. Colloquium Comput. Complex., 2004
Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004
2003
Proceedings of the Theory and Applications of Satisfiability Testing, 2003
2002
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002