Shtetl-Optimized

Get a leg up on the competition, and offer me a tenure-track position in computer science right now! Here’s everything you’ll need to decide:

• Research Statement [PS] [PDF]
• Teaching Statement [PS] [PDF]
• CV [PS] [PDF]

In your offer letter, make sure to specify starting salary, teaching load, and the number of dimensions you’d like spacetime to have.

(Note to Luboš: Unfortunately, I wasn’t planning to apply to the Harvard physics department this year. But if you make a really convincing pitch, I might just be persuaded…)

Follow

Hearty, nontrivial Christmas greetings from SAT-a-Clause, the patron saint of theoretical computer scientists! Tomorrow night, SAT-a-Clause will once again descend all possible chimneys in parallel, nondeterministically guess which ones lead to cookies, and fill the corresponding “STOC-ings” with loads of publishable results!

As I’ve done every year since I was about 14, I’ll spend Christmas Eve at my best friend Alex’s house (this year bringing the girlfriend along). My role at Alex’s family gathering, of course, is to wage the secular-humanist War On Christmas: sanctimoniously insisting that guests say “Happy Holidays” instead of “Merry Christmas,” belching loudly during hymns and carols, mocking the Savior as a “competent if unoriginal 1^st-century rabbi,” and just generally dampening Christian faith, fomenting impiety, and advancing the cause of Satan. After all, what Christmas Eve celebration would be complete without a JudeoGrinch?

If your idea of the Christmas spirit includes, you know, peace on Earth, goodwill to all mankind, etc., you should check out this New York Times essay by Peter Singer, which Luca blogged about previously. Singer strikes me as one of the few public intellectuals who’s actually gotten wiser with age, as opposed to yet more cranky and intransigent. In this latest piece, he shows himself to be less concerned with chicken liberation than with eradicating rotavirus and malaria, less interested in the Talmudic question of whether a billionaire who’s given away 90% of his wealth is now morally obligated to give away the rest than in the practical question of how to get people to give more. I also recommend this column from last Christmas season by Nicholas Kristof — a writer who’s occassionally mistaken, never less than a mensch — in which he compares the War on Christmas to the war in Darfur, and challenges Bill O’Reilly to join him in witnessing the latter.

Follow

My sojourn in Northern California is now at an end; on Sunday I flew to my parents’ place near Philadelphia for Hanukhrismanewyears. But not before going to Stanford to give a talk to their string theory group about “Computational Complexity and the Anthropic Principle.” Here are the notes from that talk; you can think of them as a Quantum Computing Since Democritus Special Bonus Lecture.

(The best part of the talk — the lengthy arguments with Lenny Susskind, Andrei Linde, and the other stringers and cosmologists, in which I repeatedly used humor to mask my utter lack of understanding — is sadly lost to eternity. Fortunately, I’m sure that new such arguments will erupt in the comments section.)

In preparation for meeting Susskind and the other Stanford stringers, I made sure to brush up on both sides of the String Wars. On the anti-string side, I read Peter Woit’s Not Even Wrong and Lee Smolin’s The Trouble With Physics. On the pro-string side, I read Susskind’s The Cosmic Landscape and also spent hours talking with Greg Kuperberg, who tried to convince me that critics of string theory are as “intellectually non-serious” as quantum computing skeptics or Ralph Nader voters. I heartily recommend all three of the books.

So, what did I learn at Stanford? Among other things, that when you talk to string theorists in person, they’re much more open-minded and reasonable than you’d expect! Of course, when your de facto spokesman is the self-parodying Luboš Motl — who often manages to excoriate feminists, climatologists, and loop quantum gravity theorists in the very same sentence — it’s hard not to seem reasonable by comparison. But I’m not even talking about him.

(Conflict-of-interest warning: I’m painfully well aware that, so long as Luboš is around, I can only ever be the second-funniest physics blogger — even if the world champion in this field isn’t trying to be funny.)

In general, I’ve found that tolerance for alternative ideas, willingness to engage with counterarguments, rejection of appeals to authority, and so on are all greater when talking to string theorists in person than when attending their talks or reading their books and articles. Maybe that’s to be expected — to some extent it’s true of every field! But with string theorists, the magnitude of the difference always astonishes me.

