Shtetl-Optimized

Yesterday’s Times ran an essay by Steve Lohr, based on speeches about the future of computing given by my former teachers Richard Karp and Jon Kleinberg. Though most of the essay is welcome and unobjectionable, let’s look at the first two paragraphs:

Computer science is not only a comparatively young field, but also one that has had to prove it is really science. Skeptics in academia would often say that after Alan Turing described the concept of the “universal machine” in the late 1930’s — the idea that a computer in theory could be made to do the work of any kind of calculating machine, including the human brain — all that remained to be done was mere engineering.

The more generous perspective today is that decades of stunningly rapid advances in processing speed, storage and networking, along with the development of increasingly clever software, have brought computing into science, business and culture in ways that were barely imagined years ago. The quantitative changes delivered through smart engineering opened the door to qualitative changes.

So, here are the two options on offer from the paper of record: either

1. computer science was finished off by Alan Turing, or
2. “stunningly rapid advances in processing speed, storage and networking” have reopened it just recently.

Even among the commenters on this post by Chad Orzel — which Dave Bacon forwarded to me with the subject line “bait” — awareness of any third possibility seems depressingly rare. Judging from the evidence, it’s not that people have engaged the mysteries of P versus NP, randomness and determinism, one-way functions and interactive proofs, and found them insufficiently deep. Rather, as bizarre as it sounds, it’s that people don’t know these mysteries exist — just as they wouldn’t know about black holes or the Big Bang if no one told them. If you want to understand why our subject — which by any objective standard, has contributed at least as much over the last 30 years as (say) particle physics or cosmology to humankind’s basic picture of the universe — receives a whopping $5 million a year from the NSF (with even that in constant danger), look no further.

Follow

Time again for Shtetl-Optimized’s Mistake of the Week series! This week my inspiration comes from a paper that’s been heating up the quantum blogosphere (the Blochosphere?): Is Fault-Tolerant Quantum Computation Really Possible? by M. I. Dyakonov. I’ll start by quoting my favorite passages:

The enormous literature devoted to this subject (Google gives 29300 hits for “fault-tolerant quantum computation”) is purely mathematical. It is mostly produced by computer scientists with a limited understanding of physics and a somewhat restricted perception of quantum mechanics as nothing more than unitary transformations in Hilbert space plus “entanglement.”

Whenever there is a complicated issue, whether in many-particle physics, climatology, or economics, one can be almost certain that no theorem will be applicable and/or relevant, because the explicit or implicit assumptions, on which it is based, will never hold in reality.

I’ll leave the detailed critique of Dyakonov’s paper to John Preskill, the Pontiff, and other “computer scientists” who understand the fault-tolerance theorem much better than a mere physicist like me. Here I instead want to take issue with an idea that surfaces again and again in Dyakonov’s paper, is almost universally accepted, but is nevertheless false. The idea is this: that it’s possible for a theory to “work on paper but not in the real world.”

The proponents of this idea go wrong, not in thinking that a theory can fail in the real world, but in thinking that if it fails, then the theory can still “work on paper.” If a theory claims to describe a phenomenon but doesn’t, then the theory doesn’t work, period — neither in the real world nor on paper. In my view, the refrain that something “works on paper but not in the real world” serves mainly as an intellectual crutch: a way for the lazy to voice their opinion that something feels wrong to them, without having to explain how or where it’s wrong.

“Ah,” you say, “but theorists often make assumptions that don’t hold in the real world!” Yes, but you’re sidestepping the key question: did the theorists state their assumptions clearly or not? If they didn’t, then the fault lies with them; if they did, then the fault lies with those practitioners who would milk a nonspherical cow like a spherical one.

To kill a theory (in the absence of direct evidence), you need to pinpoint which of its assumptions are unfounded and why. You don’t become more convincing by merely finding more assumptions to criticize; on the contrary, the “hope something sticks” approach usually smacks of desperation:

There’s no proof that the Earth’s temperature is rising, but even if there was, there’s no proof that humans are causing it, but even if there was, there’s no proof that it’s anything to worry about, but even there was, there’s no proof that we can do anything about it, but even if there was, it’s all just a theory anyway!

As should be clear, “just a theory” is not a criticism: it’s a kvetch.

Marge: I really think this is a bad idea.
Homer: Marge, I agree with you — in theory. In theory, communism works. In theory.

Actually, let’s look at Homer’s example of communism, since nothing could better illustrate my point. When people say that communism works “in theory,” they presumably mean that it works if everyone is altruistic. But regulating selfishness is the whole problem political systems are supposed to solve in the first place! Any political system that defines the problem away doesn’t work on paper, any more than “Call a SAT oracle” works on paper as a way to solve NP-complete problems. Once again, we find the “real world / paper” distinction used as a cover for intellectual laziness.

Let me end this rant by preempting the inevitable cliché that “in theory, there’s no difference between theory and practice; in practice, there is.” Behold my unanswerable retort:

In theory, there’s no difference between theory and practice even in practice.

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

[Here’s a little fable that I wrote today, while listening to a talk “showing” that a fault-tolerant quantum computer would need at least 100 physical qubits for every logical qubit. Physicists are welcome to shoot back with counter-fables, as are closet computer scientists like His Holiness.]

