Shtetl-Optimized

Update (8/19): I’ve answered most of the remaining questions and closed this thread.  If your question wasn’t answered earlier, please check now—sorry for the delay!  And thanks to everyone who asked.

This blog was born, in part, out of existential anguish.  My starting axioms, reflected in the blog’s title, were that

1. nerds like me are hothouse plants, requiring a bizarre, historically-improbable social environment to thrive in life;
2. if such an environment ever existed, then it didn’t survive one or more major upheavals of the twentieth century, such as the sexual revolution, the Holocaust, or the end of the Cold War;
3. I and other nerds were therefore essentially walking fossils, absurdly maladapted for the civilization in which we found ourselves (even, ironically, as that civilization relied more than ever on nerdly skills); and
4. all that being the case, I might as well kill some time by proving quantum complexity theorems and writing a blog full of crass jokes.

And therein lies the problem: this summer, I’ve simply been enjoying life too much to want to take time out to blog about it.  Happiness, it seems, is terrible for my literary productivity.

Still, enough people now rely on this blog for their procrastination needs that I feel a moral obligation to continue serving them.  So to overcome my own procrastination barrier, from now on I’m going to try writing entries that are basically just “requests for comment”: stones in a stone soup, with the intellectual barley, discursive salt, argumentative carrots, and dialectical beef chunks to be supplied by you, my readers.

(To a few commenters: thanks so much for the plywood, rotting raccoon carcasses, and used syringes, but the soup should be fine without them…)

To start things off, today we’re going to have another open thread.  You can ask pretty much anything; my one request is that you don’t ask for grad school or job application advice, since we already covered those things ad nauseum in two previous open threads.

Here are a few examples of things to ask me about:

1. My recent trip to the Azores for the FQXi Conference on Foundational Questions in Physics and Cosmology

2. My recent trip to Paris for the Complexity’2009 conference

3. My recent trip to Lexington, Kentucky for the Quantum Theory and Symmetries conference

4. The recent breakthrough paper by Jain, Ji, Upadhyay, and Watrous, finally proving what many in the quantum complexity world long suspected: that QIP=IP=PSPACE.  That is, quantum interactive proof systems provide no more computational power than classical ones.  (For more see this post from Lance and Steve Fenner, or this one from the Pontiff.)

5. The exciting new Polymath Project, to find (under some number-theoretic assumption) a deterministic polynomial-time algorithm for generating n-bit primes.  (Hat tip to Ryan O’Donnell.)

Oh, one other thing: while you’re welcome to ask personal questions, they’ll most likely be answered not by me but by Pablo the PSPACE Pirate.

Update (7/31): One question per person, please!

Follow

No doubt many of you already know … but for the rest, today’s xkcd comes impressively close (at least, I think it does) to solving the ancient philosophical riddle of how to convey what “being a nerd” feels like to someone cool since birth.

Follow

A few months ago I read Atlas Shrugged, the 1,069-page Ayn Rand opus that was recently praised by Stephen Colbert (for its newfound popularity with beleaguered CEOs).  As I mentioned in the comments of a previous post, like many other nerds I went through a brief Aynfatuation around the age of 14.  Rand’s portrayal of an anti-mind, anti-reason cabal of collectivist rulers, who spout oleaginous platitudes about love and self-sacrifice even as they mercilessly repress any spark of individuality, happens to be extremely relevant to at least two cases I’m aware of:

1. Soviet Russia.
2. The average American high school.

But it didn’t last long.  Even in the midst of it, I could see problems: I wrote a term paper analyzing the rape scene in The Fountainhead as immoral and irreconcilable with the rest of an otherwise supremely-rational novel.  And ironically, once I went to college and started doing more-or-less what Rand extols as life’s highest purposes—pursuing my ambitions, tackling math and science problems, trying to create something original—her philosophy itself seemed more and more quaint and irrelevant.  I snapped out of it before I reached Atlas.  (Or did I subconsciously fear that, if I did read Atlas, I’d be brainwashed forever?  Or did I just figure that, having read the 752-page Fountainhead and dozens of essays, I already got the basic idea?)

So, having now returned to Atlas out of curiosity, what can I say?  Numerous readers have already listed the reasons why, judged as a conventional novel, it’s pretty bad: wooden dialogue, over-the-top melodrama, characters barely recognizable as human.  But of course, Atlas doesn’t ask to be judged as a conventional novel.  Rand and her followers clearly saw it as a secular Bible: a Book of Books that lays out for all eternity, through parables and explicit exhortation, what you should value and how you should live your life.  This presents an obvious problem for me: how does one review a book that seeks, among other things, to define the standards by which all books should be reviewed?

