Shtetl-Optimized

Happy Thanksgiving to my American readers! I arrived last night at my parents’ place in Pennsylvania. After I’ve digested enough to walk again, I’m off to Cambridge (the England one), then Brisbane, Australia, then back to America before Christmas Eve (which I do celebrate, with Alex Halderman’s family).

For all the academic traveling I’ve done, this will be my first time circumnavigating the globe. I can’t wait to find out whether it’s really round, or whether thar’ be dragons at the end.

Yet wherever I go, I’ll always be an American. In Toronto’s Pearson airport, I came across a Maclean’s (roughly, Canada’s Time or Newsweek), whose cover depicted a smirking Bush holding a glass of water. The headline (which I’m not making up):

America is thirsty
Let’s sell them our water before they take it

Sure, we might be chipping away at that “land of the free” part, but we’re still the home of the brave.

Follow

Sorry for the delay! I was procrastinating all week by doing real work, but I’ve finally put my foot down and resolved that blogging must come first.

I lost a lot of respect for Dilbert cartoonist Scott Adams after flipping through this compilation, which offers a tedious and redundant explanation for every cartoon. But, not content to rest on his laurels, Adams has recently come out as “undecided” on the question of Darwinism versus ID.

Whenever I encounter an online mudfight about this issue, I’m struck by how few commenters — even the ones on “our” side — really grasp the crucial point: that ID is scientifically worthless, not because it’s religiously-motivated, or unfalsifiable, or even necessarily wrong, but rather because it’s boring.

Among elephant seals, 4% of the males account for 88% of the copulations. The other 96%, the ones without harems, almost never get laid. This is puzzling: why do the seals bother to produce all those males who tax the community’s food supply, yet who are destined to become the seal equivalents of computer science grad students?

The answer is that a 50-50 sex ratio is the only evolutionarily stable strategy. Think about it: if every child gets half its genes from a mother and half from a father, then males and females must pass on the same total number of genes, even if the variance is higher for males. So if you’re a female elephant seal, then you can either play it safe by having a daughter, or shoot for the genetic jackpot by having a son. In expectation, both strategies will do equally well. But if there were more girls than guys in the population, then the expected number of grandchildren per son would become greater than the expected number of grandchildren per daughter. So the advantage would shift in favor of having a son, and would continue to do so until a 50-50 equilibrium was reestablished. Mystery solved. (The example comes from Dawkins, one of the few writers who consistently presents Darwinism as a way to actually explain things. The explanation itself comes from Fisher.)

On the airplane of science, nontrivial explanations are not the beverage cart or the in-flight movie — they’re the wings. If you think something was designed, but can’t explain why the designer chose to make it one way rather than some other way, then it doesn’t matter if you’re right or not: you don’t have a result. There’s no STOC/FOCS paper.

This, I suspect, is what underlies the disconnect between scientists and almost everyone else on this issue. The business of judging ideas by their explanatory power, and rejecting the ones that don’t have any, is remarkably new in human history. Even in the hard sciences, it wasn’t until Galileo that it really caught on. So maybe it shouldn’t surprise anyone that, in K-12 science education, it’s still a bizarre and heretical idea.

Why do things fall? Because gravity makes them fall.

How does a car work? By using energy.

Why do we need to sleep? To rest ourselves.

Who designed us? A designer did.

Follow

Over at Freedom to Tinker, Alex Halderman and his adviser Ed Felten have been causing headaches for SunnComm, the makers of broken technology designed to prevent the copying of music CD’s. Alex is the Princeton graduate student who enjoyed worldwide media attention two years ago, when he showed that SunnComm’s “MediaMax” anti-copying software could be disabled by holding down the “Shift” key while inserting a CD into your computer. Alex’s paper about this was downloaded over a hundred thousand times, and caused SunnComm’s stock to lose $10,000,000 in a week. By comparison, my paper Quantum Lower Bound for Recursive Fourier Sampling has (I think) been downloaded at least twice, and would have driven Recursive Fourier Sampling In 2^o(h) Queries Incorporated out of business, had it existed.

Now Alex and Ed are reporting that SunnComm has continued to “innovate.” It seems that the latest version of MediaMax, which is included with several Sony/BMG music CD’s,

1. secretly installs itself even before you accept the End User License Agreement,
2. remains installed even if you decline the agreement, and
3. secretly “phones home” to SunnComm with information about your activities, despite assurances to the contrary.

Alex and I met in seventh grade at Newtown Junior High School. I had just transferred from a parochial school, and was so low in the social hierarchy that, when kids beat me up, I was grateful for the attention. My one consolation was that, out of all the kids in the school, I — and I alone — knew that dx³/dx=3x² and that t’=t/√(1-(v/c)²). Most importantly, I alone knew how to program in GW-BASIC.

So you can imagine the existential shock when I heard there was another kid in seventh grade who was already writing Windows applications and marketing them as shareware. Clearly I had to meet this guy, see if he was for real. After I found out that he was — and repaired the gaping holes in my ego — Alex and I became best friends. We remain so twelve years later.

