Shtetl-Optimized

In the comments section of my last post, Jack in Danville writes:

I may have misunderstood [an offhand comment about the “irrelevance” of the Continuum Hypothesis] … Intuitively I’ve thought the Continuum Hypothesis describes an aspect of the real world.

I know we’ve touched on similar topics before, but something tells me many of you are hungerin’ for a metamathematical foodfight, and Jack’s perplexity seemed as good a pretext as any for starting a new thread.

So, Jack: this is a Deep Question, but let me try to summarize my view in a few paragraphs.

It’s easy to imagine a “physical process” whose outcome could depend on whether Goldbach’s Conjecture is true or false. (For example, a computer program that tests even numbers successively and halts if it finds one that’s not a sum of two primes.) Likewise for P versus NP, the Riemann Hypothesis, and even considerably more abstract questions.

But can you imagine a “physical process” whose outcome could depend on whether there’s a set larger than the set of integers but smaller than the set of real numbers? If so, what would it look like?

I submit that the key distinction is between

1. questions that are ultimately about Turing machines and finite sets of integers (even if they’re not phrased that way), and
2. questions that aren’t.

We need to assume that we have a “direct intuition” about integers and finite processes, which precedes formal reasoning — since without such an intuition, we couldn’t even do formal reasoning in the first place! By contrast, for me the great lesson of Gödel and Cohen’s independence results is that we don’t have a similar intuition about transfinite sets, even if we sometimes fool ourselves into thinking we do. Sure, we might say we’re talking about arbitrary subsets of real numbers, but on closer inspection, it turns out we’re just talking about consequences of the ZFC axioms, and those axioms will happily admit models with intermediate cardinalities and other models without them, the same way the axioms of group theory admit both abelian and non-abelian groups. (Incidentally, Gödel’s models of ZFC+CH and Cohen’s models of ZFC+not(CH) both involve only countably many elements, which makes the notion that they’re telling us about some external reality even harder to understand.)

Of course, everything I’ve said is consistent with the possibility that there’s a “truth” about CH floating in Platonic heaven, or even that a plausible axiom system other than ZFC could prove or disprove CH (which was Gödel’s hope). But the “truth” of CH is not going to have consequences for human beings or the physical universe independent of its provability, in the same way that the truth of P=NP could conceivably have consequences for us even if we weren’t able to prove or disprove it.

For mathematicians, this distinction between “CH-like questions” and “Goldbach/Riemann/Pvs.NP-like questions” is a cringingly obvious one, probably even too obvious to point out. But I’ve seen so many people argue about Platonism versus formalism as if this distinction didn’t exist — as if one can’t be a Platonist about integers but a formalist about transfinite sets — that I think it’s worth hammering home.

To summarize, Kronecker had it backwards. Man and Woman deal with the integers; all else is the province of God.

Question for the day: what do libertarianism and the Many-Worlds Interpretation of quantum mechanics have in common? Interest in the two worldviews seems to be positively correlated: think of quantum computing pioneer David Deutsch, or several prominent posters over at Overcoming Bias, or … oh, alright, my sample size is admittedly pretty small.

Some connections are obvious: libertarianism and MWI are both grand philosophical theories that start from premises that almost all educated people accept (quantum mechanics in the one case, Econ 101 in the other), and claim to reach conclusions that most educated people reject, or are at least puzzled by (the existence of parallel universes / the desirability of eliminating fire departments). Both theories seem to have a strong following with nerds who read science fiction and post to Internet discussion groups, but a relatively poorer following with both John Q. Public and Alistair K. Intellectual. (Needless to say, these stereotypes tell us almost nothing about the theories’ validity.)

My own hypothesis has to do with bullet-dodgers versus bullet-swallowers. A bullet-dodger is a person who says things like:

Sure, obviously if you pursued that particular line of reasoning to an extreme, then you’d get such-and-such an absurd-seeming conclusion. But that very fact suggests that other forces might come into play that we don’t understand yet or haven’t accounted for. So let’s just make a mental note of it and move on.

Faced with exactly the same situation, a bullet-swallower will exclaim:

The entire world should follow the line of reasoning to precisely this extreme, and this is the conclusion, and if a ‘consensus of educated opinion’ finds it disagreeable or absurd, then so much the worse for educated opinion! Those who accept this are intellectual heroes; those who don’t are cowards.

In a lifetime of websurfing, I don’t think I’ve ever read an argument by a libertarian or a Many-Worlds proponent that didn’t sound like the latter.