Mulling over this question, I hit on an answer: I should look not at what’s in the book—whose every word is perfect by definition, to true believers who define ‘perfect’ as ‘that exemplified by Atlas Shrugged‘—but at what’s not in it.  In other words, I should review the complement of the book.  By approaching the donut through the hole, I will try to explain how, even considering it on its own terms, Atlas Shrugged fails to provide an account of human life that I found comprehensive or satisfying.

(Though on the positive side, it still makes much more sense than my 11^th-grade English teacher.)

Without further ado, here are the ten most striking things I noticed in the complement of Atlas Shrugged.

1. Recent technologies.  For a novel set in the future, whose whole point is to defend capitalism, technology, innovation, and industry, Atlas is startlingly uninterested in any technologies being developed at the time it was written (the fifties).  For Rand, the ultimate symbol of technological progress is the railroad—though she’s also impressed by steel mills, copper mines, skyscrapers, factories, and bridges.  Transistors, computers, space travel, and even plastic and interstate highways seem entirely absent from her universe, while nuclear energy (which no one could ignore at the time) enters only metaphorically, through the sinister “Project X.”  Airplanes, which were starting to overtake trains as a form of passenger travel even as Atlas was written, do play a tiny role, though it’s never explained where the busy protagonists learned to pilot.  Overall, I got the impression that Rand didn’t really care for technology as such—only for what certain specific, 19^th-century technologies symbolized to her about Man’s dominance over Nature.
2. Curiosity about the physical universe.  This, of course, is related to point 1.  For Rand, the physical world seems to be of interest only as a medium to be bent to human will.  When I read The Fountainhead as a teenager, I found myself wondering what Rand would’ve made of academic scientists: people who generally share her respect for reason, reality, and creative achievement, but not her metaphysical certainty or her hatred of all government planning.  (Also, while most male scientists resemble a cross between Howard Roark and John Galt, it must be admitted that a tiny minority of them are awkward nerds.)
   In Atlas, Rand finally supplies an answer to this question, in the form of Dr. Robert Stadler.  It turns out that in Rand’s eschatology, academic scientists are the worst evil imaginable: people smart enough to see the truth of her philosophy, but who nevertheless choose to reject it.  Science, as a whole, does not come off well in Atlas: the country starves while Stadler’s State Science Institute builds a new cyclotron; and Dr. Floyd Ferris, the author of obscurantist popular physics books, later turns into a cold-blooded torturer.  (That last bit, actually, has a ring of truth to it.)
   More important, in a book with hundreds of pages of philosophizing about human nature, there’s no mention of evolution; in a book obsessed with “physics,” there’s no evidence of any acquaintance with relativity, quantum mechanics, or pretty much anything else about physics.  (When Stadler starts talking about particles approaching the speed of light, Dagny impatiently changes the subject.)  It’s an interesting question whether Rand outright rejected the content of modern science; maybe we’ll pick up that debate in the comments section.  But another possibility—that Rand was simply indifferent to the sorts of things an Einstein, Darwin, or Robert Stadler might discover, that she didn’t care whether they were true or not—is, to my mind, hardly more defensible for a “philosopher of reason.”
