Shtetl-Optimized

Picture this: it’s my first visit to Cambridge — Ground Zero of the scientific revolution, a place that’s probably contributed more to human knowledge than any other on Earth. Within walking distance are the original manuscripts of Newton’s Principia; the halls where Darwin, Maxwell, and Russell dined as undergraduates; the Cavendish Laboratory where Rutherford bombarded nuclei and Crick and Watson unravelled nucleic acids; and architecture dating back to the 1200’s, much of it among the finest in Europe. I ought to be taking in the splendor (sorry, “splendour”) by day, and blogging about it by night.

So where have I been? Hunkered in an office, trying to finish a paper with Greg Kuperberg about QMA versus QCMA in time for the Complexity’06 submission deadline. Happily, by Saturday it had become obvious that, try though we might, we weren’t gonna make it. So I put it off till the next conference, and contented myself with submitting two papers to this year’s Complexity conference instead of three. As Douglas Adams, another Cambridge alum, put it: “I love deadlines. I like the whooshing sound they make as they fly by.”

So what can I tell you about Cambridge? First of all, when people refer to the various “colleges” — King’s, Trinity, and so on — they’re not just being eccentric and British. These colleges actually exist. Each one is basically a walled-off compound, with a few grand-looking entrances that get locked at night, thereby making Cambridge even harder to navigate than the average campus. (It doesn’t help that the streets change names constantly: St. John’s becomes Trinity becomes King’s Parade becomes Trumpington Street within a couple of blocks.)

I’m staying at King’s, pictured below:

Last week my host at King’s, Artur Ekert, invited me to High Table. For you non-Oxbridge doofuses, “High Table” is a fancy dinner at which people still wear robes, non-ironically as far as I could tell. Or rather, Fellows must wear robes when dining at their own college, though not when dining at a different college. (Makes sense, huh?) Afterwards, the Fellows and their guests retire to another room for wine, cheese, and academic gossip.

All these dining rooms are lined with portraits of illustrious King’s alumni from centuries past — but amazingly, there’s still no portrait of the greatest King’s man of all time. Who was it? Let me give you a few hints. He proved the unsolvability of the Entscheidungsproblem. He was “queer” in more than one way. He had a Machine and a Test named after him. He may have played a bigger role than Churchill in winning the Second World War.

To his great credit, Artur told me that he almost threatened to resign his Fellowship if no portrait of Alan Mathison Turing F.R.S. was hung in the halls. The relevant authorities have promised to rectify the situation, though they haven’t done so yet. (Admittedly, the computer help center at King’s is called the “Turing Centre.” One imagines Turing’s ghost managing the DHCP servers, so that the real scholars can get on with their work.)

To my mind, the central question is this: did Cambridge become the world’s scientific superpower for 300 years in spite of all this idiosyncratic formality, or because of it? I have mixed feelings. On the one hand, the amount of red tape here, and the importance attached to one’s status, is like something out of Victorian England (oh, wait…). Fellows and their guests are allowed to walk on the grass; all others are not. Even though there’s an ethernet jack right in my room, I wasn’t allowed to use it, being merely a visitor. (After I complained, Artur was kind enough to give me his IP address.)

On the other hand, I like High Table and similar traditions. I like how they acknowledge and celebrate something that’s always been obvious to me: that being an academic isn’t a job like other jobs, but a way of life. This doesn’t necessarily mean that academics have no lives; what it means is that they don’t distinguish between work and life the way most people do.

Have you ever been to one of those roadside diners where you can pick an entree plus two sides, but a few of the entrees are marked “complete,” meaning you don’t get any sides with them? Well, at Cambridge they’ve understood for centuries that academia is one of life’s complete entrees. Not that a Cambridge man would know anything about roadside diners.

Follow

Happy Thanksgiving to my American readers! I arrived last night at my parents’ place in Pennsylvania. After I’ve digested enough to walk again, I’m off to Cambridge (the England one), then Brisbane, Australia, then back to America before Christmas Eve (which I do celebrate, with Alex Halderman’s family).

For all the academic traveling I’ve done, this will be my first time circumnavigating the globe. I can’t wait to find out whether it’s really round, or whether thar’ be dragons at the end.

Yet wherever I go, I’ll always be an American. In Toronto’s Pearson airport, I came across a Maclean’s (roughly, Canada’s Time or Newsweek), whose cover depicted a smirking Bush holding a glass of water. The headline (which I’m not making up):

America is thirsty
Let’s sell them our water before they take it

Sure, we might be chipping away at that “land of the free” part, but we’re still the home of the brave.

Follow

