R. Ryan Williams
According to our database^{1},
R. Ryan Williams
authored at least 112 papers
between 2002 and 2020.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at zbmath.org

at twitter.com

at orcid.org

at id.loc.gov
On csauthors.net:
Bibliography
2020
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions.
Proceedings of the 2020 ACMSIAM 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 Firstorder Properties on Sparse Structures with Algorithmic Applications.
ACM Trans. Algorithms, 2019
Relations and Equivalences Between Circuit Lower Bounds and KarpLipton 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 resourcebounded 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 ACMSIAM Symposium on Discrete Algorithms, 2019
On Super Strong ETH.
Proceedings of the Theory and Applications of Satisfiability Testing  SAT 2019, 2019
Quadratic TimeSpace 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 ParityCounting SelfReduction.
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 AllPairs 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: NearlyLinear vs BarelySubquadratic Complexity.
Proceedings of the TwentyNinth Annual ACMSIAM Symposium on Discrete Algorithms, 2018
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs.
Proceedings of the TwentyNinth Annual ACMSIAM 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 LowDegree Polynomials.
Proceedings of the 33rd Computational Complexity Conference, 2018
2017
On the (Non) NPHardness of Computing Circuit Complexity.
Theory of Computing, 2017
Some ways of thinking algorithmically about impossibility.
SIGLOG News, 2017
Circuit Lower Bounds for Nondeterministic QuasiPolytime: An Easy Witness Lemma for NP and NQP.
Electronic Colloquium on Computational Complexity (ECCC), 2017
On the Difference Between Closest, Furthest, and Orthogonal Pairs: NearlyLinear vs BarelySubquadratic 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 TwentyEighth Annual ACMSIAM Symposium on Discrete Algorithms, 2017
Faster Online MatrixVector Multiplication.
Proceedings of the TwentyEighth Annual ACMSIAM 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 TwoSatisfiability.
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 NonInteractive Proofs of Batch Evaluation.
Electronic Colloquium on Computational Complexity (ECCC), 2016
Deterministic TimeSpace Tradeoffs for kSUM.
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 RazborovSmolensky.
Proceedings of the TwentySeventh Annual ACMSIAM Symposium on Discrete Algorithms, 2016
Deterministic TimeSpace TradeOffs for kSUM.
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
SuperLinear Gate and SuperQuadratic Wire Lower Bounds for DepthTwo and DepthThree 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 TimeSpace Lower Bounds.
Computational Complexity, 2015
Finding FourNode Subgraphs in Triangle Time.
Proceedings of the TwentySixth Annual ACMSIAM Symposium on Discrete Algorithms, 2015
Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity.
Proceedings of the TwentySixth Annual ACMSIAM Symposium on Discrete Algorithms, 2015
More Applications of the Polynomial Method to Algorithm Design.
Proceedings of the TwentySixth Annual ACMSIAM Symposium on Discrete Algorithms, 2015
The Communication Complexity of Distributed SetJoins with Applications to Matrix Multiplication.
Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015
The CircuitInput 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 TwentyFifth Annual ACMSIAM 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 firstorder graph properties.
Proceedings of the Joint Meeting of the TwentyThird EACSL Annual Conference on Computer Science Logic (CSL) and the TwentyNinth 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
AlternationTrading 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 kSUM.
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 MediumUniformity 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 typicalcase 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 TypicalCase 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 timespace 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
Nonuniform ACC Circuit Lower Bounds.
Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011
2010
Finding heaviest Hsubgraphs 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 TwentyFirst Annual ACMSIAM 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 MaxMin Matrix Products in Truly Subcubic Time.
Theory of Computing, 2009
Finding paths of length k in O^{*}(2^{k}) time.
Inf. Process. Lett., 2009
FixedPolynomial Size Circuit Bounds.
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009
2008
Maximum TwoSatisfiability.
Proceedings of the Encyclopedia of Algorithms  2008 Edition, 2008
Applying practice to theory.
SIGACT News, 2008
NonLinear 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
TimeSpace 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
Allpairs bottleneck paths for general graphs in truly subcubic time.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007
Matrixvector multiplication in subquadratic time: (some preprocessing required).
Proceedings of the Eighteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2007
2006
Finding heaviest Hsubgraphs in real weighted graphs, with applications
CoRR, 2006
Inductive TimeSpace Lower Bounds for Sat and Related Problems.
Computational Complexity, 2006
Finding a maximum weight triangle in n^{3Delta} 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 ACMSIAM 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 HSubgraph in Real Weighted Graphs and Related Problems.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006
2005
A new algorithm for optimal 2constraint satisfaction and its implications.
Theor. Comput. Sci., 2005
Better TimeSpace 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 KAnonymity.
Proceedings of the Twentythird ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems, 2004
2003
On Computing kCNF Formula Properties.
Proceedings of the Theory and Applications of Satisfiability Testing, 2003
Backdoors To Typical Case Complexity.
Proceedings of the IJCAI03, 2003
2002
Algorithms for quantified Boolean formulas.
Proceedings of the Thirteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2002