Niel de Beaudrap
  • Member for 11 years, 5 months
  • Last seen this week
  • Oxford, United Kingdom
11 answers
65 votes
5k views
21 bookmarks
What are good references to understanding the proof of the PCP theorem?
17 answers
46 votes
4k views
30 bookmarks
Physics results in TCS?
3 answers
39 votes
2k views
6 bookmarks
Is there a backup/replacement for the Complexity Zoo?
2 answers
30 votes
4k views
3 bookmarks
Quantum matrix multiplication?
2 answers
28 votes
2k views
20 bookmarks
A category of NP-complete problems?
2 answers
28 votes
953 views
10 bookmarks
Approximate counting problem capturing BQP
3 answers
27 votes
1k views
13 bookmarks
Succinct Problems in $\mathsf{P}$
4 answers
27 votes
4k views
7 bookmarks
What evidence is there that Graph Isomorphism is not in $P$?
1 answers
21 votes
917 views
6 bookmarks
Algorithms and structural complexity theory
1 answers
21 votes
1k views
5 bookmarks
What's the "real" reason that IP=PSPACE is non-relativizing?
2 answers
20 votes
882 views
11 bookmarks
Problems between NC and P: How many have been resolved from this list?
2 answers
19 votes
937 views
2 bookmarks
Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?
1 answers
18 votes
1k views
3 bookmarks
What is the status of fuzzy logic for TCS in 2011?
1 answers
17 votes
873 views
5 bookmarks
Reading up on $BQP = BPP^{BQNC}$
2 answers
15 votes
1k views
3 bookmarks
Complexity class corresponding to sorting
2 answers
13 votes
720 views
7 bookmarks
Reference for Levin's optimal factoring algorithm ?
1 answers
13 votes
888 views
7 bookmarks
How can I use my computational theory and analysis powers for the greater good?
3 answers
13 votes
6k views
6 bookmarks
Programming Language Theory and Abstract Algebra
6 answers
12 votes
2k views
5 bookmarks
Proof assistant for writing mathematics
3 answers
12 votes
736 views
3 bookmarks
How is duality of types defined?
4 answers
10 votes
716 views
3 bookmarks
Bounding the gap between quantum and deterministic query complexity
2 answers
9 votes
425 views
6 bookmarks
The complexity of Area-lawed Hamiltonians
1 answers
9 votes
335 views
3 bookmarks
Smoothed Analysis: If a Problem has Pseudopolynomial Complexity, is it in Smooth P?
2 answers
7 votes
463 views
4 bookmarks
A System for Visualizing Bibliography Information
0 answers
6 votes
343 views
2 bookmarks
Oracle complexity classes and hardness under different notions of reduction
0 answers
5 votes
139 views
1 bookmarks
What is the relationship between $\mathsf{L}$ reductions and $\mathsf{NC}$ reductions?
0 answers
2 votes
522 views
1 bookmarks
the confusion about 'with high probability (w.h.p.)'