Shtetl-Optimized

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

A reader named Hernan asked me for my opinion of a well-known rant by Jonathan Katz of Washington University, about why young people shouldn’t go into academic science since there are so few jobs and the jobs that there are stink anyway. I posted my response in the comments section, but since it seems to be of general interest I thought I’d make a proper entry of it.

Katz is correct that opportunities in academic science (at least in the US) are much scarcer than they were during the Cold War; I think government shortsightedness deserves a huge part of the blame for that. On the other hand, countless would-be grad students have already followed the invisible hand and taken Katz’s advice, and are doing quite well in Wall Street, Silicon Valley, etc. So the ones going to grad school are mostly the ones willing to assume the (by now well-known) risks: if they weren’t, they wouldn’t be there.

My fundamental disagreement with Katz is that I think PhD work is increasingly excellent preparation for industry careers. Of course, in some cases (e.g. a quantum computing PhD going to work for an Internet startup), it’s hard to argue that the PhD provides much beyond general skills like analytical thinking, teamwork, project completion, etc., and that those skills couldn’t just as well be obtained elsewhere. But even in those cases, I think a PhD at least won’t hurt your chances in industry these days (notwithstanding Phil Greenspun’s PhD expunging service). So what the PhD does is to give many people an opportunity to spend six years advancing human knowledge and doing something they enjoy, before switching to something that’s actually rewarded by the economy. (One corollary is that, if you’re not enjoying grad school, then you shouldn’t be there. But this is just an instance of a general rule: don’t choose a career option that causes you years of suffering in the hope that the suffering will end later; it probably won’t.)

Furthermore, if there used to be a stigma attached to leaving grad school for industry, I think that’s basically vanished, and that now many PhD programs even see training students for industry as a fundamental part of their mission.

I can’t comment on the rest of Katz’s complaints (the need for conformity, the burden of writing grant proposals, etc.), except to say that so far, my own experience has been more positive. Maybe the worst is ahead!

Incidentally, my comments apply most clearly to computer science PhD programs, which are what I’m most familiar with, but I believe they also apply to physics and other sciences. As for humanities PhD’s … dude, you’re on your own.

Follow

Yesterday several people asked my opinion of a preprint claiming to solve the Graph Isomorphism problem in deterministic polynomial time. I responded:

If I read all such papers, then I wouldn’t have time for anything else. It’s an interesting question how you decide whether a given paper crosses the plausibility threshold or not. For me personally, the AKS “PRIMES in P” paper somehow crossed it whereas this one somehow doesn’t.

Of course, I’d welcome an opinion from anyone who’s actually read the paper.

Three commenters wrote in to say the paper looked good. Then the author found a bug and retracted it.

Update (1/5): Laci Babai writes in to tell me that’s not quite what happened. See here for what did happen, and here for an argument that Friedland’s approach would if sound have implied P=NP.

My purpose here is not to heap embarrassment on the author: he’s a serious mathematician who had a well-defined and interesting approach, and who (most importantly) retracted his claim as soon as a bug was discovered. (Would that everyone did the same!) Though the stakes are usually smaller, similar things have happened to most of us, including me.

Instead I want to explore the following metaquestion: suppose someone sends you a complicated solution to a famous decades-old math problem, like P vs. NP. How can you decide, in ten minutes or less, whether the solution is worth reading?

For a blogger like me — whose opinions are both expected immediately and googlable indefinitely — this question actually matters. Err in one direction, and I’ll forever be known as the hidebound reactionary who failed to recognize some 21^st-century Ramanujan. Err in the other direction, and I’ll spend my whole life proofreading the work of crackpots.

A few will chime in: “but if everyone wrote out their proofs in computer-checkable form, there’d be no need for this absurd dilemma!” Sure, and if everyone buckled up there’d be fewer serious accidents. Yet here’s the bloodied patient, and here we are in the emergency room.

