Shtetl-Optimized

I arrived yesterday in Innsbruck, Austria — a lovely medieval town set in a valley in the Tyrolean Alps. Here the Pontiff and I are sharing an office at the Institut für Quantenoptik und Quanteninformation, and will have to work out a comedy routine to be performed Friday morning, when we’re supposed to open the QIPC meeting at Ike Newton’s old stomping grounds, the Royal Society in London.

Since I’m too jetlagged to write a coherent entry, I hope you’ll be satisfied with some lists:

The three secrets of air travel (distilled from a decade of experience flying to four continents, and offered free of charge to you, my readers):

1. Bring a book. Don’t even try to work on the plane; just read read read read read. If you get stuck in the airport for hours, all the more time to read!
2. If you must work, do it with pen and paper, not a laptop.
3. Put your laptop case in the overhead bin, not under your seat. This will give you more room to stretch your legs.

The only three German words you’ll ever need to know:

1. Danke (thank you). To be said after any interaction with anyone.
2. Ein (one). As in: I will have one of those (pointing).
3. Entscheidungsproblem (decision problem). The problem of deciding whether a first-order sentence is true in every interpretation, proven to be undecidable by Church and Turing.

The two things I saw yesterday that I wish I’d taken a photo of but didn’t:

1. A jewelry store display case, proudly displaying “SCHMUCK” brand designer watches. (Important Correction: Ignorant schmuck that I am, I hadn’t realized that “schmuck” is not a brand name, but just the German word for jewelry. Apparently the meaning in Yiddish migrated from “jewels” to “family jewels” to “person being compared to the family jewels,” which is a bit ironic. “Oh my turtledove, the apple of my eye, my priceless schmuck…”)
2. A campaign poster for one of Austria’s far-right politicians, which graffiti artists had decorated with a Hitler mustache, a forehead swastika, and salutations of “Heil!” (Just what point were the graffiti artists trying to make? I wish I understood.)

Follow

I woke up at my normal time — probably around 2PM — in my room at Berkeley’s International House, to find an avalanche of email: from a fellow grad student, urging everyone to check the news; from Christos Papadimitriou, reminding us that we have a community here, and communities can comfort; from Luca Trevisan, announcing that the class that he taught and I TA’ed would be canceled, since on a day like this it was impossible to think about algorithms. I then clicked over to news sites to find out what had happened.

After confirming that my friends and family were safe, I walked over to my office in Soda Hall, mostly to find people to talk to. Technically I had office hours for the algorithms class that afternoon, but I didn’t expect students actually to come. Yet come they did: begging for hints on the problem set, asking what would and wouldn’t be on the test, pointing to passages in the CLRS textbook that they didn’t understand. I pored over their textbook, shaking my head in disbelief, glancing up every minute or so at the picture of the burning buildings on the computer screen.

That night there was a big memorial service in Sproul Plaza. When I arrived, a woman offered me a candle, which I took, and a man standing next to her offered me a flyer, which I also took. The flyer, which turned out to be from a socialist organization, sought to place the events of that morning in “context,” describing the World Trade Center victims as “mostly white-collar executives and those who tried to save them.”

After a few songs and eulogies, a woman got up to explain that, on this terrible day, what was really important was that we try to understand the root causes of violence — namely poverty and despair — and not use this tragedy as a pretext to start another war. The crowd thunderously applauded.

While the speeches continued, I got up and wandered off by myself in the direction of Bancroft Way. Much as I did the year before, when the area around Telegraph was festooned with Nader for President posters, I felt palpably that I wasn’t living in an outcomes-based region of reality. The People’s Republic of Berkeley was proving to be a staunch ally of the Oilmen’s Oligarchy of Crawford, undermining the only sorts of opposition to it that had any possibility of succeeding.

I decided to forget about politics for a while and concentrate exclusively on research. I can’t say I succeeded at this. But I did pass my prelim exam three days later (on September 14), and a few weeks afterward proved the quantum lower bound for the collision problem.