Over at Freedom to Tinker, Alex Halderman and his adviser Ed Felten have been causing headaches for SunnComm, the makers of broken technology designed to prevent the copying of music CD’s. Alex is the Princeton graduate student who enjoyed worldwide media attention two years ago, when he showed that SunnComm’s “MediaMax” anti-copying software could be disabled by holding down the “Shift” key while inserting a CD into your computer. Alex’s paper about this was downloaded over a hundred thousand times, and caused SunnComm’s stock to lose $10,000,000 in a week. By comparison, my paper Quantum Lower Bound for Recursive Fourier Sampling has (I think) been downloaded at least twice, and would have driven Recursive Fourier Sampling In 2^o(h) Queries Incorporated out of business, had it existed.

Now Alex and Ed are reporting that SunnComm has continued to “innovate.” It seems that the latest version of MediaMax, which is included with several Sony/BMG music CD’s,

1. secretly installs itself even before you accept the End User License Agreement,
2. remains installed even if you decline the agreement, and
3. secretly “phones home” to SunnComm with information about your activities, despite assurances to the contrary.

Alex and I met in seventh grade at Newtown Junior High School. I had just transferred from a parochial school, and was so low in the social hierarchy that, when kids beat me up, I was grateful for the attention. My one consolation was that, out of all the kids in the school, I — and I alone — knew that dx³/dx=3x² and that t’=t/√(1-(v/c)²). Most importantly, I alone knew how to program in GW-BASIC.

So you can imagine the existential shock when I heard there was another kid in seventh grade who was already writing Windows applications and marketing them as shareware. Clearly I had to meet this guy, see if he was for real. After I found out that he was — and repaired the gaping holes in my ego — Alex and I became best friends. We remain so twelve years later.

Even in junior high, Alex was obsessed with security issues: his bestselling program, if I remember correctly, was an encryption utility. At the same time, he was obviously a “white hat.” Rather than getting himself into trouble by hacking the school computers, he’d simply make the teachers utterly reliant on his expertise, then ask them for administrator privileges.

One day in the cafeteria, Alex excitedly brought me a book he was reading, which described a bizarre-sounding encryption system called “RSA.” Supposedly, with this system you could send someone secret messages without ever having met them to agree on a key.

“But that’s obviously impossible,” I explained. I was proud that, for once, I could use my superior mathematical knowledge to set Alex straight.

Eventually Alex and I both ended up in academic computer science, albeit on opposite sides of it. Perhaps the difference between us is best summarized as follows. For Alex, the impossibility of making digital information copy-proof is a central truth of our age: something to be explained, and then re-explained, to judges, reporters, and businesspeople, in amicus curiae briefs and interviews on NPR. For me, it follows from the fact that the set of n-bit strings constitutes an orthogonal basis for Hilbert space.

Follow

Everyone knows that if you have a cold, the most important thing (besides chicken soup) is to get plenty of sleep. Sleep is when your white blood cells stop reading The Onion and watching Simpsons reruns, and start snacking on viruses.

But what if your cold is so severe that you can’t sleep, not even for an hour or two? What do you do then? Not knowing the answer — but knowing readers of your blog will be getting increasingly antsy — you go see a doctor. The doctor says to take NyQuil to sleep.

The problem is that NyQuil tastes worse than Vegemite, and (another Catch-22) you can barely force a drop of it down your swollen throat. So you mix a Coke and NyQuil, on the rocks. But this merely converts a small disgusting green beverage into a large disgusting greenish-brown one.

So you go back to the drugstore, where you’re relieved to learn that NyQuil is also sold in capsule form. You take two capsules. Hours later, you’re still not asleep. So you take a third. An hour later you’re still not asleep, and your throat is in indescribable pain. So you take two Advils. The pain doesn’t go away, so you take a third Advil.

At this point you start hallucinating and feeling dizzy. Your skin is pale, your pupils are dilated, and you’re sweating profusely. Uh-oh. What was in those pills, anyway? In each NyQuil: Dextromethorphan HBr 15mg, Pseudoephedrine HCl 30mg, Acetaminophen 325mg, Doxylamine succinate 6.25mg. In each Advil Cold & Sinus: Ibuprofen 200mg, Pseudoephedrine HCl 30mg. So, you’ve now ingested 180mg of Pseudoephedrine HCl, whatever the hell that is.

“In case of accidental overdose contact a physician or poison control centre immediately, even if there are no symptoms.”

Staggering over to your computer, you read that overdosing on antihistamines and decongestants can be fatal, and that indeed, the proper thing to do would be to get your stomach pumped as soon as possible. But it’s 4AM, and for better or worse, you decide to leave the 9-1-1 operator alone, and trust that three billion years of Darwinian natural selection weren’t for bleaaaarrrrrgghhhhhhhhh…

The Moral: Never assume that, just because a single dose of a drug doesn’t help you, a double or triple dose isn’t going to kill you.

It actually gets even more nauseating, but I’ll cut to the end: after more than a week, I can eat again. I can blog again. I can lower-bound again. I can even talk again, though I won’t be playing female leads in Broadway musicals anytime soon.

It’s good to be back.

Follow

