Shtetl-Optimized

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

“How To Be A Serious Researcher,” my infamous after-dinner speech at QIP’2006, is now available as an mp3 (5MB, 21 minutes). If you want to tar-and-feather me for this, don’t forget Ben Toner (who made the recording) or Julia Kempe (who sent the photo).

Follow

I’ve been told that “the world is awaiting” my report about the QIP’2006 conference. So here it is. I’m in Paris, near the Pantheon. The buildings are beautiful, but the weather is crummy. The food is tasty, expensive, and fattening. Everyone here has been friendly, which is surprising — considering that I’m conspicuously American, and that my French consists almost entirely of the following phrases:

Bonjour!
Merci!
Oui!
Je ne comprends pas!
Monsieur
Madame
École Polytechnique
Croissant
Baguette
Ravioli (no, wait — that’s Italian)

(I’m in a talk right now, using the wireless Internet, and Harry Buhrman is reading this over my shoulder and laughing. Stop that, Harry!)

Oh, right: there have also been talks here. Maybe I’ll blog about them in a later post, but then again, maybe not. I’m not giving a talk, but I am giving the after-dinner speech on Thursday, the quantum computing community having relegated me to the role of jester. Which reminds me that I should write the speech.

I should also apply for jobs for next year. Actually, would anyone like to offer me a tenure-track faculty position right now? Most of the deadlines have passed, and I haven’t even written my research statement — so if that sort of thing doesn’t bother you, your chances of getting me are excellent.

Follow

I arrived yesterday morning in Lisbon. I’m here to give a talk at the Instituto Superior Técnico, which is working to build up a quantum information group. On Saturday I leave for QIP’2006 in Paris, then for New York City, before returning to Waterloo. Academia is not an easy life, but I try to bear it like a soldier.

Lisbon is beautiful: sort of like San Francisco, except more so. Yesterday I hiked up to the Castelo de São Jorge, a 100% genuine castle (with turrets, a moat, etc.) that overlooks the city from a hilltop. I took lots of photos, but then lost the cable with which to upload them to my computer. Sorry!

As my host, Yasser Omar, explained to me, Portugal “missed half of the 20th century”: specifically the years 1932-1974, when it was run by a backwards dictatorship. Even today, a tradition of bureaucratic incompetence lingers on. Yasser said that when he was looking for a tenure-track physics job, he could find only one opening in the whole country — and that one was only for “geophysics or the history of physics”! (He now works in a math department.) He and like-minded academics are now doing their best to help Portugal make up for the lost time.

PS. For those Shtetl-Optimized readers who don’t know a shtetl from schmaltz (and it’s come to my attention that such exist): King Manuel I of Portugal expelled the Jews in 1497, five years after Ferdinand and Isabella expelled them from Spain. Apparently, King Manuel realized that this would devastate Portugal’s economy, so he only signed the order reluctantly, after Princess Isabel of Spain demanded he do it as a precondition of marriage (!). Portugal started readmitting Jews in the 1800’s, and eventually became a transit point for over 100,000 refugees from the Nazis. You can read more here.

Follow

I arrived Friday morning in an exotic, faraway “Backwards-Land,” where mammals have pouches, vegemite is considered edible, toilets should in principle flush the wrong way, and Christmas trees adorn a tropical summer landscape.

I’m here to visit the University of Queensland physics department, which is probably best known as the home of the world’s longest-running experiment: a glob of congealed black tar that’s been dripping through a funnel since 1927, at the rate of about one drop per decade. This important experiment recently won an Ig Nobel Prize in Physics, causing my colleague the Quantum Pontiff to regret not taking a photo of it while he had the chance. In perhaps the greatest advance in Catholic-Jewish relations since John Paul II prayed at the Western Wall, today Shtetl-Optimized proudly presents His Quantum Holiness with the following token of goodwill.

But there’s more to Australia than funnels of congealed black tar. There are also strange and wonderful birds with that wander around the campus eating people’s garbage. Birdwatching is not a pastime I’ve ever wished on anyone, but I think this one is an Australian White Ibis:

Finally, Australia is also home to terrible race riots, which erupted yesterday after a Lebanese gang apparently attacked two white lifeguards. I don’t have anything amusing to say about that.

Follow

Yesterday I visited the Wren Library, which houses many of Newton’s old books. Notably, they have a first edition of Principia Mathematica, with Newton’s handwritten corrections for the second edition. So what did Ike see fit to correct? Well, the title page of the first edition listed him as a Fellow of the Royal Society. Sir Isaac crossed that out: he was now the President of the Royal Society! As Jonathan Oppenheim pointed out to me, it’s weirdly reassuring to see a guy at the vertiginous top of the academic ladder, grasping in vain for the nonexistent rung above.

Follow