Even in junior high, Alex was obsessed with security issues: his bestselling program, if I remember correctly, was an encryption utility. At the same time, he was obviously a “white hat.” Rather than getting himself into trouble by hacking the school computers, he’d simply make the teachers utterly reliant on his expertise, then ask them for administrator privileges.

One day in the cafeteria, Alex excitedly brought me a book he was reading, which described a bizarre-sounding encryption system called “RSA.” Supposedly, with this system you could send someone secret messages without ever having met them to agree on a key.

“But that’s obviously impossible,” I explained. I was proud that, for once, I could use my superior mathematical knowledge to set Alex straight.

Eventually Alex and I both ended up in academic computer science, albeit on opposite sides of it. Perhaps the difference between us is best summarized as follows. For Alex, the impossibility of making digital information copy-proof is a central truth of our age: something to be explained, and then re-explained, to judges, reporters, and businesspeople, in amicus curiae briefs and interviews on NPR. For me, it follows from the fact that the set of n-bit strings constitutes an orthogonal basis for Hilbert space.

Follow

I just finished Marjane Satrapi’s Persepolis, the most astonishing comic book I’ve ever seen. Persepolis tells the story of Satrapi’s childhood in Iran, during which she witnessed the repressive regime of the Shah, then the takeover by Khomeini (who made the Shah look like Mr. Rogers), then the war with Iraq. What makes the story so compelling is not the horrors — next-door neighbors killed by an Iraqi missile, relatives tortured and executed for counterrevolutionary activities, etc. — but Satrapi and her friends’ absurd attempts to enjoy a normal childhood while all of this was going on. She describes how the girls in her school, suddenly forced to wear veils, would put them on backwards and pretend to be “monsters of the darkness”; how her dad brought her an Iron Maiden poster from Turkey by weaving it into his suit, lurching through airport security like Frankenstein’s monster; how a food shortage that emptied the supermarkets of everything but kidney beans provided an occasion for fart jokes. For me, reading this book only deepened the mystery of Iran: namely, how could such a funny, literate, humane country be conquered so completely by fundamentalist thugs? On reflection, I guess it’s happened before. And I guess I should be grateful that in the US, our secular institutions are strong enough that even Bush hasn’t destroyed them entirely.

Persepolis raises pointed questions about the naïveté of intellectuals, like the Iranian Marxists who refused to see the Islamists for what they were until it was too late. To any intellectuals still in Iran, I can only second Eldar’s advice, in the comments to a previous post: Get out! Get out now! And to everyone else, set aside a couple hours (which is all it takes) to read Persepolis. It might be the first comic book to win a Nobel Prize in Literature.

Follow

Newcomb’s Problem, for those of you with social lives, is this. A superintelligent “Predictor” puts two opaque boxes on a table. The first contains either $1,000,000 or nothing, while the second contains $1,000. You have a choice: you can either open the first box or both boxes. Either way, you get to keep whatever you find.

But (duhhh…) there’s a catch: the Predictor has already predicted what you’ll do. If he predicted you’ll open both boxes, then he left the first box empty; if he predicted you’ll open the first box only, then he put $1,000,000 in the first box. Furthermore, the Predictor has played this game hundreds of times before, with you and other people, and has never once been wrong.

So what do you do? As Robert Nozick wrote, in a famous 1969 paper:

“To almost everyone, it is perfectly clear and obvious what should be done. The difficulty is that these people seem to divide almost evenly on the problem, with large numbers thinking that the opposing half is just being silly.”

Actually, people confronted with Newcomb’s Problem tend to split into three camps: the one-boxers, the two-boxers, and the Wittgensteins.

The one-boxers figure they might as well trust the Predictor: after all, he’s never been wrong. According to the prediction, if you open the first box you’ll get $1,000,000, while if you open both you’ll only get $1,000. So it’s a no-brainer: you should open only the first box.

“But that’s stupid!” say the two-boxers. “By the time you’re making the choice, the $1,000,000 is either in the first box or it isn’t. Your choice can’t possibly change the past. And whatever you’d get by opening the first box, you’ll get $1,000 more by opening both. So obviously you should open both boxes.”

(Incidentally, don’t imagine you can wiggle out of this by basing your decision on a coin flip! For suppose the Predictor predicts you’ll open only the first box with probability p. Then he’ll put the $1,000,000 in that box with the same probability p. So your expected payoff is 1,000,000p² + 1,001,000p(1-p) + 1,000(1-p)² = 1,000,000p + 1,000(1-p), and you’re stuck with the same paradox as before.)

The Wittgensteins take a third, boring way out. “The whole setup is contradictory!” they say. “It’s like asking what happens if an irresistable force hits an immovable object. If the ‘Predictor’ actually existed, then you wouldn’t have free will, so you wouldn’t be making a choice to begin with. Your very choice implies that the Predictor can’t exist.”

I myself once belonged to the Wittgenstein camp. Recently, however, I came up with a new solution to Newcomb’s Problem — one that I don’t think has ever been discussed in the literature. (Please correct me if I’m wrong.) As I see it, my solution lets me be an intellectually-fulfilled one-boxer: someone who can pocket the $1,000,000, yet still believe the future doesn’t affect the past. I was going to write up my solution for a philosophy journal, but what fun is that? Instead, I hereby offer it for the enlightenment and edification of Shtetl-Optimized readers.

