R. Ryan Williams

According to our database1, R. Ryan Williams authored at least 112 papers between 2002 and 2020.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

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

2019
Some Estimated Likelihoods for Computational Complexity.
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

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems.
Electronic Colloquium on Computational Complexity (ECCC), 2019

Hardness Magnification for all Sparse NP Languages.
Electronic Colloquium on Computational Complexity (ECCC), 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

An Equivalence Class for Orthogonal Vectors.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

On Super Strong ETH.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2019, 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

The Orthogonal Vectors Conjecture for Branching Programs and Formulas.
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

Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors.
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
New Algorithms and Lower Bounds for Circuits With Linear Threshold Gates.
Theory of Computing, 2018

Faster All-Pairs Shortest Paths via Circuit Complexity.
SIAM J. Comput., 2018

Subcubic Equivalences Between Path, Matrix, and Triangle Problems.
J. ACM, 2018

Counting Solutions to Polynomial Systems via Reductions.
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

Tight Hardness for Shortest Cycles and Paths in Sparse Graphs.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Lower Bounds by Algorithm Design: A Progress Report (Invited Paper).
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
On the (Non) NP-Hardness of Computing Circuit Complexity.
Theory of Computing, 2017

Some ways of thinking algorithmically about impossibility.
SIGLOG News, 2017

Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP.
Electronic Colloquium on Computational Complexity (ECCC), 2017

On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry.
CoRR, 2017

Probabilistic rank and matrix rigidity.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Beating Brute Force for Systems of Polynomial Equations over Finite Fields.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Faster Online Matrix-Vector Multiplication.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Distributed PCP Theorems for Hardness of Approximation in P.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Easiness Amplification and Uniform Circuit Lower Bounds.
Proceedings of the 32nd Computational Complexity Conference, 2017

2016
Exact Algorithms for Maximum Two-Satisfiability.
Encyclopedia of Algorithms, 2016

Exact Algorithms and Strong Exponential Time Hypothesis.
Encyclopedia of Algorithms, 2016

LIMITS and Applications of Group Algebras for Parameterized Problems.
ACM Trans. Algorithms, 2016

Natural Proofs versus Derandomization.
SIAM J. Comput., 2016

Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Deterministic Time-Space Tradeoffs for k-SUM.
CoRR, 2016

Algebraic fingerprints for faster algorithms.
Commun. ACM, 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

Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Deterministic Time-Space Trade-Offs for k-SUM.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Polynomial Representations of Threshold Functions and Algorithmic Applications.
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.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Theory and Practice of SAT Solving (Dagstuhl Seminar 15171).
Dagstuhl Reports, 2015

Limits on Alternation Trading Proofs for Time-Space Lower Bounds.
Computational Complexity, 2015

Finding Four-Node Subgraphs in Triangle Time.
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

More Applications of the Polynomial Method to Algorithm Design.
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

The Circuit-Input Game, Natural Proofs, and Testing Circuits With Data.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Probabilistic Polynomials and Hamming Nearest Neighbors.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Thinking Algorithmically About Impossibility (Invited Talk).
Proceedings of the 24th EACSL Annual Conference on Computer Science Logic, 2015

2014
Nonuniform ACC Circuit Lower Bounds.
J. ACM, 2014

On Uniformity and Circuit Lower Bounds.
Computational Complexity, 2014

Finding orthogonal vectors in discrete structures.
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

Losing Weight by Gaining Edges.
Proceedings of the Algorithms - ESA 2014, 2014

Faster decision of first-order graph properties.
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

Algorithms for Circuits and Circuits for Algorithms.
Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013
Alternation-Trading Proofs, Linear Programming, and Lower Bounds.
TOCT, 2013

Finding, Minimizing, and Counting Weighted Subgraphs.
SIAM J. Comput., 2013

Improving Exhaustive Search Implies Superpolynomial Lower Bounds.
SIAM J. Comput., 2013

New Algorithms for QBF Satisfiability and Implications for Circuit Complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331).
Dagstuhl Reports, 2013

