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
- 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
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!