Alright, let me get more concrete. One of the few nontrivial points of agreement between string theory and loop quantum gravity seems to be that, in any bounded region of spacetime, the number of bits of information is finite: at most ~10⁶⁹ bits per square meter of surface area, or (equivalently) at most ~1 bit per Planck area. In loop quantum gravity, this is basically because one bit of information is “stored” in each Planck area. In string theory, it’s much more subtle than that: the bits of information can’t be put into any sort of one-to-one correspondence with the Planck areas on the horizon, but they both add up to the same number. (Ignoring a factor of 4, which being a complexity theorist, I don’t care about.)

Now, much of my conversation with Susskind and fellow string theorist Steve Shenker focused on the following question: isn’t it a bizarre coincidence that the Planck areas and the bits of information should both add up to the same number, if there’s no “dual” description of string theory in which each bit (or rather qubit) is stored in a Planck area? Susskind agreed with me that such a “local” description of string theory (local on the boundary, not in the bulk) would be desirable — and that, if there isn’t such a description, then that by itself is a fundamental fact worthy of more attention. I’d expected Susskind and Shenker to brush aside my question as idle pontificating; instead, they seemed to want to reinvent string theory that very afternoon so that my question would have an answer!

When it became clear that no such reinvention of the theory was forthcoming (at least that afternoon), I suggested the following. We’ve got this one proposal, string theory, which has had some spectacular technical successes (like “explaining” the Bekenstein-Hawking entropy), but which, setting aside its other well-known problems, offers no “local” description of spacetime in terms of qubits and quantum circuits at the Planck scale. Then we’ve got this other proposal, loop quantum gravity, which has had fewer successes, but which does attempt such a local description at the Planck scale. So, if we agree that such a local description is our eventual goal, then shouldn’t an outsider guess that string theory and loop quantum gravity are probably just different footprints of the same beast — much like the different string theories themselves were found to be different limiting cases of an as-yet-unknown M-theory?

Susskind agreed that such a convergence — between the “top-down” picture of string theory, which grew out of conventional high-energy physics, and a “bottom-up” picture in terms of qubits at the Planck scale — was possible or even likely. He stressed that his opposition was not to the idea of describing spacetime in terms of local interactions of qubits, but rather to the specific technical program of loop quantum gravity, and to the exaggerated claims often made on that program’s behalf. When I reminded him that other people complain about exaggerated claims made on string theory’s behalf, he replied that the two cases were not even remotely comparable.

All in all, it was an extremely productive and enjoyable visit — one in which the conversation topics ranged over (among other things) the explanatory role of the Anthropic Principle, the possibility that the entire universe arose as a quantum fluctuation, the prospects for an efficient quantum algorithm for Graph Isomorphism, the relation between thermodynamics and quantum error-correction, and whether or not Gerard ‘t Hooft actually disbelieves quantum mechanics. Susskind told me, half-jokingly, that the Stanford string theory group was the world’s hotbed of anti-Landscape sentiment, and the arguments that I saw and participated in on my visit gave me no reason to doubt him.

So what are we to make of the fact that, on the one hand, the string theorists are such swell folks in person, and on the other hand, even the most cursory glance at their writings will reveal that the charge of triumphalist arrogance is far from undeserved? Well, to the anti-stringers, the obvious interpretation will be that the string theorists don’t really believe their own pablum: that they say one thing in public and a completely different thing in private. To the pro-stringers, the obvious interpretation will be that, beneath the façade we all erect around ourselves, the string theorists are just scientists like anyone else: grasping at the truth, struggling to learn more, convinced that string theory is the best idea we have but ready to ditch it if something better comes along. As usual, it all depends on where you’re coming from.

Alas, as tidy as this resolution sounds, it doesn’t help me pick sides in the String Wars currently raging through the blogosphere. But then again, why do I need to pick sides? I like hanging out with the loop quantum gravity people at Perimeter Institute. I like the fact that Lee Smolin’s publisher sent me a free review copy of The Trouble With Physics. I like the recent paper by Denef and Douglas on computational complexity and the string Landscape. And I like getting an all-expenses-paid trip to Stanford to have a freewheeling, day-long intellectual conversation with the string theorists there.