We know plenty of historical examples where the bullet-swallowers were gloriously right: Moore’s Law, Darwinism, the abolition of slavery, women’s rights. On the other hand, at various points within the last 150 years, extremely smart people also reasoned themselves to the inescapable conclusions that aether had to exist for light to be a wave in, that capitalism was reaching its final crisis, that only a world government could prevent imminent nuclear war, and that space colonies would surely exist by 2000. In those cases, even if you couldn’t spot any flaws in the arguments, you still would’ve been wise to doubt their conclusions. (Or are you sure you would have spotted the flaws where Maxwell and Kelvin, Russell and Einstein did not?)

Here’s a favorite analogy. The world is a real-valued function that’s almost completely unknown to us, and that we only observe in the vicinity of a single point x₀. To our surprise, we find that, within that tiny vicinity, we can approximate the function extremely well by a Taylor series.

“Aha!” exclaim the bullet-swallowers. “So then the function must be the infinite series, neither more nor less.”

“Not so fast,” reply the bullet-dodgers. “All we know is that we can approximate the function in a small open interval around x₀. Who knows what unsuspected phenomena might be lurking beyond it?”

“Intellectual cowardice!” the first group snorts. “You’re just like the Jesuit schoolmen, who dismissed the Copernican system as a mere calculational device! Why can’t you accept what our best theory is clearly telling us?”

So who’s right: the bullet-swallowing libertarian Many-Worlders, or the bullet-dodging intellectual kibitzers? Well, that depends on whether the function is sin(x) or log(x).

Yeah, yeah, I know.  Combination of the end of the semester and family matters.  But I’m back with four more GITCS lectures:

• Lecture 12: Space Complexity and More

• Lecture 13: Randomness

• Lecture 14: Probabilistic Complexity Classes

• Lecture 15: Derandomization / Crypto Double Feature

Comments welcome as always.

I’ve had a miserable week (only partly because of the headaches and coughing fits that have been keeping me up all night), and feel a need to be of use to some other human being without leaving my apartment. So this thread is for you to ask about whatever’s on your mind — complexity classes, philosophy, grad school advice, anteaters … anything asked in earnest will be responded to, in considerably less than the two years it took me for Lev R.

Update (4/13): Having spent a good part of the weekend answering 57 questions about everything from quantum computing to painting elephants, I think it’s time to call it quits. Thanks to everyone who submitted; it really cheered me up! We’ll do this again sometime.

A few more lectures, hot off the Turing machine tape:

• Lecture 8: Polynomial Time
• Lecture 9: P and NP
• Lecture 10: NP-completeness
• Lecture 11: NP-completeness in Practice

Yeah, it’s all standard material, but if you don’t know it … well, this is one more place you can learn.

Apropos of computer science education, some of you may have heard the sad news that the College Board is killing the AP Computer Science AB test [Slashdot] [Pontiff]. The reasons they gave were that (1) not enough students were taking it and (2) of those who were, not enough were underrepresented minorities.

I took the AB test in ‘96, despite not having taken the course (my high school didn’t offer it) and not knowing Pascal (the language they still used, before they switched to C++ and then Java). I did read a book to prepare, and that’s where I got my first exposure to O-notation, linked lists, and other crumbs from the feast table of theory. I devoured it all like a hungry dog licking the floor.

It goes without saying that high school students (including underrepresented minorities) won’t take an AP course if it isn’t offered, or if their schools or the colleges they’re applying to don’t take it seriously. Computer science education is a threat to many people’s pet ideas about the world: that CS is not a real subject and is devoid of intellectual content. That everything having to do with computers is mundane and technical, and should (for that reason) be outsourced to China and India. That if we must teach CS, we should at least focus on applications, and get rid of any math or logical thought. That CS is passé, a 20^th-century relic that was long ago superseded by the life sciences (haven’t computer scientists gotten the message yet?). Against this backdrop, it’s not surprising that the AB test is being killed: what’s surprising is that it lasted so long.

Blogging will continue to be sporadic, as I have a cold.

Update (4/10): Lenore Blum just gave a talk here at MIT about the future of CS education, in which she echoed several themes of this post, but also argued (among other things) that the cancellation of APCSAB is good news given the course’s obsessive focus on the details of the programming language du jour, and given high schools’ refusal to treat it as a real academic subject, instead grouping it with “electives” like woodshop and metalworking. She held out hope that the US will someday develop a reasonable K-12 computer science curriculum, pointing to successful models from Israel and New Zealand. Needless to say, I have mixed feelings about canceling the mediocre (AB), keeping the truly bad (A), and hoping for the distant good.

Almost two years ago, a reader named Lev R. won my Best Anthropicism Contest with the following gem:

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