Note: Feel free to post your own retrospective in the comments section. Andris Ambainis has already done so.

Follow

From left: Amnon Ta-Shma, your humble blogger, David Zuckerman, Adi Akavia, Adam Klivans. Behind us: the majestic mountains of Banff, Canada, site of yet another complexity workshop, which I just returned from a couple days ago, after which I immediately had to move out of my apartment, which explains the delay in updating the blog. Thanks to Oded Regev for the photo.

A few highlights from the workshop:

• Rahul Santhanam presented a proof that for every fixed k, there exists a language in PromiseMA with no circuits of size n^k. This is a problem I spent some time on last year and failed to solve.
• Dmitry Gavinsky discussed the question of whether quantum one-way communication complexity can be exponentially smaller than randomized two-way communication complexity. Richard Cleve has a candidate problem that might yield such a separation.
• Ryan O’Donnell presented a proof that one can decide, using poly(1/ε) queries, whether a Boolean function is a threhold function or is ε-far from any threshold function. This is much harder than it sounds.
• I took a gondola to the top of Sulphur Mountain, where the above photo was taken. While walking amidst some slanty rocks, I slipped and twisted my ankle. I was hobbling around for several days afterward, but seem to be OK now.

Overwhelming everything else, alas, was a memorial session for Misha Alekhnovich. Misha, who loved extreme sports, went on a whitewater kayaking trip in Russia a month ago. At a dangerous bend in the river, his three companions apparently made it to shore safely, while Misha did not. He was 28, and was to get married a few days from now.

Misha and I overlapped as postdocs at IAS, and I wish I’d gotten to know him better then. From the conversations we did have, it was clear that Misha missed Russia and wanted to go back as soon as possible. The truth, though, is that I knew Misha less on a personal level than through his groundbreaking work, and particularly his beautiful paper with Razborov, where they show that the Resolution proof system is not automatizable unless FPT = W[P]. I still find it incredible that they were able to prove such a thing.

Lance has already discussed the memorial session, in which Eli Ben-Sasson and Sasha Razborov offered their personal remembrances, while Toni Pitassi and Russell Impagliazzo gave talks about Misha’s work, emphasizing how the P versus NP question always lay just beneath the surface. It occurred to me that an outsider might find these talks odd, or even off-putting. Here we were, at a memorial for a dead colleague, talking in detail about the definition of automatizability and the the performance of the DPLL algorithm on satisfiable CNF instances. Personally, I found it moving. At a funeral for a brilliant musician, would one discuss his “passion for music” in the abstract without playing any of his songs?

The tragic loss of Misha has reinforced a view I’ve long held: that if challenge is what you seek, then the thing to do is to tackle difficult open problems in math and computer science (or possibly physics). Unlike the skydiver, the kayaker, or the mountain-climber, the theorem-prover makes a permanent contribution in the best case, and is down a few months and a few hundred cups of coffee in the worst case. As for physical challenges, walking around heavily-populated tourist areas with slanty rocks has always presented more than enough of them for me.

Follow

Sorry for the long delay! I had to be in Washington D.C. this week, for reasons I’m not at liberty to disclose. (Yes, I’m serious, and no, it’s not as interesting as it sounds.) Oh: on my way back to Canada, for some strange reason they confiscated my Blistex. I guess airport security guards get chapped lips a lot.

As our world descends even further into war, terror, and Armageddon, I have an exciting complexity-theoretic announcement. Building on the Complexity Zoo, Greg Kuperberg has created a “Robozoologist”: an expert system for reasoning about complexity classes. What’s more, Greg is releasing some spinoffs of his project to the masses, including a JavaScript-powered inclusion graph, and an automatically-generated RoboZoo. I can still remember them frontier days of 2002, when I had to herd the BP operators with my two bare hands…

Follow

• Why do I procrastinate so much on blog posts, even to the extent of not blogging about a trip until well after it’s over? Because, while coming up with the ideas (i.e., the jokes) is trivial, writing the connective tissue is a pain in the ass.

