user avatar
user avatar
user avatar
Scott Aaronson
  • Member for 11 years, 10 months
  • Last seen more than 5 years ago
104 votes
Accepted

A simple decision problem whose decidability is not known

76 votes

Applicability of Church-Turing thesis to interactive models of computation

49 votes

Techniques for showing that problem is in hardness "limbo"

46 votes
Accepted

Extended Church-Turing Thesis

41 votes
Accepted

Are there canonical non-relativizing techniques?

40 votes

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

38 votes
Accepted

Is $PH \subseteq PP$?

35 votes
Accepted

Rigour leading to insight

34 votes
Accepted

$BQP$ vs $QMA$?

33 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

29 votes

Quantum computing project ideas

29 votes
Accepted

Computational complexity of pi

28 votes

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

27 votes

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

25 votes

Is the Chomsky-hierarchy outdated?

24 votes

Interactive proofs for levels of the polynomial hierarchy

24 votes
Accepted

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

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

Can relativization results be used to prove sentences formally independent?

18 votes
Accepted

Approximate counting problem capturing BQP

17 votes
Accepted

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

17 votes
Accepted

Alan Turing's Contributions to Computer Science

15 votes

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

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
Accepted

Consequences of $BQP \subseteq P/poly$?

14 votes

Can we decide whether a permanent has a unique term?

12 votes

What is the Relationship between QMA and AM?