Ryan Williams's user avatar
Ryan Williams's user avatar
Ryan Williams's user avatar
Ryan Williams
  • Member for 14 years, 3 months
  • Last seen more than a month ago
77 votes

Can a mathematical definition be wrong?

48 votes

Too old for advanced mathematics?

29 votes
Accepted

Super-linear time complexity lower bounds for any natural problem in NP?

27 votes
Accepted

Finding a cycle of fixed length

24 votes
Accepted

does the "convolution theorem" apply to weaker algebraic structures?

23 votes

Fast matrix multiplication

22 votes
Accepted

A language complete for NP intersection co-NP

20 votes

What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix?

20 votes

What techniques exist to show that a problem is not NP-complete?

19 votes

Complete problems for randomized complexity classes

18 votes
Accepted

EXPTime algorithms

17 votes
Accepted

Correct to characterise NP set as P-time image of P set?

17 votes

Is P=NP relevant to finding proofs of everyday mathematical propositions?

16 votes

Characterize P^NP (a.k.a. Delta_2^p)

12 votes

Applications of the Chinese remainder theorem

12 votes

When would you read a paper claiming to have settled a long open problem like $P$ vs. $NP$?

12 votes
Accepted

Does EXP $\in$ P/poly imply NP=RP?

11 votes

How hard is it to solve SAT if the promise is that it has an odd number of solutions?

11 votes
Accepted

How is #P related to other complexity classes?

10 votes
Accepted

P/poly algorithm for polynomial identity testing

10 votes

Non-existence of algorithm converting NP algorithm to P algorithm?

9 votes
Accepted

What is the relationship between "translation" and time complexity?

8 votes

"Industry"/Government jobs for mathematicians

8 votes
Accepted

Proofs of Lower Bounds for Ramsey Numbers?

8 votes

duplicate detection problem

8 votes

Finding all roots of a polynomial

7 votes

a proof that L_min is not in coRE?

7 votes
Accepted

Non-uniform constant-depth circuits

7 votes
Accepted

"NP has linear circuits" --> something interesting? [soft, philosophical, open]

6 votes

What are the most important results (and papers) in complexity theory that every one should know?