Update: The Pontiff has accepted my challenge and posted a counter-fable to his blog. I’ve replied in his comments section with a counter-counter-fable.

One day a group of physicists ran excitedly into the computer science building. “Guess what?” they cried. “You know how you’re always trying to prove lower bounds, but you almost never succeed? Well, today we proved a lower bound!”

“What did you prove?” asked the computer scientists.

“We proved that to pull a wagon through a forest, you need at least five oxen. It’s physically impossible to do it with four oxen or less, regardless of what other resources you have.”

“How did you prove that?”

“Well, we looked up the strength of a typical ox, the weight of a typical wagon, the size of every forest in a 30-mile radius…”

“Yeah, but what if you had an ox the size of a Brontosaurus? Or what if the forest was only two feet across? Or what if the wagon weighed less than a fingernail?”

The physicists snickered. “These are clearly unphysical assumptions. As long as you stay within a realistic region of parameter space, our impossibility proof is airtight.”

“Ah, but how do you know there couldn’t be some completely different method of pulling wagons — maybe even a method that’s not ox-based at all?”

“Look, we physicists are interested in the real world, not complexity-theory la-la land. And at least in the real world, when people want to pull wagons, oxen are what they use.”

The physicists weren’t heard from again until almost a decade later, when they once again barged into the CS building. “Guess what?” they cried. “We just discovered a loophole in the famous Five-Ox Theorem — the one we published years ago in Nature!”

“What’s the loophole?”

“Elephants! If you had an elephant pulling the wagon, you wouldn’t need any oxen at all. With hindsight it’s almost obvious, but what a paradigm shift it took!”

The computer scientists stared blankly.

“You see,” said the physicists. “This is why we never trust so-called impossibility proofs.”

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

Listen to the latest edition of Lance Fortnow’s ComplexityCast (“Complexity on Your iPod”) on Podcast or MP3.

The topic: “What Physicists Should Know About Computational Complexity”
Length: 22 minutes
Geekiness: High

I’m, uh, sorry about all the, you know, mumbling. Clearly I haven’t yet been media-trained.

Follow

Is math a science? What about computer science? (A commenter on an earlier post repeated the well-known line that “no subject calling itself a science is one.”)

These are, at the same time, boring definitional disputes best left to funding agencies, and profound mysteries worthy of such intellects as Plato, Leibniz, and Gödel. In a recent comment on Peter Woit’s blog, the physicist John Baez — as usual — went straight to the heart of the matter:

“The problem of course is that in the standard modern picture, science is empirical, based on induction, and tends to favor a materialistic ontology, while mathematics is non-empirical, based on deduction, and tends to favor a Platonist/Pythagorean ontology… yet somehow they need each other! So, mathematics is not only the queen and handmaiden of the sciences – it’s the secret mistress as well, a source of romantic fascination but also some embarrassment.”

That 17 is prime strikes us as absolutely certain, yet there’s nothing in the physical world we can point to as the source of that certainty. (Seventeen blocks that can’t be arranged into a rectangle? Give me a break.) In that respect, math seems more like subjective experience than science: you might be wrong about the sky being blue, but you can’t be wrong about your seeing it as blue. Maybe this has something to do with mathematicians’ much-noted mystical tendencies: Pythagoras sacrificing a hundred oxen because the square root of 2 was irrational; Cantor naming infinite cardinalities using the Hebrew letter aleph, which represents the “infinite greatness of God” in Kabbalah; Erdös forswearing earthly pleasures to devote his life to the Book; Gödel updating St. Anselm’s proof of the existence of God; Penrose speculating that quantum gravity gives rise to consciousness. My favorite novel about mathematicians, Rebecca Goldstein’s The Mind-Body Problem, gets much of its mileage from this ancient connection. (For empirical types: according to a 1997 survey by Larson and Witham, ~40% of mathematicians say they believe in God, compared to 20% of physicists and 30% of biologists.)

And yet, if mathematicians are mystics during those rare late-night epiphanies when they first apprehend (or believe they’ve apprehended) a timeless thought of God, then they’re scientists through and through when it comes time to LaTeX that thought and post it to the arXiv. What makes me so sure of that? Mostly, that my 10th-grade chemistry teacher claimed the opposite.

To give you some background, this is a teacher whose hatred of curiosity and independent thought was renowned throughout the school district — who’d give her students detentions for showing up fifteen seconds after the bell — who’d flunk me on exams, even when I got the answers right, because I refused to write things like (1 mol)/(1 g) = 1 mol/g. Immediately after enduring her class, I dropped out of high school and went straight to college, picking up a G.E.D. along the way. For I had sworn to myself, while listening to this woman lecture, that the goal of my life was to become her antithesis: the living embodiment of everything she detested. Ten years later, I still haven’t wavered from that goal.

Which brings me to the term project in her class. We were supposed to interview a scientist — any scientist — and then write a detailed report about his or her work. I chose a mathematician at Bell Labs who did operations research. After I’d interviewed the guy and finished my project, the teacher ordered me to redo it from scratch with a different interviewee. Why? Because “mathematicians aren’t real scientists.” (To give some context, the teacher did accept a pharmacist, a physical therapist, and an architect as real scientists.)

