user avatar
user avatar
user avatar
Scott Aaronson
  • Member for 11 years, 10 months
  • Last seen more than 5 years ago
16 votes
1 answer
464 views

Complexity classes for proofs of knowledge

20 votes
2 answers
686 views

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

22 votes
1 answer
655 views

Classifying reversible gates

10 votes
1 answer
733 views

Probability of generating a desired permutation by random swaps

23 votes
1 answer
589 views

The randomized query complexity of the conjoined trees problem

36 votes
1 answer
2k views

Computational complexity of pi

62 votes
5 answers
4k views

Overarching reasons why problems are in P or BPP

19 votes
3 answers
653 views

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

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