User Ryan Williams - MathOverflow

Ryan Williams

Member for 14 years, 4 months
Last seen more than a month ago

Twitter
people.csail.mit.edu/rrw
Cambridge, MA, United States

43 Answers

Score Activity Newest

5 votes

Accepted

Characterizing visual proofs

answered Jun 25, 2010 at 19:25

19 votes

Complete problems for randomized complexity classes

answered Aug 4, 2010 at 3:46

20 votes

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

answered Dec 18, 2009 at 9:30

24 votes

Accepted

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

answered Jan 13, 2010 at 2:12

29 votes

Accepted

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

answered Dec 16, 2009 at 6:07

7 votes

Accepted

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

answered Mar 12, 2011 at 1:53

17 votes

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

answered Dec 2, 2010 at 17:04

11 votes

Accepted

How is #P related to other complexity classes?

answered Sep 23, 2010 at 7:52

3 votes

Finding a subgraph with slightly large size in planar graphs

answered Aug 23, 2010 at 5:28

4 votes

Accepted

nonasymptotic complexity results

answered Aug 21, 2010 at 18:54

10 votes

Accepted

P/poly algorithm for polynomial identity testing

answered Aug 12, 2010 at 8:13

4 votes

Accepted

Use of randomness in constant parallel time

answered Aug 11, 2010 at 3:18

6 votes

Collapsing of exptime and alternation bounded turing machine

answered Aug 9, 2010 at 21:38

12 votes

Accepted

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

answered Aug 9, 2010 at 16:41

12 votes

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

answered Aug 8, 2010 at 22:35

22 votes

Accepted

A language complete for NP intersection co-NP

answered Aug 8, 2010 at 6:22

17 votes

Accepted

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

answered Aug 7, 2010 at 16:08

6 votes

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

answered Aug 5, 2010 at 15:05

23 votes

Fast matrix multiplication

answered Aug 2, 2010 at 2:48

9 votes

Accepted

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

answered Jul 18, 2010 at 2:05

7 votes

Accepted

Non-uniform constant-depth circuits

answered Jul 18, 2010 at 1:02

18 votes

Accepted

EXPTime algorithms

answered Jul 14, 2010 at 6:40

79 votes

Can a mathematical definition be wrong?

answered Jul 11, 2010 at 5:30

5 votes

Accepted

Provably intractable problems

answered Jul 11, 2010 at 1:21

3 votes

A decision problem in graph coloring

answered Jul 9, 2010 at 17:20

8 votes

Accepted

Proofs of Lower Bounds for Ramsey Numbers?

answered Jun 24, 2010 at 22:34

8 votes

"Industry"/Government jobs for mathematicians

answered Jun 17, 2010 at 16:56

10 votes

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

answered Jun 12, 2010 at 6:56

8 votes

duplicate detection problem

answered May 20, 2010 at 23:37

3 votes

Accepted

Is every input gate of a Boolean Circuit (to decide a language) on a path to the output gate?

answered May 20, 2010 at 19:50

1