Now, is it possible that my views about the epistemological status of mathematics are hopelessly colored by enmity toward my chemistry teacher? Yes, it is. But as far as I can tell, the refusal to count math and CS among the sciences has done some real damage, even outside the intellectual prison known as high school. Let’s consider a few examples:

• The New York Times hardly ever runs a story about math or CS theory, but it runs the same story about cosmology and string theory every two weeks.

• We all know the recipe for getting a paper published in Science or Nature: first gather up all your analytical results, and bury them in your yard. Then make some multicolored charts of Experimental Data, which suggest (at a 2σ level) the same conclusions you previously reached via the forbidden method of proving them true.

• Philosophers like Wittgenstein have gotten away with saying arbitrarily dumb things, like “Mathematical propositions express no thoughts.” As my adviser Umesh Vazirani pointed out to me, the proper response to anyone who says that is: “Indeed, the mathematical propositions that you know express no thoughts.”

• Many people seem to have the idea that, whereas scientists proceed by proposing theories and then shooting them down, mathematicians somehow proceed in a different, alien way. Which raises the question: what other way is there? Whenever I hear someone claim that “quantum computers are really just analog computers,” or “all cellular automata that aren’t obviously simple are Turing-complete,” I’m reminded that Popper’s notion of falsifiability is just as important in math and CS as in any other sciences.

• Saddest of all, many mathematicians and computer scientists seem to reason that, because they can write their results up with something approaching Platonic rigor, it follows that they should. Thus we have the spectacle of math/CS papers that, were they chemistry papers, would read something like this: “First I took the test tube out of the cabinet. Then I rinsed it. Then I filled it with the solution. Then I placed it on the bunsen burner…” For whom are such papers written? The author’s high-school teacher? God? I would think it obvious that the goal of writing a math paper should be to explain your results in just enough detail that your colleagues can “replicate” them — not in their labs or their computers, but in their minds.

The bottom line, of course, is that math and CS are similar to biology and physics in the most important sense: they bite back. Granted, you might be sitting in your armchair when you do them, but at least you’re probably leaning forward in the armchair, scribbling on a piece of paper and willing to be surprised by what you find there.

This seems like an appropriate time to quote the distinguished American philosopher Dave Barry.

Here is a very important piece of advice: be sure to choose a major that does not involve Known Facts and Right Answers. This means you must not major in mathematics, physics, biology, or chemistry, because these subjects involve actual facts. If, for example, you major in mathematics, you’re going to wander into class one day and the professor will say: “Define the cosine integer of the quadrant of a rhomboid binary axis, and extrapolate your result to five significant vertices.” If you don’t come up with exactly the answer the professor has in mind, you fail. The same is true of chemistry: if you write in your exam book that carbon and hydrogen combine to form oak, your professor will flunk you. He wants you to come up with the same answer he and all the other chemists have agreed on. Scientists are extremely snotty about this.

And, since I can’t resist, here’s a classic joke.

The dean summons the physics department chair to his office. “You people are bankrupting us!” he fumes. “Why do you need all this expensive equipment? All the mathematicians ever ask for is pencils, paper, and erasers. And the philosophers are better still: they don’t even ask for erasers!”

Follow

Over at Peter Woit’s blog there’s a lively discussion about the differences between string theory and intelligent design. There are a few obvious ones: one is based Fields Medal caliber math and the other on elementary mistakes in probability; one is studied at an Institute and the other at an “Institute”. But arguably, neither theory has yet made a clear prediction or explained what it sets out to in a non-circular way. String theorists explain the muon mass by invoking an infinite set of Calabi-Yau manifolds, some of which presumably yield the right value; ID’ers explain the complicated dance of bees by invoking a yet more complicated designer.

Of course, an important difference is that most string theorists admit the situation sucks. Many are searching for some deeper principle that would pick out a preferred vacuum (or set of vacua, or probability distribution over vacua) non-anthropically. Based on what little I know, it doesn’t sound like an enviable task. Today I had lunch with Frederik Denef, a string theorist who’s interested in the computational complexity of finding a minimum-energy vacuum, given a collection of scalar fields. He’s formulated some toy problems, all of which are provably NP-hard (or as hard as unique-SVP under a uniqueness assumption). I was impressed by Denef’s knowledge of complexity, and by his willingness to state precise problems that I could understand. But his work suggests an obvious conundrum: if finding an “optimal” Calabi-Yau is so hard, then how did Nature do it in the first place? (If the string theorists ever succeed, will a voice in the sky boom “Thanks, dudes!” just before space as we know it disappears?)

In short, if the ID’ers are armed squatters in the apartment building of science, openly scorning the materialistic concept of rent, then the string theorists are model tenants who often drop by the landlord’s office to say good afternoon, and by the way, that check from 20 years ago should clear any day. (In their defense, the other quantum gravity theorists’ checks haven’t cleared either.) To me, this raises an interesting question: does science need a notion of “resource-bounded falsifiability,” which is to Popper’s original notion as complexity is to computability?

Follow