In deciding whether to spend time on a paper, obviously the identity of the authors plays some role. If Razborov says he proved a superlinear circuit lower bound for SAT, the claim on our attention is different than if Roofus McLoofus says the same thing. But the danger of elitism is obvious here — so in this post, I’ll only be interested in what can be inferred from the text itself.

Inspired by Sean Carroll’s closely-related Alternative-Science Respectability Checklist, without further ado I now offer the Ten Signs a Claimed Mathematical Breakthrough is Wrong.

1. The authors don’t use TeX. This simple test (suggested by Dave Bacon) already catches at least 60% of wrong mathematical breakthroughs. David Deutsch and Lov Grover are among the only known false positives.

2. The authors don’t understand the question. Maybe they mistake NP≠coNP for some claim about psychology or metaphysics. Or maybe they solve the Grover problem in O(1) queries, under some notion of quantum computing lifted from a magazine article. I’ve seen both.

3. The approach seems to yield something much stronger and maybe even false (but the authors never discuss that). They’ve proved 3SAT takes exponential time; their argument would go through just as well for 2SAT.

4. The approach conflicts with a known impossibility result (which the authors never mention). The four months I spent proving the collision lower bound actually saved me some time once or twice, when I was able to reject papers violating the bound without reading them.

5. The authors themselves switch to weasel words by the end. The abstract says “we show the problem is in P,” but the conclusion contains phrases like “seems to work” and “in all cases we have tried.” Personally, I happen to be a big fan of heuristic algorithms, honestly advertised and experimentally analyzed. But when a “proof” has turned into a “plausibility argument” by page 47 — release the hounds!

6. The paper jumps into technicalities without presenting a new idea. If a famous problem could be solved only by manipulating formulas and applying standard reductions, then it’s overwhelmingly likely someone would’ve solved it already. The exceptions to this rule are interesting precisely because they’re rare (and even with the exceptions, a new idea is usually needed to find the right manipulations in the first place).

7. The paper doesn’t build on (or in some cases even refer to) any previous work. Math is cumulative. Even Wiles and Perelman had to stand on the lemma-encrusted shoulders of giants.

8. The paper wastes lots of space on standard material. If you’d really proved P≠NP, then you wouldn’t start your paper by laboriously defining 3SAT, in a manner suggesting your readers might not have heard of it.

9. The paper waxes poetic about “practical consequences,” “deep philosophical implications,” etc. Note that most papers make exactly the opposite mistake: they never get around to explaining why anyone should read them. But when it comes to something like P≠NP, to “motivate” your result is to insult your readers’ intelligence.

10. The techniques just seem too wimpy for the problem at hand. Of all ten tests, this is the slipperiest and hardest to apply — but also the decisive one in many cases. As an analogy, suppose your friend in Boston blindfolded you, drove you around for twenty minutes, then took the blindfold off and claimed you were now in Beijing. Yes, you do see Chinese signs and pagoda roofs, and no, you can’t immediately disprove him — but based on your knowledge of both cars and geography, isn’t it more likely you’re just in Chinatown? I know it’s trite, but this is exactly how I feel when I see (for example) a paper that uses category theory to prove NL≠NP. We start in Boston, we end up in Beijing, and at no point is anything resembling an ocean ever crossed.

Obviously, these are just some heuristics I’ve found successful in the past. (The nice thing about math is that sooner or later the truth comes out, and then you know for sure whether your heuristics succeeded.) If a paper fails one or more tests (particularly tests 6-10), that doesn’t necessarily mean it’s wrong; conversely, if it passes all ten that still doesn’t mean it’s right. At some point, there might be nothing left to do except to roll up your sleeves, brew some coffee, and tell your graduate student to read the paper and report back to you.

Follow

and at least over here

Not a blogger is stirring

The reason is clear

Follow

When I first saw the headline, I assumed it was from The Onion or (more likely) some local MIT humor publication. But no, it’s from the Associated Press.

Follow