As the champion, Lev won the right to ask any question and have me answer it on this blog. Here was Lev’s question:

I like your “Earth Day, Doomsday, and Chicken Little” post, but you dodged the big question. Will the world end (humans go extinct) anytime soon? Or do you think that despite our best efforts, we’ll somehow end up not destroying ourselves?

In general, I despise being asked to make predictions, even about infinitely less weighty topics — especially when there’s a chance of my being wrong, and people looking back Nelson-Muntz-like and saying “ha ha, Scott was wrong!” That’s one of only several reasons why I could never be a physicist.

An answerable question would be one that asked me to clear up a misconception, or render a moral judgment, or discuss the consequences of a given assumption. (Unanswerable: “When will we see useful quantum computers?” Answerable: “Didn’t that company in Vancouver already build one?”) Questions about relationships between complexity classes or other unsolved math problems are also fine. But as for the universe, how am I supposed to know what it’ll decide to do, among all the things it could do within reasonable bounds of physics and logic? How am I even supposed to have a prior? As a CS theorist, I’m trained to think not about what’s likely to happen, but about the very worst that could happen — within stated assumptions, of course. Among the practical consequences of this attitude, I never gamble and I never play the stock market (and not only because, while there are many things I want, almost none of them can be traded for money). I also don’t worry about being put out of a job by prediction markets. Where the Bayesian stops, and says “every question beyond these is trivial or meaningless,” that’s where I’m just getting started.

But despite everything I’ve said, after years of diligent research into the future of the human race — reading hundreds of trillions of books and articles about climate change, overpopulation, Peak Oil, nuclear proliferation, transhumanism, AI, and every other conceivably relevant topic (what do you think I was doing, writing CS papers?) — I am finally prepared, this somber April 1^st, to answer Lev’s question with the seriousness it deserves. Obviously my predictions can only be probabilistic, and obviously I can’t give you the deep reasons behind them — those would take years to explain. I shall therefore present the human future, circa 2100, in the form of a pie chart.

Consider the following less-than-hypothetical scenarios:

• Joseph Weizenbaum (who passed away two weeks ago), the MIT computer scientist who created the ELIZA chatbot in the 1960’s, spent the rest of his career decrying the evils of computer science research, holding (perhaps strangely) both that almost everything that’s done with computers could be done just as well without them, and that computers have made possible terrible things like missile guidance systems that now threaten our civilization.

• Distinguished mathematician Doron Zeilberger argues that mathematicians are wasting their time pursuing chimeras like “beauty” and “elegance,” and that within the near future, mathematics will be entirely the domain of computers.

• Ayaan Hirsi Ali, who was born into a Muslim family in Somalia, and who escaped from an arranged marriage after being forced to undergo FGM, tells Westerners they’re deluding themselves if they think current Islamic practices are compatible with Enlightenment values.

• John Browne, the Chief Executive of BP, tells the world that urgent action is needed on global warming.

• A former atheist stumps for Christianity (or vice versa).

The obvious question in all these cases is: how much extra credence does a person gain by belonging, or having once belonged, to the group he or she is criticizing? From a strict rationalist standpoint, the answer would seem to be zero: surely all that matters is the soundness of the arguments! Who cares if the keynote speaker at the anti-widget rally also happens to be past president of the Widget Club?

I can think of three possible reasons for giving extra credence to attacks from insiders:

1. The insider might simply know more about the realities of the situation than an outsider, or be less able to ignore those realities.
2. One assumes the insider is someone who’s at least grappled with the best arguments from her own side before rejecting them. (In FantasyLand, one could assume that anyone making an argument had first grappled with the best arguments from the opposing side, but FantasyLand≠Earth.)
3. When someone relentlessly attacks a single group of people — seeming to find them behind every perfidy on earth — history says to assume the worst about their motivations, and not to accept the refrain “I’m only criticizing them for their own good!” However, it’s possible that members of the group themselves should merit a pass in this regard. (Though even here there are exceptions: for example, if the person has renounced all ties with the despised group, or, as in the case of Bobby Fischer, refuses to accept the reality of his membership in it.)

On the other hand, I can think of five reasons why not to give extra credence to attacks from insiders:

