Scott Aaronson
• Member for 11 years, 4 months
• Last seen more than 4 years ago
• Cambridge, MA

The Matrix Mortality Problem for 2x2 matrices. I.e., given a finite list of 2x2 integer matrices M1,...,Mk, can the Mi's be multiplied in any order (with arbitrarily many repetitions) to produce the ...

Here's my favorite analogy. Suppose I spent a decade publishing books and papers arguing that, contrary to theoretical computer science's dogma, the Church-Turing Thesis fails to capture all of ...

Showing that your problem is in coAM (or SZK) is indeed one of the main ways to adduce evidence for "hardness limbo." But besides that, there are several others: Show that your problem is in NP ∩...

Preparatory Rant I've gotta tell you, I don't see how talking about "proofs" of the CT or ECT adds any light to this discussion. Such "proofs" tend to be exactly as good as the assumptions they rest ...

There's really only one "flagship" non-relativizing technique: namely, arithmetization (the technique used in the proofs of IP=PSPACE, MIP=NEXP, PP⊄SIZE(nk), MAEXP⊄P/poly, and several other ...

I have some "real-world experience" in this nascent industry (and no, I'm not talking about my $200,000 offer to Deolalikar :-) ) In January, a software developer emailed me that he had an attempted ... View answer Accepted answer 38 votes Huck, as Lance and Robin pointed out, we do have oracles relative to which PH is not in PP. But that doesn't answer your question, which was what the situation is in the "real" (unrelativized) world! ... View answer Accepted answer 35 votes András, as you probably know, there are so many examples of what you're talking about that it's almost impossible to know where to start! However, I think this question can actually be a good one, if ... View answer Accepted answer 34 votes 1) No implication is known in either direction. We know that P=NP implies P=PH. But we don't know if BQP and QMA are in PH, so maybe P could equal NP yet BQP and QMA still wouldn't collapse. (On ... View answer 33 votes A flip answer is that this isn't the first thing about complexity theory that I'd try to explain to a layperson! To even appreciate the idea of nonuniformity, and how it differs from nondeterminism, ... View answer 31 votes If an artificial example is really as good as a natural one, then I can indeed provide such an example! Edit: Furthermore, my example is "somewhat" less of a cheat than the one suggested by Ravi ... View answer 29 votes I posted some quantum complexity theory project ideas at http://scottaaronson.com/blog/?p=471 (But beware, most of these are problems that have been open for years! My suggestion for an ... View answer Accepted answer 28 votes OK, James Lee has pointed me to this 2011 paper by Samir Datta and Rameshwar Pratap, which proves that my language$L$(encoding the digits of$\pi$) is in the fourth level of the counting hierarchy ($...

The very terms "on the P-side" and "on the NP-side," and of course the question title, encourage us to imagine a "cozy neighborhood" surrounding P and another "cozy neighborhood" surrounding the NP-...

As others have pointed out, it's debatable to what extent the thing you're trying to explain is even true. One could argue that, in the 60s and 70s, theoretical computer scientists were just more ...

If anything in TCS is outdated, it's this inclusion hierarchy of the tiny subset of complexity classes that happened to be known / considered interesting in 1956. Rest in peace, Chomsky Hierarchy, ...

Thanks for your question! There are two answers, depending on whether you're interested in the hardness results for exact or approximate BosonSampling. In the exact case, we prove that given any n-...

This is a known (wonderful) open problem that I've worked on from time to time without success. Avi Wigderson and I mentioned the problem in our algebrization paper, where we raised the question of ...

Well, one crucial observation is that the new algorithm apparently only works for groups of the form $Z_{p^k}$ where $p$ is small --- it doesn't give a speedup for groups of the form $Z_p$. The ...

Two quick clarifications: Adiabatic QC is typically "based on qubits" just as much as circuit-based QC is -- I don't know where you got the idea that it isn't! (Though one could also use qutrits or ...

There are no "natural" complexity-theory questions that have been proved independent of really powerful formal systems, such as ZF set theory or Peano Arithmetic. (One could certainly construct such ...

Emanuele: Unfortunately, we don't know of any black-box problem capturing BQP as simple as the one you mentioned capturing BPP. Intuitively, this is because it's hard to talk about BQP without ...

To complement what Joe wrote, and maybe explain this question a bit more (without answering it!): The computational complexity of simulating "realistic" quantum field theories has been considered an ...

This question is a lot like asking for Newton's contributions to physics, or Darwin's to biology! However, there's an interesting aspect to the question that many commenters have already seized on: ...

John, while your kind comments are appreciated, I confess that I don't understand how your question relates to the simple point I was making in the quoted remark. All I was saying was that we do know ...

While I don't know the answer to this question, it seems crucial that the phenomenon isn't limited at all to theoretical computer science. I believe SIGGRAPH plays the same sort of role for graphics, ...

I don't know a reference, but I think both of these should be doable. For your first oracle: for starters you'll want an oracle (call it $A_1$) that encodes exponentially-large $MAJORITY$ instances, ...

I'd say we have no good reason to think BQP is in P/poly. We do have reasons to think that BQP is not in P/poly, but they're more-or-less identical to our reasons to think that BQP≠BPP. E.g., if ...

I apologize; I was too glib when I wrote that. While I believe it's possible to prove an oracle separation between $BQP$ and $BPP^{BQNC}$ using current techniques, it hasn't been done (12 years after ...