On the parameterized complexity of k-SUM.
CoRR, 2013

Amplifying circuit lower bounds against polynomial time, with applications.
Computational Complexity, 2013

Towards NEXP versus BPP?
Proceedings of the Computer Science - Theory and Applications, 2013

On Medium-Uniformity and Circuit Lower Bounds.
Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, 2013

2012
Maximizing Conjunctive Views in Deletion Propagation.
ACM Trans. Database Syst., 2012

Regularity Lemmas and Combinatorial Algorithms.
Theory of Computing, 2012

SIGACT News Complexity Theory Column 76: an atypical survey of typical-case heuristic algorithms.
SIGACT News, 2012

Uniform Circuits, Lower Bounds, and QBF Algorithms.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Massive Online Teaching to Bounded Learners.
Electronic Colloquium on Computational Complexity (ECCC), 2012

An Atypical Survey of Typical-Case Heuristic Algorithms
CoRR, 2012

2011
Guest column: a casual tour around a circuit complexity bound.
SIGACT News, 2011

Parallelizing Time with Polynomial Circuits.
Theory Comput. Syst., 2011

An improved time-space lower bound for tautologies.
J. Comb. Optim., 2011

A Casual Tour Around a Circuit Complexity Bound
CoRR, 2011

Connecting SAT Algorithms and Complexity Lower Bounds.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2011, 2011

Improved Parameterized Algorithms for above Average Constraint Satisfaction.
Proceedings of the Parameterized and Exact Computation - 6th International Symposium, 2011

Diagonalization Strikes Back: Some Recent Lower Bounds in Complexity Theory.
Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

Non-uniform ACC Circuit Lower Bounds.
Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010
Finding heaviest H-subgraphs in real weighted graphs, with applications.
ACM Trans. Algorithms, 2010

Improved Parameterized Algorithms for Constraint Satisfaction
CoRR, 2010

On the Possibility of Faster SAT Algorithms.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Resolving the Complexity of Some Data Privacy Problems.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Communication Complexity with Synchronized Clocks.
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, 2010

2009
All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time.
Theory of Computing, 2009

Finding paths of length k in O*(2k) time.
Inf. Process. Lett., 2009

Fixed-Polynomial Size Circuit Bounds.
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008
Maximum Two-Satisfiability.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Applying practice to theory.
SIGACT News, 2008

Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Finding paths of length k in O*(2^k) time
CoRR, 2008

Time-Space Tradeoffs for Counting NP Solutions Modulo Integers.
Computational Complexity, 2008

A New Combinatorial Approach for Sparse Graph Problems.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

08431 Open Problems - Moderately Exponential Time Algorithms.
Proceedings of the Moderately Exponential Time Algorithms, 19.10. - 24.10.2008, 2008

2007
All-pairs bottleneck paths for general graphs in truly sub-cubic time.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Matrix-vector multiplication in sub-quadratic time: (some preprocessing required).
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006
Finding heaviest H-subgraphs in real weighted graphs, with applications
CoRR, 2006

Inductive Time-Space Lower Bounds for Sat and Related Problems.
Computational Complexity, 2006

Finding a maximum weight triangle in n3-Delta time, with applications.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Confronting hardness using a hybrid approach.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Finding Small Unsatisfiable Cores to Prove Unsatisfiability of QBFs.
Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2006

Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005
A new algorithm for optimal 2-constraint satisfaction and its implications.
Theor. Comput. Sci., 2005

Better Time-Space Lower Bounds for SAT and Related Problems.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004
A new algorithm for optimal constraint satisfaction and its implications
Electronic Colloquium on Computational Complexity (ECCC), 2004

On the Complexity of Optimal K-Anonymity.
Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

2003
On Computing k-CNF Formula Properties.
Proceedings of the Theory and Applications of Satisfiability Testing, 2003

Backdoors To Typical Case Complexity.
Proceedings of the IJCAI-03, 2003

2002
Algorithms for quantified Boolean formulas.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002


  Loading...