• Bulleted lists are easier. Expect me to fall back on them more often.

• So, Prague. It was nice. Really nice. Nicer than Amsterdam even.

• Like a fool, I somehow expected that, since it’s been less than two decades since the Velvet Revolution, Prague would still be some sort of backwards city in consonant-intensive Eastern Europe, grateful for any tourists it could get.

• I dramatically overestimated how long it would take for a former Communist stronghold to become Disneyland, a.k.a. the college backpacker capital of the world.

• I’m told there are two reasons for this transformation: (1) castles and cathedrals that weren’t completely reduced to rubble by WWII, and (2) cheap beer (less than $1 a pint). Of course, factoring in the cost of airfare and hotels, you’d have to drink hundreds of beers to save money. But we are talking about college backpackers.

• Have you heard of Jan Hus? A century before Martin Luther, he was already pulling the same shtick: condemning the selling of indulgences, advocating a return to Christ’s original teachings, etc. Of course the Catholics burned him at the stake. This led to the Hussite Wars, which I guess I would’ve learned about had I stayed in high school long enough to take AP Euro. Anyway, there’s a big statue of Mr. Hus in Prague’s Old Town Square (you can see a photo of it on Hus’s Wikipedia page). Get this: the statue is glaring angrily at a nearby Catholic church. As you might have gathered, I’ve never been much of an art critic, but I think I more-or-less understood what the sculptor was getting at.

• I also saw the biggest telescope in the Czech Republic.

• Oh, yeah: there was a conference. It was about complexity or something.

• Seriously, it was an excellent conference, except that the lecture room wasn’t air-conditioned. As a direct result, I can remember very little of the talks. (Is it better to contribute to global warming or to experience it?)

• If you’re ever in Prague, definitely visit the Museum of Communism (“back-handed bribes accepted in our gift shop”), especially if you’ve never been to a Soviet-bloc country before (as I hadn’t). Learning about the 19^th century’s worst idea on a North American campus is different from learning about it on Wenceslas Square.

• Unfortunately, when I visit European cities like Amsterdam and Prague, I can never completely forget that I’m walking through a big murder scene. (“Thank you, waiter, for bringing me my chicken! And thank you, as well, for not deporting me to Theresienstadt or shooting me into an open pit! When you get a chance, could you maybe refill my water?”)

• Why does Prague have one the best Judaica collections in the world? Because the Nazis shipped their loot there, expecting to open a historical museum about the human bacillus they had successfully eradicated. (There is such a museum today, but run by the bacillus itself.)

• Speaking of which, have you heard of the Golem? It was a clay robot allegedly built in the 1500’s by Rabbi Judah Löw of Prague. This robot, you see, went rampaging around, causing random destruction, until the townspeople agreed to halt their anti-Semitic attacks. (A bit like the IDF in Lebanon.) According to legend, the Golem’s remains are still in the attic of Prague’s Old-New Synagogue, and can be reanimated if necessary. The attic is closed to visitors, but the guidebooks say that recently some great rabbi was allowed to ascend to the attic, and “returned white and trembling.” (As a friend of mine remarked, they forgot to mention that the old fellow was also white and trembling before he went up the attic.) In any case, the Golem was apparently out of service when most needed.

Follow

Who: From left, Ashwin Nayak, Debbie Leung, Mike Mosca, your humble squinting blogger, Andris Ambainis with coffee, Patrick Hayden.

Where: Haines Junction (population 789), Yukon Territory, 100 miles east of Alaska. One of the furthest outposts of civilization, surrounded by one of the last pristine wilderness areas on Earth.

When: We arrived here last night, after flying to Whitehorse and then battling heavy traffic (i.e., at least two other cars) for several hours on the Alaska Highway.

What: A quantum computing workshop sponsored by the CIAR (Canadian Institute for Advanced Research).