3. Family.  Whittaker Chambers (of pumpkin patch fame) pointed out this startling omission in his review of 1957.  The characters in Atlas mate often enough, but they never reproduce, or even discuss the possibility of reproduction (if only to take precautions against it).  Also, the only family relationships portrayed at length are entirely negative in character: Rearden’s mother, brother, and wife are all contemptible collectivists who mooch off the great man even as they despise him, while Dagny’s brother Jim is the wretched prince of looters.  Any Republicans seeking solace in Atlas should be warned: Ayn Rand is not your go-to philosopher for family values (much less “Judeo-Christian” ones).
4. “Angular,” attractive people who also happen to be collectivists, or “shapeless” people who happen to be rational individualists.  In the universe of Atlas, physical appearance is destiny—always, without exception, from John Galt down to the last minor villain.  Whenever Rand introduces a new character, you learn immediately, after a one-paragraph physical description, everything she wants you to know about that character’s moral essence: “angular” equals good, “limp,” “petulant,” and so on equal bad.  Admittedly, most movies also save the audience from unwanted thought by making similar identifications.  But Rand’s harping on this theme is so insistent, so vitriolic, that it leaves little doubt she really did accept the eugenic notion that a person’s character is visible on his or her face.
5. Personalities.  In Atlas, as in The Fountainhead, each character has (to put it mildly) a philosophy, but no personality independent of that philosophy, no Objectively-neutral character traits.  What, for example, do we know about Howard Roark?  Well, he has orange hair, likes to smoke cigarettes, and is a brilliant architect and defender of individualism.  What do we know about John Galt?  He has gold hair, likes to smoke cigarettes, and is a brilliant inventor and defender of individualism.  Besides occupation and hair color, they’re pretty much identical.  Neither is suffered to have any family, culture, backstory, weaknesses, quirks, or even hobbies or favorite foods (not counting cigarettes, of course).  Yes, I know this is by explicit authorial design.  But it also seems to undermine Rand’s basic thesis: that Galt and Roark are not gods or robots, but ordinary mortals.
6. Positive portrayal of uncertainty.  In Atlas, “rationality” is equated over and over with being certain one is right.  The only topic the good guys, like Hank and Dagny, ever change their minds about is whether the collectivists are (a) evil or (b) really, really evil.  (Spoiler alert: after 800 pages, they opt for (b).)  The idea that rationality might have anything to do with being uncertain—with admitting you’re wrong, changing your mind, withholding judgment—simply does not exist in Rand’s universe.  For me, this is the single most troubling aspect of her thought.
7. Honest disagreements.  Atlas might be the closest thing ever written to a novelization of Aumann’s Agreement Theorem.  In RandLand, whenever two rational people meet, they discover to their delight that they agree about everything—not merely the basics like capitalism and individualism, but also the usefulness of Rearden Metal, the beauty of Halley’s Fifth Concerto, and so on.  (Again, the one exception is the disagreement between those who’ve already accepted the full evil of the collectivists, and those still willing to give them a chance.)  In “Galt’s Gulch” (the book’s utopia), there’s one judge to resolve disputes, but he’s never had to do anything since no disputes have ever arisen.
8. History.  When I read The Fountainhead as a teenager, there was one detail that kept bothering me: the fact that it was published in 1943.  At such a time, how could Rand possibly imagine the ultimate human evil to be a left-wing newspaper critic?  Atlas continues the willful obliviousness to real events, like (say) World War II or the Cold War.  And yet—just like when she removes family, personality, culture, evolution, and so on from the picture—Rand clearly wants us to apply the lessons from her pared-down, stylized world to this world.  Which raises an obvious question: if her philosophy is rich enough to deal with all these elephants in the room, then why does she have to avoid mentioning the elephants while writing thousands of pages about the room’s contents?
9. Efficient evil people.  In Atlas, there’s not a single competent industrialist who isn’t also an exemplar of virtue.  The heroine, Dagny, is a railroad executive who makes trains run on time—who knows in her heart that reliable train service is its own justification, and that what the trains are transporting and why is morally irrelevant.  Granted, after 900 pages, Dagny finally admits to herself that she’s been serving an evil cause, and should probably stop.  But even then, her earlier “don’t ask why” policy is understood to have been entirely forgivable: a consequence of too much virtue rather than too little.  I found it odd that Rand, who (for all her faults) was normally a razor-sharp debater, could write this way so soon after the Holocaust without thinking through the obvious implications.
10. Ethnicity.  Seriously: to write two sprawling novels set in the US, with hundreds of characters between them, and not a single non-Aryan?  Even in the 40s and 50s?  For me, the issue here is not political correctness, but something much more basic: for all Rand’s praise of “reality,” how much interest did she have in its contents?  On a related note, somehow Rand seems to have gotten the idea that “the East,” and India in particular, were entirely populated by mystical savages sitting cross-legged on mats, eating soybeans as they condemned reason and reality.  To which I can only reply: what did she have against soybeans?  Edamame is pretty tasty.

Murray Rothbard and Eliezer Yudkowsky take different routes to some of the same conclusions.

Follow

The above is a question that’s interested me for as long as I can remember, though I avoided blogging about it until now.  See, unlike many libertarian economist Ayn-Rand types, I don’t actually like asking social or political questions the very asking of which marks you as eccentric and Aspergerish.  I’d rather apply myself to proving lower bounds, popularizing quantum mechanics, or other tasks that are (somewhat) more respected by the society I depend on for my dinner.  And I’d rather pick battles, like evolution or climate change, where truth and justice have well-connected allies on their side and a non-negligible chance of winning.  For years, I’ve been studying the delicate art of keeping my mouth shut when what I have to say will be deeply unpopular—and despite lapses, I’ve actually made a great deal of progress since (let’s say) the age of 14.

There are times, though, when a question strikes such an emotional chord with me that I break down and ask it in spite of everything.  Such a case was provoked by this story in the New York Times a few weeks ago (registration required), about a 17-year-old girl who was jailed for creating a MySpace page.

At worst, Hillary Transue thought she might get a stern lecture when she appeared before a judge for building a spoof MySpace page mocking the assistant principal at her high school in Wilkes-Barre, Pa. She was a stellar student who had never been in trouble, and the page stated clearly at the bottom that it was just a joke.

Instead, the judge sentenced her to three months at a juvenile detention center on a charge of harassment.

She was handcuffed and taken away as her stunned parents stood by.

“I felt like I had been thrown into some surreal sort of nightmare,” said Hillary, 17, who was sentenced in 2007. “All I wanted to know was how this could be fair and why the judge would do such a thing.”

