Shtetl-Optimized

• 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

So, my Best Anthropicism Contest elicited almost 50 submissions. Thanks so much to everyone who entered — if not for you, this tautological tug-of-war would’ve been something other than what it was!

To choose the winning entry, the first rule I adopted was that, when I did find the winning entry, conditions would have to be such as to make it the winning entry, since otherwise it wouldn’t be the winning entry in the first place, but rather a losing entry. Since that didn’t get me very far, I quickly fell back on other criteria.

First, the winning entry would have to be short — longwinded explanations were out right away.

Second, it would have to make sense.

Third, it would have to illustrate the anthropic principle specifically, not some sort of generic Zen wisdom.

That already killed most of the entries. Among the ones left, many dealt Hofstadterifically with the contest itself:

wolfgang: Applying the principle of mediocrity I have to conclude that it is unlikely that I will win this contest.

Matt Wedel: Oh, c’mon! Just give me the prize! If I wasn’t going to win, I’d be living in a different universe where I didn’t win. BUT — I’m not. So give me the prize.

MX: Why am I entering this contest? Because if I weren’t, I wouldn’t be me, I would be a being very similar to me living in a universe in which I did not enter this contest.

Other entries worked well as parody:

sockatume: How much wood could a woodchuck chuck if a woodchuck could chuck would? As much wood as a woodchuck could chuck if a woodchuck could chuck would, otherwise it wouldn’t be a woodchuck.

Bram Cohen: Why have all dates thus far come before January 1, 3000? Because the universe will cease to exist on that day.

In the end, though, I decided that what I was looking for wasn’t mere wit, but the real, genuine illusion of explanatory insight. And that’s why Lev R. takes the prize, with the following perspicacious pearl:

why aren’t physicists too interested in computational complexity? because if they were, they’d be computer scientists.

Follow

Back in April, I blogged about why we should all support open-access journals. But after receiving a long string of referee requests from closed-access journals, I’ve completely changed my mind about this issue. I now believe we should keep Kluwer, Elsevier, and the other publishing conglomerates rolling in dough for as long as possible, and do whatever we can to sabotage the open-access movement. Why? Because as soon as the world switches to open-access, I’ll have no choice but to start accepting referee requests again.

Follow

From these lecture notes by Harvey Friedman comes one of the best metamathematical anecdotes I’ve ever heard (and yes, I’ve heard my share). Apparently Friedman was attending a talk by the “ultra-finitist” Alexander Yessenin-Volpin, who challenged the “Platonic existence” not only of infinity, but even of large integers like 2¹⁰⁰. So Friedman raised the obvious “draw the line” objection: in the sequence 2¹,2²,…,2¹⁰⁰, which is the first integer that Yessenin-Volpin would say doesn’t exist?

Yessenin-Volpin asked Friedman to be more specific.

“Okay, then. Does 2¹ exist?”

Yessenin-Volpin quickly answered “yes.”

“What about 2²?”

After a noticeable delay: “yes.”

“2³?”

After a longer delay: “yes.”

It soon became clear that Yessenin-Volpin would answer “yes” to every question, but would take twice as long for each one as for the one before it.

Follow

A year ago, I relinquished my dictatorial control of the Complexity Zoo, accepting an offer from John Stockton to convert the Zoo into wiki format. Unfortunately, the wiki site has been down for days and shows no signs of coming back anytime soon. So for now, I’ve put the old Zoo back up at www.complexityzoo.com. I’ve learned my lesson: in times of crisis, it takes a leader with an iron fist to keep the trains running on time and the animals in their cages.

John Baez is back on the scene, with an account of his recent visit to our quantum computing group at Waterloo. Among other things, he gives a lucid explanation of how, while it’s generally impossible to keep information from leaking out of a computer, it is possible to arrange things so that the information that does leak is irrelevant to the computation. Baez links to the papers that prove this is true for quantum computing as well as classical, but complains that “most of it speaks the language of ‘error correction’ rather than thermodynamics.” Question for the audience: can the fault-tolerance theorems be reproved more physicsly? (“We now define a PHYSICAL SYSTEM called the concatenated Steane code…”)

Baez’s semi-conversion to the Church of Knill, Laflamme, and Zurek (or the Shul of Aharonov and Ben-Or) has inspired me to propose a far-reaching hypothesis:

While it’s generally impossible to explain computer science concepts to physicists so that they understand them on your terms, it is sometimes possible to explain them so that they understand on their terms.

Naturally, it helps if the physicist in question is Baez.

Follow

I arrived this morning in Prague for the 2006 Complexity conference. Soon I’ll have the photos to prove it. For now, though, I wish to blog neither about the breathtakingly beautiful city in which I find myself, nor about the meaty, succulent topic alluded to in my previous post, but instead about anthropicisms.

Inspired by Peter Woit’s almost-daily anti-anthropic broadsides, and in the spirit of my earlier Best Umeshism Contest, I hereby announce a new contest for Best Application of the Anthropic Principle. Here are a few samples to get the self-selected tautological ball rolling, not that it could do otherwise than roll:

Why do so many people seem to care about being remembered after they die? Because we only remember the ones who cared about being remembered.

Academics comprise only a tiny portion of humanity, so what are the chances of being an academic as opposed to someone else? Conditioned on asking such a question in the first place, pretty high.

Why is the moon round? Because if it were square, you wouldn’t be you — you would instead be a being extremely similar to you, except that he or she lives in a universe with a square moon.

Why am I a blogger? Because if I weren’t, you wouldn’t be reading this.

The rules are similar to the Best Umeshism Contest: up to three entries per person. Please include a name — despite the nature of the contest, “He Who Posted This” doesn’t count. Entries must be in by July 22nd. The winner (as chosen by me) gets to ask any question and have me answer it here.

Follow

I’m convinced that the following diagram means something precise:

My question is, what does it mean?

Intuitively, it means that if your software package can solve SDP’s, then you can easily use it to solve LP’s; if it can solve LP’s, you can easily use it to invert matrices, and so on, but not vice versa. But it can’t mean (for example) that SDP’s are harder than LP’s in the usual complexity theory sense, since both problems are P-complete!

Maybe it means that, if your axiom system is strong enough to prove SDP is in P, then it’s also strong enough to prove LP is in P, and so on — but not necessarily vice versa. But how would we show such a separation?

(Sorry, no money this time. We’ll see if it makes any difference — I’m guessing that it doesn’t.)

Follow

This, I’m embarrassed to admit, is something I’ve asked myself at various points over the last ten years. Fortunately, thanks to this thread on Lance Fortnow’s blog, I now have my answer: no.

Follow