It’s the Science Blog Carnival! Come see me hawking my wares, alongside Peter Woit, Dave Bacon, and dozens of other clowns.
Archive for the ‘Self-Referential’ Category
In the wake of my very public relativity humiliation, I’ve decided to sentence myself to a one-month punishment term of only blogging about things that I actually understand. That means, unfortunately, that from now until September 27 this blog is going to be quite boring and limited in scope. It also means that Lev R.’s prizewinning question, about the survival prospects of the human race, will need to be deferred until after the punishment term.
To be clear: No string theory. No global warming. No biting vaginas. No Mahmoud. Quantum complexity classes are probably kosher.
The remainder of today’s entry will be about the topic of bananas. Bananas are long, yellow fruits that grow in bunches on some sort of plant or other. They consist of two components: the peel, and the “meat.” Well, there are probably other components as well, but those two are the most readily identifiable. The meat is delicious when fresh, even more so if covered with chocolate. When not fresh, on the other hand, it tends to form brown spots. The peel is not so good to eat, but is reputed to good for tripping dumb, careless, unwary people. Like me.
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.
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.)
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
If a layperson asks you what computational complexity is, you could do worse than to tell the following story, which I learned from Steven Rudich.
A man with a flowing gray beard is standing on a street corner, claiming to be God. A bemused crowd gathers around him. “Prove it!” they taunt.
“Well,” says the man,”I can beat anyone at chess.”
A game is duly arranged against Kasparov, who happens to be in town. The man with the gray beard wins.
“OK, so you’re pretty good at chess,” the onlookers concede. “But that still doesn’t mean you’re God.”
“O ye of little faith! As long as I play White, it’s not just hard to beat me — it’s mathematically impossible! Play Black over and over, try every possible sequence of moves, and you’ll see: I always win.”
A nerd pipes up. “But there are more sequences of moves than there are atoms in the universe! Even supposing you beat us every day for a century, we’d still have no idea whether some sequence of moves we hadn’t tried yet would lead to your defeat. We’ll be long dead before every possibility is examined. So unless you’re prepared to grant us immortality, there’s no way you can possibly convince us!”
Most of you know the punchline to this story, but for those who don’t: the nerd is wrong. By asking a short sequence of randomly-chosen questions, each a followup to the last, the crowd can quickly convince itself, to as high a confidence as it likes, that the man they’re interrogating knows a winning strategy for White — or else expose his lie if he doesn’t. The reason was discovered in 1990 by Lund, Fortnow, Karloff, Nisan, and Shamir, and has less to do with chess than with the zeroes of polynomials over finite fields.
There are two lessons I’d like to draw from Rudich’s Fable of the Chessmaster.
The first lesson is that computational complexity theory is really, really, really not about computers. Computers play the same role in complexity that clocks, trains, and elevators play in relativity. They’re a great way to illustrate the point, they were probably essential for discovering the point, but they’re not the point.
The best definition of complexity theory I can think of is that it’s quantitative theology: the mathematical study of hypothetical superintelligent beings such as gods. Its concerns include:
- If a God or gods existed, how could they reveal themselves to mortals? (IP=PSPACE, or MIP=NEXP in the polytheistic case.)
- Which gods are mightier than which other gods? (PNP vs. PP, SZK vs. QMA, BQPNP vs. NPBQP, etc. etc.)
- Could a munificent God choose to bestow His omniscience on a mortal? (EXP vs. P/poly.)
- Can oracles be trusted? (Can oracles be trusted?)
And of course:
- Could mortals ever become godlike themselves? (P vs. NP, BQP vs. NP.)
Incidentally, it’s ironic that some people derisively refer to string theory as “recreational mathematical theology.” String theory has to earn the status of mathematical theology — right now it’s merely physics! A good place for string theorists to start their theological training is this recent paper by Denef and Douglas.
So that was my first lesson. The second lesson is that interaction helps: you can get your message across a lot faster if people are continually challenging you. If the gray-bearded man were just lecturing to a passive audience, rather than being grilled by doubters trying to trap him in a contradiction, then it would take longer than the age of the universe for him to prove his unbeatability at chess. Or rather, we theologians conjecture that it would.
I’m reminded of the power of interaction every time I give a talk. Despite a certain reputation for cheap yuks, I’ve never been a good speaker. I’m terrible at explaining anything coherently — that is, in a way that anticipates people’s objections. Fortunately, as long as people interrupt me, it doesn’t matter much, since I can easily answer the objections once I know what they are. Indeed, not only do interruptions clue me in on what’s bugging people — as in the Fable of the Chessmaster, they also let me prove that I basically know what I’m talking about, even if I can’t articulate it in the allotted time!
(In my ideal talk, I would begin by saying “Thank you. Are there any questions?”)
For another example, take the sex columnist Dan Savage. Savage has a “philosophy,” which consists partly of a refusal to condemn sex acts if they don’t harm anyone, and a willingness to condemn them if they do. But if he tried to state his philosophy explicitly, he wouldn’t do it justice any more than I just did. So instead he answers questions about used underwear fetishes and masturbating parakeets.
The same goes for comedians, at least the good ones like Jon Stewart. Stewart has an enviably easy job: news happens, he reacts to it. It’s like my ideal talk that consists entirely of questions — except that instead of questions, there’s Bush warning about “human-animal hybrids” in his State of the Union address, or Cheney shooting his hunting buddy in the face.
Inspired by such examples, and by my recent positive experience answering Peter Brooke’s question, I’ve decided to open this blog to questions on a regular basis. Email them, post them in the comments section, whatever. I can’t promise to take up everything. Try to guess which of the following would have a better chance:
“Please discuss the relative merits of conference and journal publication in theoretical computer science.”
“How could schools be redesigned to improve the sex lives of nerds?”
Like a masked chicken of the darkness, the anonymous commenter deposits his ad hominem attack and then flees the scene, as though repelled by the malodorous stench of his own words. Alright, I’m not Stephen King. But the point is that, if you leave an anonymous comment that doesn’t contribute anything, from now on I’m going to feel free to delete it. I will never delete signed comments, unless they’re completely off-topic, or reveal the coordinates of nuclear missiles being transported across South Dakota, or something like that. Oh yeah: and tomorrow night, if you’re going to egg any houses or toilet-paper any trees, sign your work.
I’ve caved in to popular demand. From now on, every embryonic insight, discursive jumble of neural firings, and missive from the depths of my soul will be filed under a pithy title, so that readers on the go can quickly decide which ones are worth their time to read. To maintain consistency, I also went back and titled the 17 previous posts.
This is a question recently asked by Lance Fortnow. There are a few boring answers: I thought I wouldn’t have time, what with my packed schedule of websurfing, procrastinating, and sleeping. I thought the human race had already overpopulated God’s green blogosphere. I thought the bandwagon had already passed in 2003, and there was no use chasing it now. I thought it would be presumptuous (as indeed it is).
But the real answer is that to run a successful blog, I knew I’d have to write about what actually mattered to me — and that included more than just the latest arXiv preprints or bizarre complexity classes. I’d have to state strong opinions, make my worst fears everyone else’s business, probably offend some people, and probably embarrass myself. So before I did that, I wanted to make sure I could at least do it in the best, most eloquent words — words that couldn’t possibly be misunderstood.
So what happened? Did I find those words? As you can see for yourself, I didn’t. What happened is that, after finishing grad school and reaching an advanced age, I started to face my mortality. Before then, I could always justify inaction by telling myself I was still preparing for the rest of my life. But once you’re in the rest of your life, if you’re not actually living it, then what are you doing? It occurred to me that, if you wait for the “perfect opportunity” to start a weblog — or switch to a new research area, or ask someone out, or whatever it is you want to do — then you’re essentially just committing delayed suicide. I’m sorry if that sounds trite and obvious.
Efficiency matters. Time constraints change everything. How could I have forgotten?