Scott Aaronson's user avatar
Scott Aaronson's user avatar
Scott Aaronson's user avatar
Scott Aaronson
  • Member for 13 years, 6 months
  • Last seen more than a month ago
64 votes
5 answers
5k views

Overarching reasons why problems are in P or BPP

54 votes
3 answers
3k 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

24 votes
1 answer
625 views

The randomized query complexity of the conjoined trees problem

22 votes
1 answer
687 views

Classifying reversible gates

21 votes
2 answers
738 views

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

19 votes
3 answers
694 views

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

16 votes
1 answer
510 views

Complexity classes for proofs of knowledge

10 votes
1 answer
826 views

Probability of generating a desired permutation by random swaps

8 votes
2 answers
497 views

Given real numbers $x_1,...,x_n$ , find the maximum of $ \frac{(x_j-x_i)^2}{j-i}$