The answers became a bit clearer on Thursday as the judge, Mark A. Ciavarella Jr., and a colleague, Michael T. Conahan, appeared in federal court in Scranton, Pa., to plead guilty to wire fraud and income tax fraud for taking more than $2.6 million in kickbacks to send teenagers to two privately run youth detention centers run by PA Child Care and a sister company, Western PA Child Care.

The article expresses disapproval about the corruption of the judge and the severity of the sentence, but seems completely unfazed by the idea of an American citizen standing before a judge to answer for a satirical website.  And this is actually understandable given the context.  While children’s rights law is a notoriously murky area, it seems fair to say that children’s “individual rights” (free speech, due process, etc.) are generally thin to nonexistent, certainly in the US and probably elsewhere too.  So for example, if Ms. Transue had been punished by her school rather than a court for setting up her website, it probably wouldn’t even have been news.

The law strikes me as inconsistent in its attitude toward minors: first it denies them individual rights, on the ground that they’re not yet capable of exercising moral judgment.  But then it punishes them harshly for all sorts of offenses (in many cases more harshly than adults), thereby presupposing the moral responsibility they’re not yet supposed to have.

Now, if I had political capital to spend, I would not want to spend it on children’s rights, just as I wouldn’t want to spend it on legalizing marijuana.  In both cases, I’m guessing that lions will embrace vegetarianism and the polynomial hierarchy will collapse to the 23^rd level before American law changes significantly.  But I’ve also noticed an interesting difference between the two issues.  In the case of marijuana, almost every brainful person I’ve met (whether “liberal” or “conservative”) has agreed that the current American laws are an absurdity; that all the power is on one side of the issue while all the evidence and arguments are on the other side; and that eventually, one imagines this will all be as obvious to everyone as it’s obvious today (say) that contraceptives should be legal.  It’s just a question of time, of the regrettable generations-long delay between the inarguable and the acted-upon.

By contrast, when it comes to granting legal rights to children, people whose intelligence I respect seem compelled to give really bad arguments for the status quo—arguments that (so to speak) a 12-year-old could demolish.   (I know of only two famous intellectuals who’ve publicly advocated changing things: the educator John Holt and the quantum computing pioneer David Deutsch.  Anyone know of others?)

For simplicity, let’s restrict attention to the question of whether suffrage should be extended to a large class of people under 18: either by lowering the voting age (say, to 12 or 14), or better yet (in my view), by giving any citizen the vote once he or she reaches a certain age or passes a test of basic civics knowledge analogous to a driver’s-ed or citizenship test.  (Just like with the plurality voting system, showing that the current rule is terrible is the easy part; figuring out the best among many possible better rules to replace it is the harder and more interesting problem.)

I’ll also restrict attention to the US, even though most of the discussion applies more broadly.  Finally, I’ll use the word “children” to mean “children and teenagers”; I like it more than legal terms like “minors” or “people under 18.”

As John Stuart Mill pointed out in The Subjection of Women, it’s not clear how you make an affirmative case against a form of discrimination: pretty much all you can do is stand around, wait for people to suggest pro-discrimination arguments, and then answer them.

People say: should toddlers have the vote?  Should embryos?  You have to draw a line somewhere!  But the real question is: granting that one has to draw a line, granting that any line will be arbitrary and unfair, can’t one at least make it vastly, manifestly less unfair than the current line?  To give two examples: if you can be imprisoned for a crime, shouldn’t you be able to vote?  If you can demonstrate knowledge of American politics and history well beyond that of the average voter, shouldn’t you be able to vote?  (In 1971, the 26^th Amendment lowered the voting age from 21 to 18, on the ground that anyone who can be drafted into the military should be able to vote.  It seems to me that one can take that same logic much further.)

People say: if you want to grant the vote to sufficiently knowledgeable children, then shouldn’t you also take it away from sufficiently ignorant adults?  Well, it’s going to be quite a while before the glorious age of the intellectual meritocracy, when all shall submit willingly to Plato’s philosopher-kings.  And before that happens, we’ll have probably all upgraded ourselves to post-Einsteinian superintelligences anyway, by downloading the requisite applet from the iBrain store—so the question of what to do with the ignoramuses will be moot.  Until that day, I’m content to imagine something that’s merely politically impossible (like giving the vote to anyone over 18 and to all knowledgeable minors), rather than 2 to the politically impossible power.
(Notice also that slippery-slope arguments get invoked every time any new step away from medieval morality is on the table: if we legalize gay marriage, then don’t we also need to legalize polygamy, etc. etc.  Again, the fact that any rule we can think of is imperfect, doesn’t imply that some rules we can think of wouldn’t be much better than the current ones.)

People say: if you’re going to grant votes to some children and not others on the basis of a test, isn’t that elitist?  But why isn’t the driver’s-ed test or the citizenship test given to immigrants similarly elitist?

