user avatar
user avatar
user avatar
Scott Aaronson
  • Member for 11 years, 9 months
  • Last seen more than 5 years ago
62 votes
5 answers
4k views

Overarching reasons why problems are in P or BPP

54 votes
3 answers
2k views

Rigorous security proof for Wiesner's quantum money?

40 votes
3 answers
2k views

Circuit lower bounds over arbitrary sets of gates

36 votes
1 answer
2k views

Computational complexity of pi

23 votes
1 answer
586 views

The randomized query complexity of the conjoined trees problem

22 votes
1 answer
651 views

Classifying reversible gates

20 votes
2 answers
683 views

For a random oracle R, does BPP equal the set of computable languages in P^R?

19 votes
3 answers
653 views

Running a BPP algorithm with a half-random, half-adversarial string

16 votes
1 answer
463 views

Complexity classes for proofs of knowledge

10 votes
1 answer
730 views

Probability of generating a desired permutation by random swaps