Shtetl-Optimized

A reader from Istanbul wrote in, asking me to comment on the war in Israel and Lebanon. In other words, he wants me to make this blog the scene of yet another intellectual bloodbath, with insult-laden rockets launched from untraceable IP addresses and complexity-theoretic civilians trapped in the crossfire. What a neat idea! Why didn’t I think of it before?

Alright, let me start with some context. No, I’m not talking about the Gaza pullout, or Camp David, or the last Lebanon invasion, or the Yom Kippur War, or the Six-Day War, or the War of Independence, or the UN partition plan, or the 1939 White Paper. I’m talking about the first appearance of Israel in the extrabiblical historical record, which seems to have been around 1200 BC. Boasting in a victory stele about his recent military conquests in Canaan, the Egyptian pharaoh Merneptah included a single sentence about Israel:

Israel is laid waste; his seed is destroyed.

Sure, the pharoah was a bit premature. But give him credit for prescience if not for accuracy. Unlike (say) pyramid-building or Ra-worship, Merneptah’s Jew-killing idea has remained consistently popular for 3.2 millennia.

Today, in the year 2006, as the LHC prepares to find the Higgs boson and the New Horizons probe heads to Pluto, Am Yisra’el (literally, “the people that argues with God”) is once again surrounded by enemies whose stated goal is to wipe it off the face of the Earth. And, in the familiar process of fighting for its existence, that people is grievously, inexplicably, incompetently, blowing up six-year-olds and farmers while failing to make any visible progress on its military objectives.

So what is there to say about this that hasn’t already been said Ackermann(50) times? Instead of cluttering the blogosphere any further, I’ll simply point you to a beautiful New York Times op-ed by Rebecca Goldstein, commemorating the 350^th anniversary of Spinoza’s excommunication from the Jewish community of Amsterdam. Actually, I’ll quote a few passages:

Spinoza’s reaction to the religious intolerance he saw around him was to try to think his way out of all sectarian thinking. He understood the powerful tendency in each of us toward developing a view of the truth that favors the circumstances into which we happened to have been born. Self-aggrandizement can be the invisible scaffolding of religion, politics or ideology.

Against this tendency we have no defense but the relentless application of reason.

Spinoza’s system is a long deductive argument for a conclusion as radical in our day as it was in his, namely that to the extent that we are rational, we each partake in exactly the same identity.

Spinoza’s dream of making us susceptible to the voice of reason might seem hopelessly quixotic at this moment, with religion-infested politics on the march. But imagine how much more impossible a dream it would have seemed on that day 350 years ago.

Follow

A commenter on a previous post writes:

A lot of great discoveries came from non-scientific losers. E=MCC. Airplanes. America. Someone discovered how to make an airplane by playing with a box. Physics is mostly theoretical. America, I guess, is the most scientific discovery. They applied the scientific method to determine its existence, but they used no control group, and no placebo. For that, America’s existence is not yet proven. There seem to be other ways of establishing truth than just the scientific method. Scientists are contemporary soothsayers. They should use every means possible of proving a fact.

Despite its insightfulness and coherence, the above argument raises some immediate questions:

1. What does it have to do with anything I said?
2. E=MCC?
3. What would mean to use a placebo or control group to test America’s existence? Would it mean sending a ship in a different direction, and checking that it didn’t also reach America? Would it mean verifying that America can’t be reached from Europe by foot — since if it could, then it wouldn’t be America, but rather part of Eurasia?
4. Has England’s existence been scientifically proven? What about France’s?
5. Where do so many people get the cockamamie idea that there’s such a thing as a “scientific method” — that science is not just really, really, really careful thinking? (I blame the school system.)

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

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