People say: even supposing they can pass some test, doesn’t everyone know that children are too immature and unwise to be entrusted with awesome burden of democracy?  Ah, and who are the mature, wise elders, those paragons of Enlightenment rationality, who twice elected George W. Bush?  If minors could vote, wouldn’t Bush have almost certainly lost both times—thereby averting (or at least mitigating) the global disaster from which we’re now struggling to recover?  Or was that a fluke: a case of the young disproportionately getting the right answer by accident, while the older and wiser made one of their rare mistakes?  Or am I being ‘reductive’ and ‘simplistic’?  Does our belief in the political immaturity of the young belong to that special category of truths, the ones too profound to be confronted by data or experience?

People say: but children only care about the present; they lack foresight.  But isn’t it children pressuring their parents to worry about climate change and the Amazon rainforest, more often than the other way around?  And isn’t that just what you’d expect, if children formed a self-interested bloc much like any other; if they grasped (some clearly, others less so) that they’d eventually run the planet, and if they consequently cared more rather than less about the distant future? So if—like me and many others—you see excessive short-term focus as the central tragedy of politics, then shouldn’t you be chomping at the bit to let more young people vote?

People say: but children will just vote however their parents tell them to.  But to whatever extent this is true, doesn’t it undercut the previous fears, of immature brats voting in Mickey Mouse for president?  And if millions of wives in conservative parts of the country still vote however their husbands tell them to, is that an argument for denying those wives the vote?  And don’t most people of every age simply vote their demographics?

People say: but only a tiny minority of precocious, high-IQ children could possibly care about voting—and while you might have a point in their case, you ignore the 99% of children who only care about the latest Hannah Montana accessory.  But if less than 1% of Americans want to run for Congress, or file a Freedom of Information Act request, or do computer security research that’s outlawed by the DMCA, does that make those rights unimportant?  At the risk of the usual charge—elitism—doesn’t the tiny minority that cares about such things tend to have a disproportionate impact on everyone else?

Also, suppose that in Victorian England, only a tiny percentage of women cared about politics rather than the latest in corsets and garden mazes: should that have carried much weight as an argument against women’s suffrage?  What if the denial of rights to a whole class of people is a reason why many in that class focus on trivialities, rather than the other way around?

People say: but it’s obvious that children shouldn’t vote, because they’re not economically self-sufficient.  Again, wouldn’t it save time to pass these arguments through the “Victorian England / women’s suffrage” filter before making them, rather than after?

People say: ah, but there’s no comparison between the two cases, since unlike Victorian women, children will be able to vote once they’re old enough.  Right, and what about the children who die before they’re 18?  Even ignoring those cases, is it obvious that it’s okay to deny people their fundamental rights, provided that those people, in turn, will someday get to deny fundamental rights to others?

People say: at any rate, denying the vote to children doesn’t seem to have any particularly bad consequences.  I wish I agreed; the reasons why I don’t are really a topic for another post.  Briefly, though, I think our culture’s insistence on treating children as children even after those children are ready to be treated as adults is

1. weird from the standpoint of anthropology and evolutionary psychology,
2. an excellent prescription for turning out adults who still think the way children are supposed to,
3. a useful tool for cracking down on unwanted precocity of all kinds, and
4. a terrific way to make up for the unfortunate encroachments these past few centuries of justice, civilized behavior, and protections for the nerdy and weak, by keeping human beings in such a savage environment for the first years of their lives that by the time they’re let out, the new Enlightenment nonsense has difficulty gaining a foothold.

(For more on similar themes, see Paul Graham’s justly-celebrated essay Why Nerds Are Unpopular, or my Return to the Beehive.)  The denial of suffrage is just a small part of the story—nowhere near the most important part—but it works as an example.

Finally people say: that’s just the way things are.  This argument—also useful for justifying chattel slavery if you happen to live in 1845—is, at last, a sound one. I agree with it and accept it.  Because of this argument, I’ll now admit that this entire post has been nothing more than an intellectual exercise, a way for me to procrastinate from answering email.  I don’t actually believe any of what I wrote—nor, for that matter, do I believe anything.  Still, purely out of academic curiosity, I’d be interested to know: are there any other arguments for the legal status of Hillary Transue, besides its being the way things are?

Follow

Today I continue a three-entry streak of praising things that are good.  While visiting IAS to give a talk, I noticed on several of my friends’ desks heavily-bookmarked copies of the Princeton Companion to Mathematics: a 1000-page volume that’s sort of an encyclopedia of math, history of math, biographical dictionary of math, beginners’ guide to math, experts’ desk reference of math, philosophical treatise on math, cultural account of math, and defense of math rolled into one, written by about 130 topic specialists and edited by the Fields medalist, blogger, and master expositor Timothy Gowers.

