MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Ryan Williams

3,126
Reputation
1511 views
Is this your account?

Registered User 

Name Ryan Williams
Member for 3 years
Seen Jun 2 at 4:47
Website
Location California
Age
Interested in algorithms, complexity, and anything that the rest of mathematics can say about these two.
2

Questions
3

2

 

43

Answers
votes newest views recent
36
Can a mathematical definition be wrong?
26
Too old for advanced mathematics?
16
Super-linear time complexity lower bounds for any natural problem in NP?
14
Correct to characterise NP set as P-time image of P set?
13
Complete problems for randomized complexity classes
13
EXPTime algorithms
12
Fast Matrix Multiplication
12
What techniques exist to show that a problem is not NP-complete?
12
What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix?
11
A language complete for NP intersection co-NP
11
How is #P related to other complexity classes?
10
Finding a cycle of fixed length
9
Applications of the Chinese remainder theorem
9
does the “convolution theorem” apply to weaker algebraic structures?
9
Characterize P^NP
9
Is P=NP relevant to finding proofs of everyday mathematical propositions?
9
P/poly algorithm for polynomial identity testing
8
Non-existence of algorithm converting NP algorithm to P algorithm?
7
Non-uniform constant-depth circuits
7
What is the relationship between “translation” and time complexity?
7
When would you read a paper claiming to have settled a long open problem like $P$ vs. $NP$?
7
Does EXP $\in$ P/poly imply NP=RP?
7
How hard is it to solve SAT if the promise is that it has an odd number of solutions?
6
duplicate detection problem
6
Collapsing of exptime and alternation bounded turing machine
6
What are the most important results (and papers) in complexity theory that every one should know?
6
“NP has linear circuits” --> something interesting? [soft, philosophical, open]
5
Provably intractable problems
5
Characterizing visual proofs
5
Finding all roots of a polynomial
1 2 next

 

194

Votes
191
3

 

40

Tags
× 31
× 8
× 7
× 5
× 5
× 5
× 4
× 4
× 3
× 3
 × 3
× 2
× 2



















 

32

Badges
● Good Answer× 2
● Yearling× 3
● Nice Answer× 12
● Popular Question× 2
 ● Enlightened
● Organizer
● Enthusiast
● Citizen Patrol
 ● Commentator
● Autobiographer
● Nice Question
● Scholar
 ● Student
● Critic
● Supporter
● Teacher
 ● Editor