Shtetl-Optimized

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

1. There’s now a popular article by Lisa Zyga at physorg.com, about my paper with John Watrous on quantum computing with closed timelike curves. On the whole, I think Zyga did an excellent job at getting the facts (such as they are) correct.

2. Challenged ballots in the Coleman vs. Franken race: you be the judge!

3. One of the unfortunate things about not updating your blog often, I find, is that people assume you’re still obsessed with the last thing you blogged about, weeks after you’ve all but forgotten about it.  As it happens, I’ve now fully recovered from the joy of the election, and am back to my normal angst-ridden equilibrium.  On the other hand, I’ve not yet recovered from the STOC deadline.

4. My quest to become more obamalike in temperament is now officially a failure.   I should try it again sometime.

Follow

On balance? I’ll take it.

Follow

(Assuming you’re eligible?)

An argument I came up with a while ago is that, in an election with N voters, the probability of your vote swaying the outcome could be expected to scale like 1/√N—but the utility to the world if your vote does sway the outcome could be expected to scale like N.  Under those assumptions, the expected utility of your vote for the world scales like √N (or -√N, depending which candidate you vote for).  So if you care about the world even ~1/√N as much as you care about yourself, you should probably vote, even though your vote almost certainly won’t change the outcome.  Indeed, the case is even stronger in the US (at least if you live in a swing state), both because the electoral college amplifies the probability of your vote mattering (see the Majority-Is-Stablest Theorem), and because of the US’s disproportionate influence on the world.

A version of the above argument was discovered independently by Peter Norvig, who—appropriately for an applied rather than theoretical computer scientist—plugs in some actual numbers, rather than considering the asymptotics as the number of voters goes to infinity.  Norvig finds an expected value of your vote to the United States of about $1 million (or $6 trillion divided by a 1 in 6 million chance of your vote mattering).  Another version of the argument was given by Andrew Gelman, who points out that other people’s votes are actually not well-modeled by unbiased coin flips (unless you live in Florida, I guess)—but that even under a more realistic prior, your vote still has a constant expected value to society (i.e., it doesn’t decrease with the number of voters N).

I’m aware, of course, that the above is merely a nerdy, rational argument, of a sort that’s probably never actually convinced anyone in the entire history of the world, with the possible exception of Robin Hanson.  So let me raise the stakes a little.  Let me give you an emotional argument.

Did you see WALL-E?  My favorite scene in that predictably-excellent movie—a scene I confess almost brought me to tears—actually had nothing to do with WALL-E or his robo-love-interest EVE.  It was the scene aboard the spaceship Axiom, where the leaf symbol starts flashing overhead, indicating that the earth is once again able to support life, and the fat, coddled human passengers actually have to make a decision about whether to return to earth or not.  For the first time in 700 years, the spaceship’s course is not on autopilot.  Like children away from their parents, the humans face the terrifying realization that there’s no longer any higher authority to tell them what to do.  Or rather, their robot masters are trying to tell them what to do, but the humans are not obliged to listen.

See?  Just like an election.

Your vote almost certainly won’t change the outcome; indeed, thanks to the wonders of technology, there’s probably no way to verify it’ll even be counted.  But on the one day when that leaf is flashing … to have to tell posterity you were too busy finishing a problem set?

Naturally, I also think I know which way you should vote.  But even if you’re one of the humans who thinks the spaceship carrying the last remnant of humanity should remain floating in space—since although (and here I’m embellishing the movie) the spaceship’s power will soon run out, leaving all the humans dead, it’s conceivable that the power could be extended a few years by drilling a nearby asteroid (drill, baby, drill!)—even if that’s your belief system, still I think you should vote.  Why?  Because of my newfound Zen-like equanimity, combined with the belief that your candidate’s going to lose anyway.

Then, after you’ve voted, go into the comments section and ask me a question about what’s new in computational complexity.  As a commenter on my last post helpfully opined, it’s time to start tending my garden again.

Yes We Can.  Prove We Can’t.

Follow