The best way I can explain what the PCM is trying to do is this.  Suppose that—like in the Hitchhiker’s Guide to the Galaxy—aliens are threatening to obliterate the earth along with all its life to make room for an interstellar highway.  But while the aliens are unresponsive to pleas for mercy, an exemption might be granted if the humans can show that, over the last four millennia, such mathematical insights as they’ve managed to attain are a credit rather than an embarrassment to their species.  To help decide the case, the aliens ask that humans send them an overview of all their most interesting mathematics, comprising no more than 1,000 of the humans’ pages.  Crucially, this overview will not be read by the aliens’ great mathematicians—who have no time for such menial jobs—but by a regional highway administrator who did passably well in math class at Zorgamak Elementary School.  So the more engaging and accessible the better.

I don’t know what our chances would be in such a situation, but I know that the PCM (suitably translated into the aliens’ language) is the book I’d want beamed into space to justify the continued existence of our species.

So what makes it good?  Two things, mainly:

1. For some strange reason I still don’t understand, it’s written as if you were supposed to read it.  Picture a stack of yellow books (), and imagine cornering the authors one by one and demanding they tell you what’s really going on, and the result might look something like this.  Admittedly, there are plenty of topics I still didn’t understand after reading about them here—Calabi-Yau manifolds, K-theory, modular forms—but even there, I gained the useful information that these things are apparently hard for me even when someone’s trying to make them easy.
2. The book is cheerfully unapologetic about throwing in wavelets, error-correcting codes, the simplex algorithm, and the Ising model alongside the greatest hits of algebra, geometry, analysis, and topology—as if no one would think to do otherwise, as if the former were part of the mathematical canon all along (as indeed they could’ve been, but for historical accident).  Nor does it dismay me that the book gives such a large role to theoretical computer science—with a 30-page chapter on complexity by Avi Wigderson and Oded Goldreich, as well as chapters on cryptography, numerical analysis, computability, and quantum computing (my tiny role was to help with the last).  There are also essays on computer-assisted proofs, “experimental mathematics,” innumeracy, math and art, and the goals of mathematical research; a guide to mathematical software packages; “advice to a young mathematician”; and a timeline of mathematical events, from the first known use of a bone for counting through Shor’s factoring algorithm and the proofs of Wiles and Perelman.

But enough!  I must now descend from Platonic heaven, reenter the illusory world of shadows, and finish my grant proposal … alright, maybe one more puff …

Follow

In response to my (justified) kvetching about Vista in my last post, a commenter named Matt wrote in:

I hear there’s some free operating system written by a guy from Finland. Sounds pretty crazy to me, but I hear you can just download it for free. Maybe you could have used that if you didn’t like Vista?

Yes, I’ve heard of the OS by the guy from Finland, and even tried it. On introspection, though, my feelings about Windows are pretty much identical to my feelings about America: sure, it’s big and bloated and crass and flawed and overcommercialized and buggy and insecure, and at least 95% of the insults that the sophisticates hurl at it are true. And other countries and OSes have a great deal to be said for them, and indeed I do spend much of my time visiting them. But this is home, dammit, it’s where I was brought up, and things would have to get a lot worse before I’d consider moving away for good.

All I need, then, is the Windows analogue of Obama. Would that be the Windows 7 beta? (Vista, of course, being the Windows analogue of Bush?)

Follow

A year ago, a group of CS theorists—including Eli Ben-Sasson, Andrej Bogdanov, Anupam Gupta, Bobby Kleinberg, Rocco Servedio, and your humble blogger, and fired up by the evangelism of Sanjeev Arora, Christos Papadimitriou, and Avi Wigderson—agreed to form a committee to improve Wikipedia’s arguably-somewhat-sketchy coverage of theoretical computer science.  One year later, our committee of busy academics has done, to a first approximation, nothing.

In considering this state of affairs, I’m reminded of the story of Wikipedia’s founding.  Before Wikipedia there was Nupedia, where the articles had to be written by experts and peer-reviewed.  After three years, Nupedia had produced a grand total of 24 articles.  Then a tiny, experimental adjunct to Nupedia—a wiki-based peanut gallery where anyone could contribute—exploded into the flawed, chaotic, greatest encyclopedia in the history of the world that we all know today.

Personally, I’ve never understood academics (and there are many) who sneer at Wikipedia.  I’ve been both an awestruck admirer of it and a massive waster of time on it since shortly after it came out.  But I also accept the reality that Wikipedia is fundamentally an amateur achievement.  It will never be an ideal venue for academics—not only because we don’t have the time, but because we’re used to (1) putting our names on our stuff, (2) editorializing pretty freely, (3) using “original research” as a compliment and not an accusation, and (4) not having our prose rewritten or deleted by people calling themselves Duduyat, Raul654, and Prokonsul Piotrus.

