Theoretical Computer Science
Ryan Williams's user avatar
Ryan Williams's user avatar
Ryan Williams's user avatar
Ryan Williams
  • Member for 13 years, 3 months
  • Last seen this week
Profile Activity

159 Answers

Score Activity Newest
17 votes
Accepted

Are quasi-polynomial sized circuits for 3-SAT trivial?

17 votes

Constructivity in Natural Proof and Geometric Complexity

17 votes

Can one return to a TCS research job after an excursion to a non-research industry job?

17 votes

Books/Lecture Notes on Parametrized Complexity

17 votes
Accepted

What is the most general structure on which matrix product verification can be done in $O(n^2)$ time?

17 votes

Techniques for Reversing the Order of Quantifiers

17 votes
Accepted

Is there a Time Hierarchy theorem for PH?

17 votes

Proofs, Barriers and P vs NP

16 votes
Accepted

Permanents - Approximation and connection to integer factorization

16 votes
Accepted

Complexity of Unique s-t-Connectivity

16 votes

A data structure for minimum dot product queries

16 votes
Accepted

Is ALogTime != PH hard to prove (and unknown)?

16 votes
Accepted

Memory requirement for fast matrix multiplication

16 votes
Accepted

An obstruction like ETH

15 votes
Accepted

Smallest vertex cover which is also an independent set

15 votes

Scope of natural proofs barrier

15 votes
Accepted

The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem

15 votes
Accepted

Uses of XORification

15 votes
Accepted

Complexity Classes for Cases Other Than "Worst Case"

15 votes

Open problems on the frontiers of TCS

15 votes
Accepted

What are the best known upper bounds and lower bounds for computing O(log n)-Clique?

15 votes
Accepted

Are there natural separations in the nondeterministic time hierarchy?

14 votes
Accepted

Are there alternatives to using polynomials in defining the different notions of efficient computation?

14 votes
Accepted

NP-complete variants of undecidable problems?

14 votes

MAX 1 in 2 SAT Algorithm

14 votes
Accepted

Complexity of k-clique for hypergraphs

13 votes

Does the isomorphism conjecture imply exponential lower bounds on witnesses density?

13 votes
Accepted

Collapses under the assumption that $NEXP\subseteq P/Poly$

13 votes

What is the fastest known simulation of BPP using Las Vegas algorithms?

13 votes
Accepted

Characterization of problems for which sublinear time algorithms exist

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.