Archive for the ‘CS/Physics Deathmatch’ Category

Newton vs. Leibniz: the wigs are off

Tuesday, October 17th, 2006

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):

The physicists and the wagon

Monday, June 19th, 2006

[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.”

The neologistas

Saturday, May 27th, 2006

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.

My interview with Lance

Thursday, December 15th, 2005

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.

It’s science if it bites back

Wednesday, November 9th, 2005

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!”

Insert “string” pun here

Thursday, October 27th, 2005

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?