So this Thanksgiving weekend, at the suggestion of my student Andy Drucker, I’m going to try an experiment in the spirit of Wikipedia.  I’m going to post our wish-list of theoretical computer science topics, and invite you—my interested, knowledgeable readers—to write some articles about them.  (Of course you’re welcome to add your own topics, not that you’d need permission.)  Don’t worry if you’re not an expert; even some stubs would be helpful.  Let us know in the comments section when you’ve written something.

Thanks, and happy Thanksgiving!

Research areas not defined on Wikipedia

• Property testing
• Quantum computation (though Quantum computer is defined)
• Algorithmic game theory
• Derandomization
• Sketching algorithms
• Propositional proof complexity (though Proof complexity is defined)
• Arithmetic circuit complexity
• Discrete harmonic analysis
• Streaming algorithms
• Hardness of approximation

Research areas ill-defined on Wikipedia

• Algorithmic mechanism design — extend beyond 4 sentences, and create link from Mechanism design article of Wikipedia
• Circuit complexity
• Online Algorithms

Basic terms not defined on Wikipedia

• Sparsest cut
• Metric embedding — also create link from Embedding article on Wikipedia
• Price of anarchy
• Combinatorial auction
• Glauber dynamics
• Locally testable code
• Locally decodable code (but the closely related Private information retrieval is defined)
• Average case complexity
• Worst case complexity
• Polynomial identity testing
• Unique games conjecture
• Primal-dual approximation algorithm

Basic terms ill-defined on Wikipedia

• Conductance (probability) — extend beyond 3 sentences
• Probabilistically checkable proofs
• Polynomial-time hierarchy
• Algorithms for matrix multiplication
• Max-flow min-cut
• Zero knowledge proof
• Model of computation
• List-decoding

Well-known theoretical computer scientists without Wikipedia pages

• No, I’m not going to make that list … but you can.

Update (11/30): A big shout-out and thank-you to those theorists, such as David Eppstein, who’ve actually been contributing to Wikipedia and not just theorizing about it!

Follow

I’m seeking a talented student for summer of 2009, to work with me in developing and experimenting with a new open-source web application.  I’m open to students from anywhere, though MIT students will receive special consideration for funding reasons.

The web app — tentatively called “Worldview Manager” — is intended to help people ferret out hidden contradictions in their worldviews.  Think of a kindly, patient teacher in a philosophy seminar who never directly accuses students of irrationality, but instead uses Socratic questioning to help them clarify their own beliefs.

The idea is extremely simple (as of course it has to be, if this app is to attract any significant number of users).  The user selects a topic from a list, which might include the following at the beginning:

Climate Change
The Singularity
Libertarianism
Computational Complexity
Interpretation of Quantum Mechanics
Quantum Computing
Gay Rights
Israel
Gifted Education
Foundations of Mathematics
Strong AI and Philosophy of Mind
Utilitarian Ethics
Animal Rights
Art and Aesthetics

Users will also be able to contribute their own topic files.  (The above list is biased toward those topics about which I feel like I could write a topic file myself.)

After choosing a topic, the user will be presented with a sequence of statements, one at a time and in a random order.  For example, if the topic is Foundations of Mathematics, the statements might include the following:

Math is a cultural construct.
Math privileges male, linear thinking over female, intuitive thinking.
The Continuum Hypothesis is either true or false, even if humans will never know which.
There’s a sense in which integers, real numbers, and other mathematical objects “existed” before humans were around to name them, and will continue to exist after humans are gone.

The user can indicate her level of agreement with each statement by dragging the cursor.

Now the topic file, in addition to the statements themselves, will also contain lists of pairs or sometimes triples of statements that appear (at least to the writer of the topic file) to be in “tension” with one another.  From time to time, the program will search the user’s previous responses for beliefs that appear to be in tension, point out the tension, and give the user the opportunity to adjust one or more beliefs accordingly.  For example, the user might get a message like the following:

You indicated substantial agreement with the statement

If a scientific consensus on climate change existed, then society would have to act accordingly.

and also substantial agreement with the statement

The so-called “consensus” on climate change simply reflects scientists’ liberal beliefs, and therefore does not necessitate action.

These views would seem to be in tension with each other.  Would you like to adjust your belief in one or both statements accordingly?

That’s about all there is to it.  No Bayesianism, no advanced math of any kind (or at least none that the user sees).

As you may have gathered, the writing of topic files is not a “value-neutral” activity: the choice of statements, and of which statements are in tension with which other ones, will necessarily reflect the writer’s interests and biases.  This seems completely unavoidable to me.  The goal, however, will be to adhere as closely as is practical to Wikipedia’s NPOV standard.  And thus, for example, any well-written topic file ought to admit “multiple equilibria”; that is, multiple points of view that are genuinely different from one another but all more-or-less internally consistent.

The student’s responsibilities for this project will be as follows:

