Theoretical Computer Science
Ryan Williams's user avatar
Ryan Williams's user avatar
Ryan Williams's user avatar
Ryan Williams
  • Member for 12 years, 10 months
  • Last seen more than a week ago
Profile Activity

155 Answers

Score Activity Newest
88 votes
Accepted

Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?

54 votes

What papers should everyone read?

48 votes

How do you get a "Physical Intuition" for results in TCS?

47 votes
Accepted

What are the best current lower bounds on 3SAT?

40 votes

Problems that can be used to show polynomial-time hardness results

40 votes
Accepted

Inspirational talk for final year high school pupils

38 votes
Accepted

Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$

35 votes
Accepted

Matrix multiplication in $O(n^2 \log n)$

33 votes

Is $AC^0/poly \cap NP$ contained in $P$?

31 votes
Accepted

True Bit Complexity of matrix multiplication is $O(n^{4})$

31 votes
Accepted

Is there any justification to believe that $NL\neq L$?

31 votes
Accepted

Space complexity of Coppersmith–Winograd algorithm

31 votes
Accepted

Super-polynomial time approximation algorithms for MAX 3SAT

30 votes
Accepted

Is there any book on the philosophical implications of Theoretical Computer Science?

30 votes
Accepted

Lower bounds on #SAT?

30 votes

Examples of the price of abstraction?

30 votes
Accepted

How many tautologies are there?

29 votes

Semantic vs. Syntactic Complexity Classes

29 votes
Accepted

Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

28 votes
Accepted

What is $\mathsf{NP}$ restricted to linear size witnesses?

28 votes
Accepted

NTIME(n^k) ≠ DTIME(n^k) ?

28 votes
Accepted

NC = P consequences?

27 votes

Is there a complexity theory analogue of Rice's theorem in computability theory?

27 votes
Accepted

What is the big version of NC?

26 votes

Toy examples for barriers to $P \ne NP$

26 votes

References for TCS proof techniques

25 votes

Implications of proof of abc conjecture for cs theory

25 votes

Proof that circuit upper bounds for $E$ imply $P \neq NP$

24 votes

Problems with big open complexity gaps

24 votes
Accepted

Is "Experimental Complexity Theory" being used to solve open problems?

1
2 3 4 5 6

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.