Yaroslav Bulatov sent me the following nice question. Given vectors (a1,…,an) and (b1,…,bn) in Rn, is there an efficient algorithm to decide whether sgn(a1x1+…+anxn) equals sgn(b1x1+…+bnxn) for all x in {0,1}n? I could think about it myself, but wouldn’t it be more fun to call upon the collective expertise of my readers? After all, this is a Serious Blog now. I await the observation that’s eluded me for the past five minutes.
No need to thank me for my turnabout — we’ve got work to do. There’s a new complexity class in town, and I need you to help me name it.
My new class is like P/poly, except that the polynomial-size advice can’t be trusted — you have to verify it. Or to put it another way, it’s like NP intersect coNP, except that there’s only one witness for each input length. Give me that witness, and I’ll correctly decide every input of size n. Give me a different witness, and for every input of size n I’ll either output the right answer or else say “I don’t know.”
Now, anyone could make up a name for this animal — even I could! But I want the name to be naturally extensible to further classes. For example, if (hypothetically speaking) I was able to use a new result about the learnability of quantum states to prove that AvgBQP/qpoly is contained in AvgQMA/poly, but my proof actually yielded the stronger result that AvgBQP/qpoly is contained in the subclass of AvgQMA/poly where there’s only one QMA witness for each input length, then your naming convention should immediately give me a name for that subclass.
So let the christening commence! And for extra credit, prove or (relative to an oracle) disprove that if my class contains NP, then P=NP.
This morning I got an email pointedly criticizing several aspects of this blog — including my handling of l’affaire Chad Okere, and my ridiculing (as opposed to answering) people who think that if P=NP, the major implication would be that airlines could schedule their flights better. The author summed up his critique as follows:
I like your blog. I only wish it would be a little bit more about complexity theory and things at least vaguely related. You have a knack for writing, and for making hard things easy. That’s something which separates you from the large majority of the (blogging) complexity theorists. I understand that you blog in order to procrastinate, and that you have no special obligation to write about anything you don’t want to write about, but I don’t believe I’m alone in thinking that such talent could nonetheless be used to better ends than writing about biting vaginas.
Godammit, I muttered. Though he overestimates my talent, the dude has a point. In my constant battle against predictability, I’ve become too self-absorbed — like Frank Gehry designing the MIT Stata Center, or a Playboy model discoursing on international politics. I’ve neglected the meat-and-potatoes that readers want and expect from me.
So, welcome to a reconceptualized shtetl. From now on I’ll be sure to ladle out the heaping helpings of complexity you crave. The danger, of course, is that as the earnestness and scientific-ness goes up, the sexual innuendoes, heavy-handed irony, ethnic jokes, and crass ridicule will decrease proportionately. Rest assured that I’ll guard against that possibility.
From Discovery News comes a report that Bernardo Provenzano, the recently-arrested “Boss of Bosses” of the Sicilian Mafia, was finally caught because he relied on an encryption system that consisted of ….. [cue the opening notes of The Godfather theme song] ….. adding 3 to the numerical value of each letter. Apparently this has really been a bad week for evil masterminds in Italy.
From the comments on my last post:
scott would you be so kind, if you have some spare time, to post a list of textbooks that you’ve read in math and cs?
Now this is the kind of blog topic I like: zero expenditure of emotional energy required; lends itself to snarky one-liners. So here’s a list of math and CS books that I’ve read and you should too. Pitifully incomplete, but enough to get you started.
You’ve probably spent days, or even months, wondering why I don’t update this blog more often. What could possibly be more important to my career — besides napping, web surfing, napping again, or watching Jon Stewart?
So it’s time to come clean: besides my gig at Shtetl-Optimized, I also have a “day job,” most of which is actually performed at night. Greg Kuperberg, who used to be my most regular commenter before he went M.I.A., has a similar “day job.” If you don’t already know what this day job is, it’s a little hard to explain. We barely understand it ourselves. One thing I can say is that it involves the production of documents like the following:
S. Aaronson and G. Kuperberg, Quantum Versus Classical Proofs and Advice, quant-ph/0604056.
This paper studies whether quantum proofs are more powerful than classical proofs, or in complexity terms, whether QMA=QCMA. We prove two results about this question. First, we give a “quantum oracle separation” between QMA and QCMA. More concretely, we show that any quantum algorithm needs Ω(sqrt(2n/(m+1))) queries to find an n-qubit “marked state” |ψ>, even if given an m-bit classical description of |ψ> together with a quantum black box that recognizes |ψ>. We also prove a matching upper bound. Second, we show that, in the one previously-known case where quantum proofs seemed to help, classical proofs are basically just as powerful. In particular, Watrous gave a QMA protocol for verifying non-membership in finite groups. Under plausible group-theoretic assumptions, we give a QCMA protocol for the same problem. Even with no assumptions, our protocol makes only polynomially many queries to the group oracle. Both of our results apply equally to the problem of quantum versus classical advice — that is, of whether BQP/qpoly equals BQP/poly. We end with some conjectures about quantum versus classical oracles, and about the problem of achieving a classical oracle separation between QMA and QCMA.
Alright, suppose you’re King Arthur. Merlin, your staff wizard, claims to have solved a very hard math problem (a “Holy Grail,” so to speak) on which your entire kingdom depends. The problem might involve, say, the speed of an African swallow, or the best kind of oil in which to boil heretics — the details aren’t important.
Being suspicious of wizards, you want to check Merlin’s solution, but being a king, you don’t have much time to do it. You do, however, have a quantum computer at hand (why not?). Here’s the question: is there anything Merlin could convince you of by giving you a quantum-mechanical superposition, that he couldn’t convince you of by just communicating classically?
QMA, which stands for “Quantum Merlin Arthur,” is (basically) the class of problems for which Merlin could feasibly convince you of the answer by giving you a quantum state. QCMA, which stands for “Quantum Classical Merlin Arthur,” is the class of problems for which Merlin could feasibly convince you of the answer by just communicating classically. (Some people have suggested changing the acronym to CMQA, for “Classical Merlin Quantum Arthur,” since Arthur has the quantum computer while Merlin has to communicate classically.)
The key question is whether QMA and QCMA are equal. So, do Greg and I answer that question in our paper? Of course not — are you nuts?! All we do is get closer to answering it than anyone before. We do so by giving two new pieces of evidence: one suggesting that QMA and QCMA are equal, and another suggesting that they’re not. You might not realize it, but this represents Progress.
To those who aren’t “in the business,” all of this medieval quantum intrigue might raise a question: why do we bother? Why do we spend months writing papers that (if we’re lucky) maybe a hundred people will ever be aware of, and ten will ever understand? Well, Greg can answer for himself. As for me, I’ve always liked the answer once given by Bertrand Russell. And no, this isn’t my “serious” or “official” answer (nor was it Bertie’s), but it’s a fine response to anyone who has to ask.
…a word of advice to such of my hearers as may happen to be professors. I am allowed to use plain English because everybody knows that I could use mathematical logic if I chose. Take the statement: “Some people marry their deceased wives’ sisters.” I can express this in language which only becomes intelligible after years of study, and this gives me freedom. I suggest to young professors that their first work should be written in a jargon only to be understood by the erudite few. With that behind them, they can ever after say what they have to say in a language “understanded of the people.”
Time for a little pet peeve. I’ve gotten numerous emails that say something like, “In your last blog…” when what they mean is, “In your last blog entry…”
A blog is a collection of entries (or posts). The set of possible entries is only countably infinite, but the set of possible blogs has the cardinality of the continuum.
(In practice, the positivity of the cosmological constant does impose an upper bound of about 210^122 on the number of possible blogs. But that’s merely a contingent fact about our universe, and is not intrinsic to the notion of blog. Logically, there’s no reason for a blog ever to end — even though any particular entry, including this one, must.)
What am I mad about? Oh, God.
I’m mad about Bush receiving Michael Crichton in the White House, to be reassured that climate change is a hoax even as the Northwest Passage opens up for the first time in a few million years. I’m mad about the Democrats’ failure to capitalize on the Enron scandal, and particularly the infamous “Grandma Millie” tapes (having just watched the film Enron: The Smartest Guys in the Room). I’m mad about Pius XII, the man who arm-twisted Germany’s 23 million Catholics into cooperating with the Nazis despite their initial opposition, being considered for sainthood (I’m in the middle of a book about it, Hitler’s Pope by John Cornwell). I’m mad about my own procrastination in writing a popular article for Scientific American about the limits of quantum computing. I’m mad about a public school system that condemns any math or science tracking as “elitist,” while the football and basketball programs aren’t similarly condemned. I’m mad about people who declare that “a proof of P!=NP would be worthless, since what if there were an algorithm for SAT that took 1.0000001n steps?,” as if no one had ever had such a perceptive insight in the 50-year history of complexity theory.
But, as for the “not gonna take it anymore” part, one does have to restrict one’s focus a bit. So recently I decided to concentrate my anger on overpriced journal subscriptions — and in particular, on the gouging of university libraries by companies like Kluwer and Elsevier. I’ve just written a three-page polemic about this issue (technically a book review), which is going to appear in SIGACT News, possibly with a rebuttal and counter-rebuttal. I’d be grateful for comments. Note that what I write about scientists’ “peculiar anger deficiency” applies to many other issues, global warming being one obvious example. There comes a time when it’s no longer enough to be correct: you also have to be angry!
Thanks to Bill Gasarch, both for commissioning the review and for suggesting the title of this post.
Note: My diatribe is also available in HTML and postscript.
Yeah, alright. I, Scott Aaronson, have been arrested and have spent eight hours in the custody of the Waterloo police.
Since a lot of bogus information has been circulating about how this happened, let me give you my side of the story. It’s easiest to start with Gaurav Mukherjee, who’s currently an undergrad at IIT New Delhi. I assume most of you have heard of him by now (he’s been all over the blogosphere), but for those who haven’t: earlier this week Mukherjee announced a proof of the “physical independence” of P versus NP and related questions. In a manuscript that’s been circulating by email, he claims to exhibit laws of physics under which P equals NP (in the unrelativized setting), and different laws under which P doesn’t equal NP. Indeed, he even claims to give laws under which P=NP can exist in a quantum superposition of truth and falsehood.
When Gaurav sent me the manuscript on Wednesday, I immediately wrote it off as crackpot nonsense. So when I visited Perimeter Institute yesterday afternoon, I was astonished to find it was all anyone was talking about! I tried in vain to argue with the physicists: “Look, you don’t get it. P versus NP is a mathematical question. By definition, its truth or falsehood can’t depend on any assumptions about physics.”
“Have you even read the paper?” the physicists would shoot back. “That kind of statement only makes sense in a pre-Mukherjee ontology. You might as well say after Einstein’s paper that the rate of time can’t possibly depend on how fast you’re moving!”
“No, that’s a shitty analogy!” I’d respond, getting more and more agitated as the afternoon wore on.
At 9PM or so, a bunch of us decided to hit Jane Bond, a popular bar in Waterloo, to argue about it some more. That’s where things took a turn for the worse. I’ve never held my alcohol well, but the physicists were all ordering three or four beers apiece, so I did the same. By midnight, I’d gotten into an especially ugly argument with a certain postdoc who will remain anonymous. “You complexity theorists, you’re all the same,” he drawled. “Prove this, bound that, this makes no sense, this can’t possibly influence that. Buncha stuck-up pussies.”
The physicists all laughed, and that’s when I lost it.
“You idiot!” I screamed. “You doofus! You ignorant farmer!”
“What did you call me?” the postdoc said, pushing my shoulder so hard I almost fell off my chair.
“An ignorant farmer,” I said, socking him in the jaw as hard as I could.
We both got up. I noticed that the postdoc’s jaw was bleeding. The other Perimeter guys gathered around us — quantum information theorists on one side, cosmologists and quantum gravity theorists on the other. The postdoc and I traded blows for a minute or two until the cops showed up. When they asked who started it, everyone pointed to me, and as a result, I was the only one they arrested! Fortunately, the cops said they wouldn’t charge me with anything, but they did keep me at the station until I sobered up.
I had plenty of time there to think things over. What if Mukherjee is right? I thought. What if the very formulation of Turing machines, P versus NP, and so on depends on presuppositions that I’ve never seriously thought through? There was one particular point in Mukherjee’s paper — the construction of an ontology where polynomial time means the same as exponential time — that I hadn’t understood till then, but that I finally got at 4AM or so. Staring at the walls of the station, the lone officer pacing back and forth, my handcuffs, etc. I could feel my previous worldview crumbling all around me.
By now — Saturday morning — Mukherjee’s paper has changed how I think about almost everything. This might seem like a stretch, but it’s even made me more sanguine about the George W. Bush presidency. Look, if whether P=NP can depend so strongly on our beliefs and assumptions, then why not whether the universe is 6,000 or 14 billion years old, or whether a missile defense system will or won’t work? The bottom line is that facts, logic, and “objective reality” (whatever that means) aren’t nearly as important as I thought they were. If enough people want something to be true, it becomes true. I guess I’ll keep writing this blog, but from now on it’s never going to be the same.
I have good news and bad news, though neither of them has much to do with biting vaginas.
The good news is that Luca Trevisan — complexity theorist extraordinaire, member of my thesis committee at Berkeley, occasional commenter on Shtetl-Optimized, world-renowned for his pronunciation of the word “pseudorandom” — has recently started a blog. Right now Luca is filing travel reports from Beijing, where apparently the food is excellent.
The bad news is that, according to Luca, Shtetl-Optimized has been blocked by the “Great Firewall of China”! Even though Luca congratulates me on my “accomplishment” of being censored in China — an accomplishment not shared by a certain unnamed competitor — this is actually a serious blow to me. See, I’ve long felt that the 1.3 billion citizens of the Middle Kingdom represent the single most promising growth market for the complexity/physics/Jewish-humor/biting-vagina weblog industry. (Oh, you think the Chinese can live without Jewish humor? You might as well say the Jews can live without mu shu and crunchy noodles!)
But what makes this ban by Beijing particularly unfortunate is that, just today, I was planning to blog about my contempt for the moronic pseudoscience of Falun Gong. But that’s only a taste of what I’ve been hoping to tackle in the weeks ahead — including the absurd pretensions of the Dalai Lama (what’s with that robe, dude?), the benefits of collectivized agriculture, the impudence of the Tiananmen Square traitors, and of course, my profound respect for the awesomest person ever:
If you ask me, Marx, Lenin, and Stalin might have paved the way, but Mao surpasses them all as the true voice of the proletariat. Down with capitalist-bourgeois idealism! Reunite Zhōngguó Táibĕi with the motherland!
And while I’m at it, here another experiment, this one aimed at increasing the number of comments on this post: biting vaginas biting vaginas biting vaginas biting vaginas biting vaginas
You are currently browsing the Shtetl-Optimized weblog archives.
Follow