1. Given any exotic mixture of beliefs and group affiliations, there’s almost certainly someone on earth who fits the description — and is even available for a fee to speak at your next event. If you want an accomplished scientist who sees science as an expensive sham or tool of the military, you can find one. If you want a former Republican hardliner who’s now a Naderite, you can find one. If you want a Jew who renounces Jews or Israel, you can find a stadium of them. So you can’t conclude anything from the mere existence of such people — at most, you can possibly learn something from their number.
2. Any group of people — computer scientists, CEO’s, Israelis, African-Americans — will consist (to put it mildly) of multiple factions, some of whom might seek to gain an advantage over the other factions by blasting their group as a whole before the outside world. So one can’t simply accept someone’s presentation of himself as a lone, courageous whistleblower, without first understanding the internal dynamics of the group he comes from and is criticizing.
3. The very fact that people within a group feel free to criticize it can in some cases speak well about the group’s tolerance for dissent, and thereby undermine some of the critics’ central claims. (Of course, one has to verify that the tolerated dissenters aren’t just a sham maintained by the ruling faction, as in Communist regimes throughout their history.)
4. Some people simply enjoy dissenting from their peers, as a way of proving their independence or of drawing attention to themselves.
5. Just as most people like to toot their own group’s horn, a few are masochistically biased toward the opposite extreme. We can all think of people who, for whatever deep psychological reasons, feel a constant need to repent the sins of themselves or their group, in a manner wildly out of proportion to any actual guilt. Granted, anyone can understand the conflict a physicist might feel over having participated in the Manhattan Project. On the other hand, when the invention you’re renouncing is the ELIZA chatbot, the question arises of whether you’ve earned the right to Faust-like penitence over the unspeakable evil you’ve unleashed.

So what’s my verdict? Belonging to the group you’re criticizing can give you one or two free starting chips at the table of argument, entitling you to a hearing where someone else wouldn’t be so entitled. But once you’ve sat down and entered the game, from then on you have to play by the same rules as everyone else.

For those who missed it on the sidebar, we now have six more GITCS lecture notes available:

Lecture 2: Logic

Lecture 3: Circuits and Finite Automata

Lecture 4: Turing Machines

Lecture 5: Reducibility and Gödel

Lecture 6: Minds and Machines

Lecture 7: Complexity

More are on the way — compared to the Democritus notes, it’s so much easier with others doing the writing! These notes were prepared almost entirely by the students, with only minor editing from me and Yinmeng. In general, I think the students have been doing a fantastic job. On the other hand, if you rely on these notes to build a Turing-machine-controlled jumbo jet which then crashes in the Himalayas, it’s entirely possible that it wasn’t my fault.

About six months ago, a group of theoretical computer scientists started raising concerns about what they saw as a growing problem in our field. (My parody post “FOCS’36 notification” was one attempt to explain what this problem is.) The group has now put together a statement, which I was happy to sign, and which is meant to serve as a starting point for further discussion at the STOC’08 business meeting. If you support this statement and want add your name to it, please say so in the comments section! Of course criticism is welcome too. –SA

---

We, the undersigned, are concerned about two related attitudes that seem to be increasingly prevalent in the TCS community, and in particular, are affecting its program committees and their decisions. The goal of this statement is to attempt to recognize and reverse this trend. We are happy to note that the STOC’08 PC made a conscious effort to move in the direction of this proposal.The trends that worry us are the following:

1. Assignment of little weight to “conceptual” considerations, while assigning the dominant weight to technical considerations.
2. The view that technical simplicity is a drawback, and the failure to realize that simple observations may represent an important mind-switch that can pave the way to significant progress.

Most works offer a mix of conceptual and technical aspects, where by “conceptual” we mean the aspects that can be communicated succinctly, with a minimum amount of technical notation, and yet their content reshapes our view/understanding. Conceptual contributions can be thought of as contents of the work that are most likely to be a part of a scientific hallway discussion. They may appear in a work’s “bottom line” or “along the way”.

• A conceptual “bottom line” may be a result that affects the worldview of researchers outside the community studying the problem, or the introduction of a new problem that may appeal to the wider TCS community.
• A conceptual aspect “along the way” may be an innovative way of modeling, looking at, or manipulating a known object or problem, including establishing a new connection between known objects/problems.

Needless to say, the above list is not exhaustive.

Once understood, conceptual aspects tend to be viewed as obvious, which actually means that they have become fully incorporated in the worldview of the expert. This positive effect is actually a source of trouble in the evaluation process, because the evaluators forget that these contributions were not obvious at all before being made.

Indeed, our community should be warned of dismissing such contributions by saying “yes, but that’s obvious”; when somebody says such a thing, one should ask “was it obvious to you before reading this article?”

We believe that the community needs to remain vigilant about these issues, and program committees should make a conscious effort to pay attention to conceptual contributions (as apparently done by the STOC’08 PC). This will enable our conferences to continue to be a driving force in the progress of our field.

