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

158 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?

41 votes
Accepted

Inspirational talk for final year high school pupils

40 votes

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

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

Lower bounds on #SAT?

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

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?

28 votes
Accepted

What is the big version of NC?

27 votes

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

26 votes

References for TCS proof techniques

26 votes

Toy examples for barriers to $P \ne NP$

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

Hierarchy for BPP vs derandomization

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.