Why: I dunno, I guess the CIAR has more money than it knows what to do with.

How: You thought they wouldn’t have WiFi here?

Follow

Ever since I arrived at fellow blogger Dave Bacon‘s house on Tuesday, the Pontiff and I have been tossing around ideas for a joint blog initiative. Finally we hit on something: since we’re both neologistas — people who enjoy spending their free time coining new words — we decided to compile a list of the neologisms we’d most like to see adopted by the general population. Without further ado:

shnood: (roughly) an imposter; a person oblivious to just how trivial or wrong his ideas are.

“Were there any interesting speakers at the conference?”
“No, just a bunch of shnoods.”

“The magazine New Scientist loves to feature shnoods on the cover.”

Note: someone who’s utterly contemptible would not be a shnood, but rather a schmuck.

iriterie: a list or compilation of people named Irit.

See the comments on the last post for an example of an iriterie.

extralusionary intelligence: intelligence in one domain that is misapplied in another.

“Bob’s a brilliant physicist — I bet he’s onto something with his condensed-matter approach to P versus NP.”
“No, he’s just suffering from extralusionary intelligence.”

circumpolitical: So far to one end of the political spectrum that one is actually on the other end.

“Professor Zimmerman mounted a circumpolitical defense of hereditary dictatorship, female genital mutilation, and the dragging of murdered homosexuals through the streets, arguing that we have no right to condemn these indigenous practices of non-Western peoples.”

philosonomicon: A philosophical prolegomenon.

Dave’s PhD thesis begins with a philosonomicon, as does mine.

high-hanging fruit: the opposite of low-hanging fruit.

“Do you ever think about the Nonabelian Hidden Subgroup Problem?”
“No, that’s high-hanging fruit. I like to watch other people jump for it.”

napotonin: any substance that makes you want to nap.

“Ohhhh … must’ve been a lot of napotonin in that calzone … can’t work … unnngghhhh”

nontrivia: the opposite of trivia.

“If you’re so smart, how come you’re no good at Trivial Pursuit?”
“Because I prefer to fill my brain with nontrivia.”

In an effort to speed up the adoption of these words by the Oxford English Dictionary, Dave and I hereby ask that every comment on this post correctly use at least one of them. Also, while you’re welcome to crack the obvious jokes (“Scott is a shnood,” “Dave suffers from extralusionary intelligence,” etc.), be aware that we’ve just preempted them.

Follow

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.

Follow

I have made my first (and, I expect, last) contribution to the Sarong Theorem Archive, the only public repository of images of people proving theorems while wearing sarongs. I encourage all of you to contribute as well to this important archive. Thanks to Daniel Gottesman for the photography (and the use of his office), Karp and Lipton for the theorem, and Kelly Itakura for the sarong.

Follow

The list of accepted papers for STOC’06 is now available. The process of forming this list confirmed my fundamental respect for the scientific peer review process — a process that, in its speed, objectivity, and reliance on reasoned argument, might someday rival such renowned deliberative bodies as the US House of Representatives.

For this experience I’m deeply grateful to my 19 fellow program committee members, except of course when they mistakenly disagreed with me. I’m especially grateful to Jon Kleinberg, the PC chair, for inviting me to join the committee, even though he only gave me an A- in his COMS681 Analysis of Algorithms class my freshman year at Cornell. Finally I feel like I’ve made it.

I’d love to tell you all about the heated debates, shifting alliances, and last-minute turnarounds that characterized our committee meeting in the moonlit Fortress of STOC — until we, clad in hooded robes, brandishing our laptops as torches, and calling on NEXP and PSPACE for benediction, sealed the minutes of our deliberations in the sacred Vault of Turing, which no one without a PhD in a technical subject can gaze upon and live, and which can only be opened if all twenty of us come together with twenty golden keys. (We thought of using encryption, but it seemed too complicated and theoretical.)

Yes, I’d love to tell you about it, but I’d have to kill you afterwards, and then who would be left to read my blog?

Follow