Skip to main content
Ryan Williams's user avatar
Ryan Williams's user avatar
Ryan Williams's user avatar
Ryan Williams
  • Member for 13 years, 10 months
  • Last seen more than a week ago
13 votes
Accepted

Characterization of problems for which sublinear time algorithms exist

13 votes

Results showing existence/non-existence of finite graphs with specific computable properties imply certain complexity results

13 votes

DFA intersection in subquadratic space?

13 votes

What is the general consensus on the NL vs P question?

13 votes
Accepted

Law of the Excluded Middle in complexity theory

12 votes
Accepted

Alternate notion of complexity based on gap between brute-force and the best algorithm?

12 votes
Accepted

Space-time tradeoff lower bounds

12 votes

SC^2 algorithms for st-connectivity

12 votes

Introduction to spectral graph theory

12 votes

Fast sparse boolean matrix product with possible preprocessing

12 votes

Rigour leading to insight

12 votes
Accepted

Highest lower bound on NP problems (TSP)

12 votes
Accepted

Solving $n$-SAT and #$n$-SAT

12 votes

How Hard is Exact Simulation of Algorithms, and a Related Operation on Complexity Classes

12 votes

Advanced techniques for determining complexity lower bounds

12 votes

Hardness of a subcase of Set Cover

12 votes
Accepted

Barriers to separating other complexity classes

11 votes

Problems not known to be PSPACE-complete

11 votes
Accepted

$NP$-complete problem with quasi-polynomial bound on the number of solutions

11 votes

On reducing the hardness of CNF-SAT to k-Clique

11 votes

Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

11 votes
Accepted

If NP in BPP then NP equals RP

11 votes
Accepted

Complexity class of efficient streaming algorithms

11 votes

Lower-bounds under SETH

10 votes
Accepted

Trade-off for Barrington's theorem

10 votes

Bootstrapping results that really bootstrap

10 votes

Testing boolean vectors orthogonality with fast query-time

10 votes

Beigel-Tarui transformation of ACC cricuits

9 votes
Accepted

Non-uniform hierarchy theorem for approximating functions

9 votes
Accepted

Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?