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
8 votes
2 answers
495 views

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

22 votes
1 answer
682 views

Classifying reversible gates

16 votes
1 answer
506 views

Complexity classes for proofs of knowledge

21 votes
2 answers
737 views

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

10 votes
1 answer
822 views

Probability of generating a desired permutation by random swaps

24 votes
1 answer
624 views

The randomized query complexity of the conjoined trees problem

36 votes
1 answer
2k views

Computational complexity of pi

64 votes
5 answers
5k views

Overarching reasons why problems are in P or BPP

19 votes
3 answers
694 views

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

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