• Write, debug, and document the web app.  This sounds straightforward, but it’ll be important to get the details right.  I’m not even sure which development tools would be best—e.g., whether we should use Java or JavaScript, do all computation on the server side, etc.—and will rely on you to make implementation decisions.
• Write topic files.  I can create many of the files myself, but it would be great if you could pitch in with your own ideas.
• Help run experiments with real users.
• Help write up a paper about the project.

If there’s time, we could also add more advanced functionality to Worldview Manager.  Your own ideas are more than welcome, but here are a few possibilities:

• Present statements to the user in a non-random order that more rapidly uncovers tensions.
• Allow users to register for accounts, and save their “worldviews” to work on later.
• Give users the ability to compare worldviews against their friends’, with large disagreements flagged for special consideration.
• Give users the ability to use a local search or backtrack algorithm to decrease the total “tension” in their worldviews, while changing their stated beliefs by the minimum possible amount.
• Enable adaptive follow-up questions.  That is, once two beliefs in tension have been uncovered, the user can be queried more specifically on how she wants to resolve the apparent contradiction.

I’m looking for someone smart, curious, enthusiastic, and hard-working, who has experience with the development of web applications (a work sample is requested).  Grad students, undergrads, high school students, nursery school students … it’s what you can do that interests me.

I expect the internship to last about three months, but am flexible with dates.  Note that in the year or so since I started at MIT, I’ve already worked with six undergraduate students, and three of these interactions have led or will lead to published papers.

If you’re interested, send a cover letter, cv, and link to a work sample to aaronson at csail mit edu.  If you want to tell me why the Worldview Manager idea is idiotic and misguided, use the comments section as usual.

Update (10/15): In a somewhat related spirit, Eric Schwitzgebel at UC Riverside points me to a study that he and a colleague are conducting, on whether professional philosophers respond differently than laypeople to ethical dilemmas.  Shtetl-Optimized readers are encouraged to participate.

Follow

Today Sean Carroll emailed various bloggers, defying us to participate in the DonorsChoose Blogger Challenge 2008.  Here’s how it works: we (the bloggers) pick projects that we like in underfunded public schools.  Then we beg our readers to donate small amounts of money to make those projects happen.  Any blogger whose readers can’t or won’t contribute is revealed as weak, pathetic, and inadequate—as are the readers themselves.

Now, do I seem like the sort of pusillanimous coward who would back down from such a direct challenge to his bloghood?  Who would cede the moral high ground to a physicist?

I do?

Then let the word echo from the mountaintops and RSS feeds.  I, Scott Aaronson, am now seeking to raise up to $7000 for public school teachers trying to:

• Help “gifted” students, meaning those blessed with the gifts of awkwardness, alienation, and solitude.  (Note that in the US, less than 0.02% of the federal education budget goes to this lucky group.)
• Teach evolution.
• Buy Art Spiegelman’s Maus (the acclaimed graphic novel about the Holocaust, and an astonishingly un-P.C. work for the classroom).
• Buy Twain’s Huckleberry Finn, the classic and oft-censored howl against doofosity.

Twain, incidentally, was the one who wrote that “in the first place, God made idiots. That was for practice. Then He made school boards.”  The genius of DonorsChoose is that it bypasses those pinnacles of God’s handiwork, letting you route money directly to deserving teachers.

So: if, in your time reading Shtetl-Optimized, you’ve enjoyed one entry, I ask you to go here and donate $10 to a featured project of your choice.  If you’ve enjoyed ten entries, I ask you to donate $25 (you get the bulk discount).  If you’ve enjoyed every entry (!), I ask you to donate $50 (that’s the Platinum Elite Package).

If you’re currently a student or Wall Street broker, you can of course scale down your donation appropriately.

And no, this won’t save the world or even swing the election.  But … sniff … maybe Sean Carroll will finally respect me.

Update (Oct. 6): Thanks so much, everyone!  So far we’ve raised $2,049 (counting my own small contribution).

Follow

Luca and Terry Tao have already reported the tragic loss of the brilliant probabilist Oded Schramm in a hiking accident.  I didn’t know Oded, but I knew some of his great results and was deeply saddened by the news.  My heartfelt condolences go out to his friends and family.

It was two years ago that we lost Misha Alekhnovich, who I did know, in a whitewater rafting accident.  Other mathematicians and scientists lost in similar ways have included Heinz Pagels, Jacques Herbrand, Raymond Paley, Krzysztof Galicki, and Erik Rauch.  The teenage Einstein very nearly died while hiking on a mountain near Zurich.  I have more than one irreplaceable colleague who’s repeatedly courted death on the ski slopes.

I’d like to issue a plea to any mathematicians and scientists who might be reading: please go easier on the extreme outdoor activities.  Let those who live for such things demonstrate their daring by gambling their lives; those who live for the ages can find safer recreations.  The world needs more nerds, not fewer.

Follow