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
107 votes
Accepted

A simple decision problem whose decidability is not known

76 votes

Applicability of Church-Turing thesis to interactive models of computation

50 votes

Techniques for showing that problem is in hardness "limbo"

46 votes
Accepted

Extended Church-Turing Thesis

42 votes

Should experts in TCS charge money to read proofs that P != NP?

41 votes
Accepted

Are there canonical non-relativizing techniques?

40 votes
Accepted

Is $PH \subseteq PP$?

35 votes
Accepted

Rigour leading to insight

34 votes
Accepted

$BQP$ vs $QMA$?

34 votes

The unreasonable power of non-uniformity

31 votes

A decision problem which is not known to be in PH but will be in P if P=NP

30 votes
Accepted

Computational complexity of pi

29 votes

Why are so few natural candidates for NP-intermediate status?

29 votes

Quantum computing project ideas

28 votes

The cozy neighborhoods of "P" and of "NP-hard"

26 votes
Accepted

How does the BosonSampling paper avoid easy classes of complex matrices?

25 votes

Interactive proofs for levels of the polynomial hierarchy

25 votes

Is the Chomsky-hierarchy outdated?

19 votes

Is adiabatic quantum computing as powerful as the circuit model?

19 votes
Accepted

New algorithm for Discrete log and its implications for Quantum computing

18 votes
Accepted

Approximate counting problem capturing BQP

18 votes
Accepted

Ed. Witten's new paper and the simulation of a quantum field theory

17 votes
Accepted

Can relativization results be used to prove sentences formally independent?

17 votes
Accepted

Alan Turing's Contributions to Computer Science

16 votes
Accepted

Consequences of $BQP \subseteq P/poly$?

15 votes

How did TCS become conference-oriented rather than journal-oriented?

15 votes

Complexity of optimization over unitary group

15 votes
Accepted

Do natural generalizations of P versus NP exist?

14 votes
Accepted

Relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$

14 votes

Can we decide whether a permanent has a unique term?