Missing Wikipedia articles

Question

Which missing TCS topics on Wikipedia would you most like there to be an article about?

They could be glaring omissions or just topics you think should really have an article.

One topic per answer please so that the most wanted ones can be voted up.

Update 5/2/2017: Shuchi Chawla is leading an effort to improve TCS coverage on wikipedia. I'm adding this update in the hopes that people will update their answers as appropriate, add more answers, and/or contribute to the effort!

If you don't restrict the possible topics to TCS related, then this question is off topic. — Tyson Williams, Sep 07 '11 at 20:36
@Tyson Williams: The question is now edited to explicitly ask for TCS topics. — WSSW, Sep 07 '11 at 20:42
I think it could be ok if it gives a list of topics for people to work on. — Suresh Venkat, Sep 07 '11 at 20:59
Why are you asking? What do you plan to do with the answer? — Jukka Suomela, Sep 07 '11 at 21:19
I think this can be OK, something similar to these MO question: Books you would like to read (if somebody would just write them...) or A Book You Would Like to Write — Kaveh, Sep 08 '11 at 01:51
interaction with wikipedia is always nice. Note that we are starting to show up as a source in wikipedia. — Artem Kaznatcheev, Sep 08 '11 at 04:37
@Kaveh one possible issue: this same exact question (with the obvious minor changes) was also asked (and closed!) on math.SE and physics.SE. — Artem Kaznatcheev, Sep 08 '11 at 04:40
@Artem, thanks, I checked them. I agree that this is not the best way of using the site, but I think it is OK. (I don't think we are ranking anything here nor polling, and the fact that there is also a Wikipedia page for articles that should be written doesn't mean we should not ask what is missing from the list there. In any case, if anyone wants to continue discussing the question please it is better to start a meta discussion.) — Kaveh, Sep 08 '11 at 05:32
@Artem that's neat: along with our generally high google rank, these are good signs. — Suresh Venkat, Sep 09 '11 at 16:19
It isn't missing, but the PCP Theorem article is rather scant and could use a lot of elaboration and context to explain why it is so important. The section on hardness of approximation fails to explain the connection between "traditional" PCP and hardness of approximation, and would be greatly improved by an example showing how to use PCP to prove a hardness of approximation result. There is a hardness of approximation page, but it too is severely lacking in details and examples: https://en.wikipedia.org/wiki/PCP_theorem https://en.wikipedia.org/wiki/Hardness_of_approximation — Stella Biderman, May 03 '17 at 17:36

score 22 · Answer 1 · answered Sep 07 '11 at 20:43

22

Some missing topics from my collection of graph algorithms articles:

Dynamic graph algorithms
K shortest paths
Spanners and approximate shortest path data structures

Also, not so much missing topics, but a lot of the articles on topics covered by undergraduate algorithms classes kind of look like they were written by students in those classes. There's a deeper level of understanding missing, and they take a dogmatic point of view that reflects a single textbook rather than a synthesis of multiple sources. More expert help there could be useful.

answered Sep 07 '11 at 20:43

David Eppstein

50,990
3
170
278

I didn't know you could make books like that with wikipedia! That is really awesome! – Artem Kaznatcheev Sep 08 '11 at 05:04
9

Thanks for all your hard work in making this part of Wikipedia the most convenient online resource for graph theory. – András Salamon Sep 08 '11 at 09:09

score 6 · Answer 2 · answered Sep 07 '11 at 20:54

6

I would love a Wikipedia page on the Abstract Tile Assembly Model.

answered Sep 07 '11 at 20:54

Aaron Sterling

6,994
6
42
74

score 4 · Answer 3 · answered Sep 07 '11 at 21:51

4

The entry on the Johnson-Lindenstrauss Lemma lacks a complete set of references, and might also benefit from a high level explanation of the different types of algorithms available.

answered Sep 07 '11 at 21:51

Suresh Venkat

32,071
4
95
271

score 4 · Answer 4 · answered Sep 09 '11 at 07:45

The current article on computational topology covers only one small (but important!) subfield. Other subfields are covered in topological data analysis, topological graph theory, discrete exterior calculus, and possibly even topological quantum computing. But even combined, the resulting article would be incomplete.

Yes, yes, I know.

Missing Wikipedia articles

4 Answers4