Scott Aaronson
  • Member for 11 years, 3 months
  • Last seen more than 4 years ago
5 answers
61 votes
4k views
28 bookmarks
Overarching reasons why problems are in P or BPP
3 answers
54 votes
2k views
5 bookmarks
Rigorous security proof for Wiesner's quantum money?
3 answers
40 votes
2k views
19 bookmarks
Circuit lower bounds over arbitrary sets of gates
1 answers
35 votes
2k views
6 bookmarks
Computational complexity of pi
1 answers
23 votes
579 views
4 bookmarks
The randomized query complexity of the conjoined trees problem
1 answers
22 votes
646 views
1 bookmarks
Classifying reversible gates
2 answers
20 votes
678 views
4 bookmarks
For a random oracle R, does BPP equal the set of computable languages in P^R?
3 answers
19 votes
650 views
2 bookmarks
Running a BPP algorithm with a half-random, half-adversarial string
1 answers
16 votes
457 views
3 bookmarks
Complexity classes for proofs of knowledge
1 answers
10 votes
722 views
3 bookmarks
Probability of generating a desired permutation by random swaps