We’ll start with a definition:

“You” are anything that suffices to predict your future behavior.

I know this definition seems circular, but it has an important consequence: that if some external entity could predict your future behavior as well as you could, then we’d have to regard that entity as “instantiating” another copy of you. In other words, just as a perfect simulation of multiplication is multiplication, I’m asserting that a perfect simulation of you is you.

Now imagine you’re standing in front of the boxes, agonizing over what to do. As the minutes pass, your mind wanders:

I wonder what the Predictor thinks I’ll decide? “Predictor”! What a pompous asshole. Thinks he knows me better than I do. He’s like that idiot counselor at Camp Kirkville — what was his name again? Andrew. I can still hear his patronizing voice: “You may not believe me now, but someday you’ll realize you were wrong to hide those candy bars under the bed. And I don’t care if you hate the cafeteria food! What about the other kids, who don’t have candy bars? Didn’t you ever think of them?” Well, you know what, Predictor? Let’s see how well you can track my thoughts. Opening only one box would be rather odd, wouldn’t you say? Camp Kirkville, Andrew, candy bar – that’s 27 letters in total. An odd number. So then that settles it: one box.

What’s my point? That reliably predicting whether you’ll take one or both boxes is “you-complete,” in the sense that anyone who can do it should be able to predict anything else about you as well. So by definition, the Predictor must be running a simulation of you so detailed that it’s literally a copy of you. But in that case, how can you possibly know whether you’re the “real” you, or a simulated version running inside the Predictor’s mind?

“But that’s silly!” you interject. “Here, I’ll prove I’m the ‘real’ me by pinching myself!” But of course, your simulated doppelganger says and does exactly the same thing. Let’s face it: the two of you are like IP and PSPACE, water and H₂O, Mark Twain and Samuel Clemens.

If you accept that, then the optimal strategy is clear: open the first box only. Sure, you could make an extra $1,000 by opening both boxes if you didn’t lead a double life inside the Predictor’s head, but you do. That, and not “backwards-in-time causation,” is what explains how your decision can affect whether or not there’s $1,000,000 in the first box.

An important point about my solution is that it completely sidesteps the “mystery” of free will and determinism, in much the same way that an NP-completeness proof sidesteps the mystery of P versus NP. What I mean is that, while it is mysterious how your “free will” could influence the output of the Predictor’s simulation, it doesn’t seem more mysterious than how your free will could influence the output of your own brain! It’s six of one, half a dozen of the other. Or at least, that’s what the neural firings in my own brain have inexorably led me to believe.

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

Everyone knows that if you have a cold, the most important thing (besides chicken soup) is to get plenty of sleep. Sleep is when your white blood cells stop reading The Onion and watching Simpsons reruns, and start snacking on viruses.

But what if your cold is so severe that you can’t sleep, not even for an hour or two? What do you do then? Not knowing the answer — but knowing readers of your blog will be getting increasingly antsy — you go see a doctor. The doctor says to take NyQuil to sleep.

The problem is that NyQuil tastes worse than Vegemite, and (another Catch-22) you can barely force a drop of it down your swollen throat. So you mix a Coke and NyQuil, on the rocks. But this merely converts a small disgusting green beverage into a large disgusting greenish-brown one.

So you go back to the drugstore, where you’re relieved to learn that NyQuil is also sold in capsule form. You take two capsules. Hours later, you’re still not asleep. So you take a third. An hour later you’re still not asleep, and your throat is in indescribable pain. So you take two Advils. The pain doesn’t go away, so you take a third Advil.

At this point you start hallucinating and feeling dizzy. Your skin is pale, your pupils are dilated, and you’re sweating profusely. Uh-oh. What was in those pills, anyway? In each NyQuil: Dextromethorphan HBr 15mg, Pseudoephedrine HCl 30mg, Acetaminophen 325mg, Doxylamine succinate 6.25mg. In each Advil Cold & Sinus: Ibuprofen 200mg, Pseudoephedrine HCl 30mg. So, you’ve now ingested 180mg of Pseudoephedrine HCl, whatever the hell that is.

“In case of accidental overdose contact a physician or poison control centre immediately, even if there are no symptoms.”

Staggering over to your computer, you read that overdosing on antihistamines and decongestants can be fatal, and that indeed, the proper thing to do would be to get your stomach pumped as soon as possible. But it’s 4AM, and for better or worse, you decide to leave the 9-1-1 operator alone, and trust that three billion years of Darwinian natural selection weren’t for bleaaaarrrrrgghhhhhhhhh…

The Moral: Never assume that, just because a single dose of a drug doesn’t help you, a double or triple dose isn’t going to kill you.

It actually gets even more nauseating, but I’ll cut to the end: after more than a week, I can eat again. I can blog again. I can lower-bound again. I can even talk again, though I won’t be playing female leads in Broadway musicals anytime soon.

It’s good to be back.

Follow