Skip to main content
Share Your Experience: Take the 2024 Developer Survey
Scott Aaronson's user avatar
Scott Aaronson's user avatar
Scott Aaronson's user avatar
Scott Aaronson
  • Member for 13 years, 8 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
630 views

The randomized query complexity of the conjoined trees problem

22 votes
1 answer
690 views

Classifying reversible gates

21 votes
2 answers
741 views

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

19 votes
3 answers
696 views

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

16 votes
1 answer
517 views

Complexity classes for proofs of knowledge

10 votes
1 answer
831 views

Probability of generating a desired permutation by random swaps

8 votes
2 answers
501 views

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