Scott Aaronson
Allan Borodin
Bernard Chazelle
Oded Goldreich
Shafi Goldwasser
Richard Karp
Michael Kearns
Christos Papadimitriou
Madhu Sudan
Salil Vadhan

Until today, I have failed to uphold one of the most sacred responsibilities of the guild of bloggers: that of weighing in on the Democratic primary. This is not because of any desire to keep politics out of this blog: I’ve never succeeded in keeping anything out of this blog. Rather, it’s because I find the question genuinely difficult.

The general election is so damn easy by comparison. There, the only questions I need to ask myself are, “do I prefer the Enlightenment or the Dark Ages that preceded it? Is the Earth 4.6 billion years old or 10,000? Do anti-gay laws spring from a less repugnant part of human nature than Jim Crow laws?” While I look forward to the day when my answers to such questions won’t determine my vote, so far they unfailingly have — thereby eliminating the need for me to adjudicate more complicated social and economic issues that I don’t really understand.

In other words, my view of Democrats and Republicans couldn’t possibly be further from that of (say) Eliezer Yudkowsky, who sees the general US election as a meaningless, Kang vs. Kodos popularity contest. Like Yudkowsky, I can easily imagine two political parties fighting over nothing — but what I see in reality is a clearly-identifiable neo-Union and neo-Confederacy, who every four years re-fight the Civil War. As many others have pointed out, even the geographic boundary between America’s two subcountries has barely changed since the 1860’s; the one real irony is that the “party of Lincoln” now represents the Confederate side. (And yes, if the free-market/libertarian wing of the Republican Party ever broke free of the medieval wing, then this correspondence would break down. I’m only talking about things as they currently stand.)

On the other hand, as Clinton and Obama debated their subtly-different proposals for health insurance, subprime lending reform, etc., I realized that, in a race between Democrats (or a general election in a more normal country), my “go with the Enlightenment” approach can only take me so far. Faced with two non-lunatic candidates, you almost have to, like, know something about policy or economics to make a sensible choice.

So being an ignorant computer scientist, what can I say? Let’s start with the obvious: that after seven years of Bush, to ask whether I’d “prefer” Hillary or Obama is like asking a drowning person surrounded by sharks which of two lifeboats he prefers to be rescued by (and adding, in case it’s helpful, that one lifeboat is rowed by a woman and the other by a half-Kenyan). It’s a shame we can’t elect both of them, and then send one back in time to have been president for the last eight years. As the next best option, I wish the candidates would just agree right now to choose the winner by an Intrade-weighted coin flip, and thereby save money for defeating the religious-right-courting hypocrite McCain.

But of course they won’t do that, and hence the question of whom to prefer. Until recently I had a mild preference for Hillary, my reasons being as follows:

1. Because she’s been despised for so many years by so many people who I despise (and the worse they say about her, the better she seems).
2. Because she’s been doing better than Obama in crucial swing states like Florida.
3. Because with her you get all the advantages of her husband but with considerably less chance of a sex scandal.
4. Because on one issue that I actually follow — ending the Republicans’ “war on science” — her position paper is full of excellent specifics, whereas (so far as I know) Obama has only said much vaguer things in the same direction.

Recently, though, I’ve been tilting more toward Obama, for five reasons:

1. Because he’s winning (still, after last night). This, of course, would be an important piece of evidence about his likelihood of winning the general election, even if it weren’t also a prerequisite to winning.
2. Because unlike Hillary, he’s clearly stated his position on the inefficiency of bubblesort.
3. Because I’m told that some Americans now supplement their reading of text by the viewing of “YouTubes” and “tele-vision boxes” — and in those settings, Obama clearly does better. His jokes succeed where Hillary’s fail.
4. Because the 2000 and 2004 elections suggest that experience is now a severe liability: it simply translates into more stuff that an opponent will twist against you.
5. Because people whose judgment I respect, and who follow politics more closely than I do, seem to prefer Obama by a wide margin. As in Aumann’s Agreement Theorem, the mere fact of these other people’s opinions ought to change my own opinion if I’m a rational agent. Whether for rational reasons or not, it has.

Incidentally, so far as I can tell, the accusations of anti-Semitism against Obama that have filled the right-wing blogosphere are completely baseless. The assumption underlying these accusations is that admiration is a transitive predicate: that is, if x admires y and y admires z (where, say, z=Farrakhan), then x must admire z, even if x claims to “reject and denounce” z. But it’s easy to think of counterexamples: I admire Sakharov who admired Stalin (at least for part of his life), I admire Bertrand Russell who admired all sorts of thugs and poseurs, etc. Of course it’s impossible to know Obama’s heart about these matters, but I don’t think one needs to: it’s enough to know his brain.