I have therefore reached a decision. From this day forward, my allegiances in the String Wars will be open for sale to the highest bidder. Like a cynical arms merchant, I will offer my computational-complexity and humor services to both sides, and publicly espouse the views of whichever side seems more interested in buying them at the moment. Fly me to an exotic enough location, put me up in a swank enough hotel, and the number of spacetime dimensions can be anything you want it to be: 4, 10, 11, or even 172.9+3πi. Is it more important for a quantum gravity theory to connect to the Standard Model, or to build in background-independence from the outset? Can one use the Anthropic Principle to make falsifiable predictions? How much is riding on whether or not the LHC finds supersymmetry? I might have opinions on these topics, but they’re nothing that a cushy job offer or a suitcase full of “reimbursements” couldn’t change.

Someday, perhaps, a dramatic new experimental finding or theoretical breakthrough will change the situation vis-à-vis string theory and its competitors. Until then, I shall answer to no quantum-gravity research program, but rather seek to profit from them all.

Update (12/23): The indefatigable Luboš Motl has put up a new jeremiad against me. Taking my ‘For Sale’ announcement completely seriously, Luboš writes:

It is absolutely impossible for me to hide how intensely I despise people like Scott Aaronson … He’s the ultimate example of a complete moral breakdown of a scientist. It is astonishing that the situation became so bad that the people are not only corrupt and dishonest but they proudly announce this fact on their blogs…

In fact, I have learned that the situation is so bad that when I simply state that Aaronson’s attitude is flagrantly incompatible with the ethical standards of a scholar as they have been understood for centuries, there could be some parts of the official establishment that would support him against me. There doesn’t seem to be a single blog article besides mine that denounces Aaronson’s attitude…

The difference between [the] two of us is like the difference between a superman from the action movies who fights for the universal justice on one side and the most dirty corrupt villain on the other side. It’s like the Heaven and the Hell, freedom and feminism, careful evaluation of the climate and the alarmist hysteria, or string theory and loop quantum gravity…

I can’t tell you how proud I am to have become “the most dirty corrupt villain” in Luboš’s cosmology, and no longer just an anonymous bystander. Thanks so much, Luboš, and Merry Christmas to you too!

Update (12/24): Man oh man, I had no idea that people would take my offer so seriously! Because of this, I now feel obligated to provide a financial disclosure statement. The Stanford string theorists did not actually pay my way to California, although they offered to — most of my expenses were covered by Umesh, my adviser at Berkeley. Stanford paid for (1) one night’s hotel stay in Palo Alto, and (2) one lunch, consisting of a small cheese pizza and an iced tea.

Follow

Yes, less than a week after the course itself finished, a new set of lecture notes is finally here! The topic: randomness.

I’m writing this post from über-commenter Greg Kuperberg’s office at UC Davis, where I’m visiting for a few days to give a math colloquium. Greg has been trying to fill my thick skull with something called “t-cubature formulas,” and writing this post provides me with a much-needed break!

After Davis, I’ll be going to Berkeley for a couple weeks (not that I ever really left it), then my parents’ place in Pennsylvania for the holidays, then Caltech, then New Zealand (why the hell not?), then Australia for QIP, then back to Waterloo in February. Much more relaxing than last year’s trip — note that I won’t return from this one with an (additional) 2πi phase.

Follow

Of course, the greatest scientific flame war of all time was the calculus priority dispute between Isaac Newton and Gottfried Wilhelm Leibniz. This one had everything: intrigue, pettiness, hypocrisy, nationalism, and even hints of the physicist vs. computer scientist split that continues to this day.

In our opening talk at QIPC’2006 in London, Dave Bacon and I decided to relive the hatred — with Dave in a frilly white wig playing the part of Newton, and your humble blogger in a frilly black wig playing the part of Leibniz. We forgot to take photos, but here’s the script, and here are the slides for the … err, “serious” talk that Dave and I gave after dewigging.

Update (thanks to Dave and Viv Kendon):

Follow

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