I’m bedridden with a sore throat, and on enough painkillers to knock out an elephant (well, a very small elephant). I assume the String Theory God is punishing me. I’ve been repenting to all five of His manifestations — Type I, Type IIA, Type IIB, Heterotic SO(32), and Heterotic E₈xE₈ — and hopefully I’ll be back in a couple days. Happy Halloween.

Follow

Sorry for the inordinate delay in updating! This weekend I was busy with several things, one of which was “EinsteinFest,” Perimeter Institute’s celebration of the hundred-year anniversary of Einstein’s annus mirabilis. The Fest is a monthlong program of exhibits, talks, etc., aimed at the general public, and covering four topics: “The Science, The Times, The Man, The Legacy.” This weekend’s talks were about “The Man,” which is why I attended.

See, I was worried that the Fest would place too much emphasis on Einstein the sockless symbol of scientific progress, Einstein the secular saint, Einstein the posthumous salesman for Perimeter Institute. And how it could do that without indulging in the very pomposity that Einstein himself detested?

My fears were not assuaged by the many exhibits devoted to Freud, Picasso, the Wright Brothers, the automobile, fashion at the turn of the century, and so on. These exhibits gave visitors the impression of a great band of innovators marching into the future, with Einstein cheerfully in front. The reality, of course, is that Einstein never marched in anyone’s band, and — like his friend Gödel — saw himself as opposed to the main intellectual currents of the time.

It didn’t help either that, to handle the influx of visitors, Perimeter has basically transformed itself into Relativistic Disney World — complete with tickets, long lines, guides wearing uniforms, signs directing traffic, cordoned-off areas, and an outdoor tent for kids called “Physica Fantastica.” To some extent I guess this was unavoidable, although sometimes it resulted in unintended comedy:

(Sorry, I just bought a digital camera and couldn’t resist.)

So it was a pleasure to attend the talks on “Einstein the Man” and find that, in spite of everything, they were fantastic. We heard David Rowe on Einstein and politics, Trevor Lipscombe on Einstein and Mileva, and John Dawson on Einstein and Gödel. Partly these speakers won me over with wisecracks (Dawson: “Gödel thought he’d found a flaw in the Constitution, by which the US could legally turn into a dictatorship. In light of recent events, I don’t see why anyone would doubt him”). But mostly they just let the old man speak for himself. We saw Einstein write the following to his then-mistress Elsa:

If you were to recite the most beautiful poem ever so divinely, the joy I would derive from it would not come close to the joy I experienced when I received the mushrooms and goose cracklings you cooked.

And to Mileva, during the months when he was finishing general relativity:

You will see to it: (1) that my clothes and linen are kept in order; (2) that I am served three regular meals a day in my room; (3) that my bedroom and study are always kept in good order and that my desk is not touched by anyone other than me.

We saw Einstein the pacifist urging the Allies to rearm at once against Hitler, and Einstein the secular internationalist supporting the creation of Israel. And eventually we came to understand that this was not an oracle spouting wisdom from God; it was just a guy with a great deal of common sense — as much common sense as anyone’s ever had. Isn’t it strange that, despite deserving to be celebrated, he is?

Follow

On Friday, I drove to the University of Toronto to give a talk. This was the first time I’d ever driven on a freeway alone. I didn’t drive at all until a year ago, for four reasons:

1. Global warming. I assuaged my conscience by buying a Prius (though admittedly, given the waiting lists for hybrids, I’m probably increasing CO2 concentrations by preventing someone who drives more than I do from having my car).
2. Fear of getting lost. The solution to this one was “Carla,” my sultry female computerized travel companion (“Proceed on the current route for 0.3 miles”). I realize that for some guys, Carla would feel like a direct assault on their virility — especially since she’s always right. But I love her, and I predict that in five years’ time, everyone else will want her too.
3. Lack of any social life that would necessitate a car. I’ve since realized that this was as much a symptom as a cause of my carlessness.
4. Fear of dying a gruesome death. I haven’t yet licked this one, as became evident on Friday.

To avoid the traffic, I left Waterloo at 5:30am (yes, I’d been up all night). Unfortunately, that’s when all the trucks were out, and trucks on a freeway make me nervous. See, the problem with freeways is that there are no red lights — and therefore, no time to hunt down the neurons firing off about Futurama or BQP/qpoly, and refocus their attention on the road. It’s like having to play Super Mario all the way through without pausing — the differences being that there are no stars or mushrooms, you only get one life, and it’s your actual life. (Also, you can’t stomp on the goombas, since they’re people too.)

So when I finally pulled into the parking garage at U of T, palms white and sweaty on the steering wheel, I started laughing hysterically: “I made it! I’m still alive! At least in this branch of the wavefunction, I’m alive! Joy to the world!” That I hadn’t yet written the talk that I was to give in two hours seemed utterly insignificant.

For the ride home, I asked Carla to find me a route that avoided freeways, and ended up zigzagging through the small towns of southeast Ontario. The stoplights looked as pretty as the setting sun.

Follow