Wanted: Better Wikipedia coverage of theoretical computer science
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
Comment #1 November 26th, 2008 at 9:50 pm
Seven Wonders of the Internet
(1)ArXiv
(2)Wikipedia
(3)CTAN
(4)Netlib
What would you add to this list?
Comment #2 November 26th, 2008 at 9:58 pm
rrtucci: I assume you left out the Complexity Zoo by mistake.
Comment #3 November 26th, 2008 at 10:12 pm
Scott, it seems a fundamentally bad idea to form a committee to improve Wikipedia. I am rather surprised that you were party to this decision, given that you have had experience managing wikis like Complexity Zoo.
The whole issue of using Wikipedia for academic dissemination is one that I have had trouble with in the past, but I remain confident that we’ll all converge to some resolution about how stale some research must be before Wikipedia does not consider it original any more.
To some extent, arXiv and other pre-print servers fill in a useful gap between slow and rigorous peer review and fast and loose Wiki editing. Is the lack of advanced research topics on Wikipedia really hurting?
Re having articles about notable TCS researchers, the best way to satisfy Wikipedia’s notability guidelines is to be interviewed by some mainstream media outfit, even your campus newspaper. Writing articles, peer-reviewed or otherwise, does not help due to the Conflict of Interest and Circular Argument clauses, and being called notable by other TCS researchers could fall afoul of the Mutual Admiration Clique clause. Another way to get a Wikipedia article without trouble is to name some number or property after yourself and get it listed on Wolfram MathWorld (like the Shrikhande graph for instance).
Comment #4 November 26th, 2008 at 11:21 pm
As a beginning graduate student, contributing to Wikipedia was extremely valuable to me as a way to learn about the topics I was contributing to, the same way that you understand your own research better if you explain it to someone.
I think the most effective way to improve TCS coverage would be for professors to encourage their advisees to contribute, since students get something out of it, have more time on their hands and less of an urge to put their name on things.
Comment #5 November 26th, 2008 at 11:59 pm
Arvind beat me to the same point :). There was a course overat UIUC where one of the main tasks for students was to focus on updating a particular section of Wikipedia (I think the course was on expanders).
Doing this as part of a class project (rather than making students do the usual pointless projects) might be an effective way of getting some improvements. In fact, I’ll probably experiment with something like this for my computational geometry class next semester, after I compile a similar list of under-informed topics.
It’s easy to grade such a project, and it’s even easier for students to update the material. Right now, I have students do this on a private wiki for material they present in class, but of course this could easily be done on wikipedia directly.
Comment #6 November 27th, 2008 at 12:02 am
“Writing articles, peer-reviewed or otherwise, does not help due to the Conflict of Interest and Circular Argument clauses, and being called notable by other TCS researchers could fall afoul of the Mutual Admiration Clique clause…”
Foo, how are these not fundamental terms/areas in mathematics and computer science? Why should the popular press (nevermind Wolfram Research) be in charge of deciding what’s relevant? Sounds like a race to the bottom.
Let the Wikipedia community peer review it. It should be large and robust enough to route out the kind of nonsense you might find in an Elsevier journal.
Comment #7 November 27th, 2008 at 12:06 am
Speaking of which, I noticed this morning that El Naschie (now former editor of “Chaos, Solitons, and Fractals”) was finally featured in the latest issue of Nature Magazine. 🙂
Comment #8 November 27th, 2008 at 12:21 am
As a grad student, Wikipedia is often the first place I go to get a quick definition/feel for an area/concept. As Scott’s pointed out, it’s often hit or miss when it comes to TCS. This likely makes the field much less accessible to those in other areas of CS. In short, even academics who question Wikipedia’s value should take their field’s entries seriously.
To this end, I believe the shortcomings of TCS wikipedia entries could be quickly overcome if professors simply asked their students to fill in some gaps. Specifically, when a first/second year graduate student is learning about a topic for their reading and research, why not ask them to solidify their understanding by proposing improvements to one or two lacking entries. If the professor approves of the suggested improvements, they can both make the change together.
This simultaneously addresses two major reasons why folks in TCS don’t edit Wikipedia because namely that they 1) are not confident in their authority on a particular topic, and 2) are busy and worry that the changes they make will go to waste. By having a student take a first stab at the edit, and a professor edit their work, the professor saves a lot of time, and the student can be confident their changes.
Furthermore, the students time is very well spent, as they gain experience producing a clean write up with good notation. This is not only good practice for paper/lecture writing, it’s also a way for young graduate students to immediately produce writing that is valuable to their field. Furthermore, they will get credit for their work, at least in the eyes of their professor.
Comment #9 November 27th, 2008 at 12:22 am
You know, i’m looking at the Complexity Zoo and i like how the contains, is-contained and if-then scenarios seem to be parsable. Maybe this data could be gathered and placed in a nice database (is there one already?).
It would be great to see a picture of all the complexity classes, given some assumptions, e.g. that AvgP = DistNP (whatever these classes are) – drawings of related classes would already be something. You could propagate assumptions and check for inconsistencies, check scenarios, etc. This type of contains/is-contained data is so easily handled. If the Complexity Zoo had a formally formatted version how cool would that be – i _want_ this.
Comment #10 November 27th, 2008 at 12:30 am
Also, it might be a nice tradition for an advisee, *AFTER* getting their PhD, to fill in the Wikipedia entry for their advisor. Certainly no advisee should be asked to do, but after the fact, it’s kind of a nice gesture (and certainly after 5+ years as a grad student, their authority on the subject will not be called into question)
Comment #11 November 27th, 2008 at 1:09 am
You know, while you’ve been forming committees, some of us have actually been working on improving Wikipedia.
EERac#10: I think advisor-advisee is still too much of a conflict of interest. How about you pick someone you haven’t worked with and make an article for them instead. I have a list of a few people I’d like to see articles for here, for instance, but I haven’t added an article for one of my top priorities (Goodrich) because I’m too close to him. Also, see our guidelines on what makes an academic notable enough to write an article about; your new article will stand a much better chance of survival if you pay attention to these criteria and incorporate sources and information into your article that demonstrate that the academic in question passes the guidelines. The guidelines are a bit crude compared to the typical tenure review, clearly, but we need something to keep Wikipedia being flooded by articles from thousands of self-promoting and not-yet-notable junior academics and they work pretty well in practice for that purpose.
But really, what Wikipedia doesn’t need for better coverage of TCS is more short articles saying that so-and-so is a professor at such-and-such university; it needs articles on the content of their research. Scott’s wishlist seems like a good step in getting more of that done.
Comment #12 November 27th, 2008 at 7:48 am
Grreat initiative Scott!
Perhaps it will be useful to add a list of good wikipedia entries in TCS. A comprehensive list will be great, and just a short list of “role models” can also be good.
Comment #13 November 27th, 2008 at 8:37 am
Why not expanding on http://www.scholarpedia.com ?
Comment #14 November 27th, 2008 at 12:06 pm
As soon as I read the first paragraph of this post, I was about to mention David Eppstein myself. On several occasions when I found an article was particularly well-written (and with great figures :-)), I have clicked on “revision history” and found him as one of the contributors. I have also noticed many edits by arvindn above; I haven’t noticed any edits by anyone on the committee 😛
Comment #15 November 27th, 2008 at 12:10 pm
As others have said above, professors should encourage students to improve every year the Wikipedia articles related to the topics they are studying. This will help them understand the topic and at the same time improve Wikipedia. At some point the articles in Wikipedia will be as good or better than any textbook out there.
Wikipedia is not a place for self promotion. So, don’t worry if your name is not in it. That is what Journals are for. One has to leave the ego out when going into Wikipedia. Perhaps the users “Duduyat, Raul654, and Prokonsul Piotrus” are also professors or grad students working on topics related to the article. In Wikipedia what counts is not the name but the information you provide: accurate and reliable (citations).
To finalize, I think the mistake was creating a “committee” outside from Wikipedia to improve Wikipedia. That committee should have been created inside it. After people had started editing and getting involve. Once that is done, then you can form your “virtual committee” inside Wikipedia.
Comment #16 November 27th, 2008 at 1:31 pm
A suggestion– Rather than promoting writing articles for Wikipedia, why not start with a smaller project of adding lists of useful external references to existing articles? Doing that has various advantages– First, it’s a focussed task that should be faster and easier than writing a pedagogically sound article. Second, if you really want to write an article, you can go ahead and write one and then cite yourself. And third, there’s virtually no chance of being edited by amateurs– everyone agrees that more references in a Wikipedia article are a good thing.
Comment #17 November 27th, 2008 at 9:23 pm
Sorry this is off topic, but I need help with inequalities, and complexity theorist are very good at that.
Suppose X is a random variable.
According to Jensen’s inequality
(E[X])^2
Comment #18 November 27th, 2008 at 9:35 pm
Second attempt:
Sorry this is off topic, but I need some help with inequalities, and complexity theorists are very good with inequalities
Suppose X is a random variable. According to Jensen’s inequality, $latex (E[X])^2 \leq E[X^2]$. Is there some nice upper bound $latex E[X^2]\leq f(E[X])$, for some function f, assuming X is non-negative.
Related question: is there some nice table or repository of mathematical inequalties on the internet. RGMIA used to have one, but I can no longer find it.
Comment #19 November 27th, 2008 at 10:01 pm
rrtucci says: Suppose X is a random variable. According to Jensen’s inequality, $latex (E[X])^2 \leq E[X^2]$. Is there some nice upper bound $latex E[X^2]\leq f(E[X])$, for some function f, assuming X is non-negative.
There can be no such function, since the lhs can be infinite even if the rhs is finite (e.g., X is a positive integer i with probability 1/(i^3 zeta(3)).
Comment #20 November 27th, 2008 at 11:33 pm
The state space of the probability distribution is finite, and 0\leq X \leq 1.
Comment #21 November 27th, 2008 at 11:34 pm
rrtucci: You can use < and >. Sorry about that.
Comment #22 November 27th, 2008 at 11:56 pm
Oh. Once you scale X so that all 0\leq X\leq 1 then E[X^2]\leq E[X}
Comment #23 November 28th, 2008 at 5:58 am
Basically, “what David said.” Improving Wikipedia is hard work, but it’s done inside Wikipedia, which has very well-thought out mechanisms for collaboration, topic selection, etc.
I can see only very few things that the CS community can to from the outside, maybe apart from raising awareness and respect. But let me try.
1. We might want to improve peer recognition. David and some others are doing extremely good work, and as a community we might want to think about mechanisms for rewarding this kind of activity (here I include blogging, writing pop-sci articles and books, as long as they aren’t written with too many occurrences of the first person singular pronoun, etc.)
2. An anonymous comment on Lance’s blog final-stoc-post made me think that we as a community missed a great opportunity when the Encyclopedia of Algorithms was produced. We (the content providers) could have decided to also release this things on Wikipedia, thereby laying the foundations for potentially useful articles on a lot of topics. I don’t know if that would have worked with Springer, but it’s at least an issue where committee work would have been usefully leveraged.
3. In a similar vein, the A compendium of NP optimization problems is in terrible state. Much the Complexity Zoo, I think this information would benefit from begin collaboratively edited. The information is crisp, verifiable, and already presented in a strict format. One potential way to include it in Wikipedia is to create infoboxes like for chemical elements (see Helium) with each computational problem. By migrating the Compendium to Wikipedia we would immediately produce a lot of very good content that would actually be useful to us as well. Again, this requires a decision at “community level”, possibly even involving a publisher, so it’s something that isn’t well handled at the level of an individual Wikipedian.
Comment #24 November 28th, 2008 at 8:21 am
“Seven Wonders of the Internet
[…]
What would you add to this list?”
5) OEIS (http://www.research.att.com/~njas/sequences/)
6) NUMDAM (http://www.numdam.org/)
7) MSRI (http://www.msri.org/communications/)
bonus: archive.org
Comment #25 November 28th, 2008 at 8:32 am
There are loads of nice lecture notes on various topics. Is there a way to convert it to more accessible wiki pages. Though this does involve a lot of work it could make things faster and easier.
Comment #26 November 28th, 2008 at 9:34 am
Hmmm … Scott, it sure sounds like your committee had in mind to do for complexity theory some of things that “steeluniversity.org” is doing for the global steelmaking industry.
Steeluniversity.org provides a “comprehensive package of highly interactive, informative, innovative, integrated and sophisticated e-learning resources on steel technologies, covering all aspects of iron and steelmaking processes through to steel products, their applications and recycling.”
And steeluniversity.org seems to be impressively successful at achieving this goal.
Suppose we ask, why can’t we simply substitute “all aspects of complexity theory through to practical applications, jobs for young people, and societal impact” for “all aspects of iron and steelmaking processes through to steel products, their applications and recycling”?
The above question is somewhat tongue-in-cheek, but it suggests a reasonable question: what fundamental obstructions (if any) prevent the complexity theory community from embracing a comparably comprehensive and integrated education program?
Because after all, isn’t identifying obstructions the first step to overcoming them?
Lest folks scoff, I will note that solving the practical problems that arise in steelmaking is *not* easy … many of the classical problems of complexity theory are embedded therein.
Comment #27 November 28th, 2008 at 1:43 pm
There is a lot of high quality resources for TCS on the web (among them of course Scott’s courses and articles).
I don’t wish to deny the value of enhancing Wikipedia’s content, and I do use it a lot, but what exactly should be the added value when compared to other online material ? Should the articles, for example, strive to be as self-contained as possible as opposed to the material present in online lectures where the content of one lecture often depends on the previous one ?
Or does one hope to produce ultimately something much more detailed and expanded than the online lectures and articles by academics, thanks to the (potentially) much larger number of contributors ?
Comment #28 November 28th, 2008 at 3:58 pm
Maybe the best solution is to have short articles on wikipedia that present the most common aspects of a topic and link to reliable sites (where one can look to for more in-depth information) instead of long in-depth articles that have no links and are more subject to misinformation. This because:
1. It makes it easier to navigate the wikis.
2. It makes it easier to maintain and correct pages.
3. It leaves the in-depth content in sites that have some expertise on the topic.
4. It doesn’t duplicate what’s already available.
5. Gives the user more choice for in-depth content.
6. It gives credit to the authors that have expertise in the topic (in the form of a link to pages on their sites).
Comment #29 November 28th, 2008 at 6:17 pm
Last semester two students wanted to get graduate credit when taking my undergraduate Algorithms course. The extra work I gave them to get graduate credit: write an entry on wikipedia.
Comment #30 November 29th, 2008 at 2:45 pm
The STOC and FOCS conferences are each missing Wikipedia pages.
Comment #31 November 29th, 2008 at 3:40 pm
Hey, I made the walksat page on wikipedia not be completely wrong a while back. That’s something, although it’s a bit odd that much more fundamental issues in computational complexity don’t have real pages. The physics and chemistry pages on wikipedia are quite a bit better.
Comment #32 November 29th, 2008 at 3:46 pm
“(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”
Sounds like wikipedia may just not be the appropriate venue for contributions from academia. Have you considered using Knol?
Comment #33 November 29th, 2008 at 4:22 pm
I think you guys are really making this out to be harder than it is. If you look at the whole of wikipedia, the task is unimagnably daunting. There are over a million articles that need to be cleaned up in some fashion. Whole swathes of knowledge and learning are under-represented. The articles that Wikipedia presents on the main page represent less than 1/2 of one percent of the total articles on the site.
But wikipedia doesn’t work by confronting this mess as a whole (assuming you accept the proposition that wikipedia works). We work by tackling small portions of it piecemeal and allowing (hopefully) interested parties to make contributions in their sphere of competence. Projects like Wikipedia:Spotlight within the project suffer from chronically low participation, while projects that funnel individual effort on disparate subjects are often well attended.
My suggestion is for you to exhort students and advisees to take a closer look at wikipedia. A common refrain I still here from academics is that wikipedia is to be avoided like the plague–no doubt this is to stop students from citing it as they would a reliable source. The problem is that this true statement (that wikipedia is not a reliable source for academic or legal work) becomes conflated with the larger, less accurate statement (that wikipedia is dismal or unreliable more generally).
I see David has already commented above, and I second his remarks. Work on content, not people. Cite material from textbooks (or published articles) or (assuming you are published in the field) your own website! Don’t worry about wikipedia’s citation system. Just cite author-date as you would normally and give the book information at the end of the article. Getting caught up in the CiteWeb vs. Harvard vs. whatever else isn’t helpful. Remember to write as though no one knows who you are. And register an account. As much as we hope to be open to editing by everyone under all circumstances we are not. Some pages are protected from anonymous editing and some editors view changes by anonymous editors as more suspect than changes by registered editors. Also, if you log in from a school address, those may be blocked for periods of time (as you share an IP with the frat boy in the union writing “poop” on the Math page.
As for why Wikipedia versus some other information aggregation site? Well, for starters…we’re the biggest. Information you add there (and pages you fix there) are more likely to help your graduate and undergraduate students when they inevitably click on wikipedia looking for something. Second, since Wikipedia is released under the GFDL (Soon to be CC 3.0), what you add there is available for anyone to use, for any purpose.
Ok, enough of my sales pitch. 🙂
Comment #34 November 29th, 2008 at 4:33 pm
Google Knol is the appropriate venue and not wikipedia. Wikipedia is an ENCYCLOPEDIA written by 12 YEAR OLD MONKEYS. Its just not meant for serious knowledge gathering and relies on the too many cooks DONT spoil the broth principle. For serious discourse, go elsewhere. Somewhere you can control the knowledge and not let entropy destroy it.
Own your content, put your name and reputation on the line and further human knowledge. Dont let random surfers gradually destroy your work for no other reason than to get brownie points for edits.
Comment #35 November 29th, 2008 at 4:53 pm
Been there done that…
As someone once made me an article topic on Wikipedia and I decided to finally correct some errors and elaborate on the original focus (which was a project of mine and not me) by my creating a wikipedia page on the subject matter of the project.
It was removed under the “original research argument” even though the simple proof is found in trying to avoid the actions I identified.
So…. I created my own site for it and have since expanded it some.
http://abstractionphysics.com
What is commonly second nature to us, is not so second nature to computers. But what a reflective mirror it would make to provide the means to do so.
Comment #36 November 29th, 2008 at 5:59 pm
Out of curiosity i did a very rough scan for complexity class containment relations in the Complexity Zoo and graphed any relationships that the scanner could extract:
http://gdocs.latexlab.org/static_images/ZooGraph.png
If this information was in a more formal and parsable format (including the what-if scenarions such as “if Class1 = Class2 then Class3 = Class4 by Paper5”) better visualization and some class information could be generated on the fly.
This isn’t for or against Wikipedia/Knol articles obviously, i’m just wondering if anyone else would see any value in having a more formal system for storing complexity class relationships and other class information in a queryable format.
Comment #37 November 29th, 2008 at 6:55 pm
Wikiversity. 🙂
Comment #38 November 29th, 2008 at 7:10 pm
The problem with wikipedia is that the “corrections” unqualified people make while hiding behind their usernames are often unquestionably wrong. As a professor of computer science, I’d just contributed to an article in my research area, and I was pretty annoyed to see some anonymous (probably high school) kid with too much free time overwriting my changes with something false because he incorrectly thought he knew better.
And authors of fiction who use pen names are irrelevant to this because Mark Twain was using his name to write stories, not to assert any sort of scientific expertise. George Eliot wasn’t using the name to publish incorrect “facts” in the Encyclopedia Britannica, but maybe ‘duduyat’ was doing exactly that in Wikipedia and yet his “opinions” about something objectively true or false were given equal weight.
Comment #39 November 29th, 2008 at 7:34 pm
Doc#36: re your “As a professor of computer science, I’d just contributed”: one aspect (I hesitate to call it either a bug or a feature) of Wikipedia is that credentialism of this sort doesn’t get you very far. If you are in a dispute with someone over whether your take or theirs is correct, you need to back it up with published sources. Although this can be quite annoying to those of us who do have the credentials, the effect of this sort of dispute can often be that the sources go into the articles, and that the writing gets redone to make it harder to misinterpret and mistakenly “correct,” leading to a net improvement. And if you do have the credentials, you also know how to find the sources that will help you win these disputes on non-credentialist grounds.
Comment #40 November 29th, 2008 at 7:48 pm
regrettably it doesnt. edit wars and deletionists patrol wikipedia and remove published and well sourced material as easily as unverified material.
there arent any checks and balances.
Comment #41 November 29th, 2008 at 7:59 pm
Not worth it.
Mob mentality rules on a social encyclopedia. If 1 expert knows something to be true, 100 idiots who agree with each other can rewrite their own version of that truth.
Comment #42 November 29th, 2008 at 8:49 pm
I really do not agree with the comments which seem to claim that the presence of unqualified editors in wikipedia makes it worthless. It has plenty of great articles. Personally, I understood many mathematics related topics from it. For example see the page on Kalman Filter. Or see the article on confidence intervals. In my opinion, the textbooks that have such a clear and detailed explanation are rare.
Comment #43 November 29th, 2008 at 9:47 pm
Great suggestion Scott! It would be good if Wikipedia contained much much more useful info on theoretical computer science.
What I often miss when looking at Wikipedia entries are mathematical proofs – I see no reason why 1-2 page proofs shouldn’t be in the article. Also, the links for more information are often not ideal. There are a lot of great lecture notes and survey articles available on the web on particular topics, but they’re not always easy to find. The Wikipedia entry for a topic could be a natural place to include these links.
Anyway, just wanted to say that if anyone takes Scott on his challenge, feel free to use anything I’ve written including my lecture notes and the draft complexity book with Sanjeev Arora that’s available on my web site.
–Boaz
p.s. I also disagree with the disparaging of Wikipedia. The mere fact that many fundamental TCS concepts have no entries at all shows that there’s no army of trolls out there looking to destroy any entries we have written. If many people who know what they’re doing will write entries (and include verification/references to information provided) then Wikipedia will have strong TCS content.
Comment #44 November 29th, 2008 at 10:01 pm
Several comments have mentioned alternatives to Wikipedia, and I’d like to add another: http://www.citizendium.com . Note that I’m not endorsing Citizendium, but rather simply throwing it on the pile.
Wikipedia is undeniably useful, but it also possesses some unavoidable fatal flaws that can make it unreliable. Why not encourage your readers to contribute to alternative resources that attempt to address some of these flaws?
Comment #45 November 30th, 2008 at 1:49 am
A better graph:
http://www.bloo.us/temp/zoograph2.png
No, not pretty.
Comment #46 November 30th, 2008 at 2:49 am
It turns out someone already did a (better) graph of the complexity classes (thanks for telling me), and used the same graph engine and all, displaying the data in the exact same way i did (striking coincidence i think).
http://www.public.iastate.edu/~crb002/combData/compTax.html
Well that’s 3 or 4 hours down the drain.
Comment #47 November 30th, 2008 at 2:56 am
It was more like 8 hours actually, looking back. That’s how i like to spend my Saturdays, doing things i would have been better off not doing but did anyway because nobody told me.
Comment #48 November 30th, 2008 at 4:04 am
There seems to be another case here among some of the comments and participants of impedance mismatch with Wikipedia.
The problem is – anyone can stand up and say “I’m a CS professor, and I assert this to be correct”. They can even use a real verifyable CS professor’s name. And still be lying through their teeth, some completely unrelated person, trying to insert misinformation.
IF you provide the sort of citations for your edits and articles that you would for a journal article, particularly if most of the citations are also available on the web for people not in the field to fact check, you should not be getting grief for adding anything. It’s best if you don’t cite yourself too much, but that’s true in publishing as much on WP. If you cite eight things and three were your work, but the other five are clearly independent and agreeing or supporting, there’s no problem.
If you’re just asserting things and not providing references, then you’re not helping. Because, honestly, most of the people who do that are just nuts or ignorant. We have higher standards of verifyability for information to keep that out. Yes, that means that Professor Z may have problems posting info on the bleeding edge. But it also means that we can with the same rules and enforcement mechanisms keep a jr high school student from posting nonsense. This is a real legitimate problem for Wikipedia.
Cite and reference your work. You do this in real life, you should be used to doing it and be very comfortable with doing it. You need to do it on Wikipedia, too. That’s nearly all you need to know. That, and use article talk pages if something doesn’t work, to talk it out rather than trying to apply superior mental or educational force to the article text directly…
If you don’t feel like providing citations there, then Wikipedia’s not the venue for you to be writing. Some people can’t write good general textbooks, some people can’t give a good conference presentation, some people who are brilliant have huge problems with their thesis defense because of personality or communications style. Wikipedia ultimately isn’t for *everyone* either, because it’s got its own structure and rules. If you don’t fit in that’s unfortunate. If you don’t make an effort to understand, that’s unfortunate and lazy. Put in the effort. And don’t forget to Cite!
Comment #49 November 30th, 2008 at 4:44 am
May be we(including me) should spend more time on wikiing than blogging :).
Comment #50 November 30th, 2008 at 8:20 am
Quantum computation (though Quantum computer is defined)
I disagree, what’s that doing here in a theoretical CS? That’s physics. Quantum computing isn’t CS, it’s physics, and impossible to realize in practice!
Comment #51 November 30th, 2008 at 12:34 pm
My experience has been that Wikipedia does an outstanding job of covering the basic concepts of algebraic and differential geometry. And this includes some basic concepts that are of fundamental importance in quantum information science (see for example, Wikipedia’s coverage of Stinespring’s factorization theorem and Choi’s theorem).
For these basic topics, Wikipedia’s coverage oftentimes is more concise, clear, and convenient of access than any textbook.
A useful rule-of-thumb (IMHO) is that if a mathematical topic has more than (say) ~500 people who are learning and/or using that topic (at any given moment in time) then its Wikipedia coverage tends to be very good.
It is noteworthy that pretty much mathematical topic that Terrence Tao posts about has good Wikipedia coverage. It’s not clear whether this is because ~500 (or more!) people are inspired by each of Tao’s posts, or whether Tao and his collaborators take an active role in editing (at least some) Wikipedia pages. Plausibly, both.
Comment #52 November 30th, 2008 at 2:15 pm
“Academics are not having our prose rewritten or deleted by people calling themselves [nicknames]”.
Not true. Some are used to collaborative work, and some endorse Wikipedia collaborative knowledge principle. Here’s a good article by an academic: http://chnm.gmu.edu/resources/essays/d/42
And yes, for those who cannot stand the idea of collaborative editing with anybody out there, there are other projects – from Citizendium, to Knoll.
Comment #53 November 30th, 2008 at 2:56 pm
The “academic” from http://chnm.gmu.edu/resources/essays/d/42 is a Historian, you can’t compare that to math ant phys.
Comment #54 November 30th, 2008 at 3:30 pm
Critic#52: The active math and physics editors in Wikipedia include at least one Fields medalist. But I think most of the mathematicians are more interested in writing about math itself than about the sociology of Wikipedia contribution.
Comment #55 November 30th, 2008 at 6:32 pm
Quantum computing isn’t CS, it’s physics, and impossible to realize in practice!
Then it’s not physics?
Comment #56 November 30th, 2008 at 7:04 pm
Critic says: Quantum computing isn’t CS, it’s physics, and impossible to realize in practice!
Scott replies: Then it’s not physics?
Quantum computing surely is a noble vision … of amazing physics … of wonderful mathematics … and also, daunting engineering challenges. Rather like controlled thermonuclear fusion, eh?
Even if the engineering of practical quantum computers takes awhile (as has happened for thermonuclear reactors), the payoff in mathematics, physics, and advanced simulation methods already is exceedingly valuable (as has happened for thermonuclear reactors).
The above is a system engineer’s narrative about the value of quantum computing. A mathematician might tell a different story … a physicist still another story.
It is the mark of a great enterprise—and quantum computing surely is one of humanity’s great enterprise—that it readily supports multiple narratives, which do not conflict, but rather reinforce one another.
Comment #57 December 1st, 2008 at 12:09 am
We should rename “Quantum Computing” to make it clear that it is primarily a field within Physics – for instance we could name it “Quantum Physics” (since it’s not yet taken). Why isn’t there a field named “Quantum Physics” anyway? I guess i’ll never know – i mean there is a “Quantum Computing” field and not a “Quantum Physics” field?
And you know, if the Computer Science people want to study the Quantum world then they should just create their own field and name it accordingly, this way there’s no confusion. And why haven’t they done this? Instead of attaching themselves to other people’s fields?
I suggest we change “Quantum Computing” to “Quantum Physics” and add the field “Quantum Windows, Word and Excel Science”, that ought to fix the problem once and for all.
Comment #58 December 1st, 2008 at 4:58 am
Just a suggestion. Can you blog about stuff which could be easily wikied. This way you can add entries with minimal effort.
Also there are wiki e-books(http://en.wikibooks.org/wiki/Main_Page). Can’t some of the lecture notes be made into wiki e-books.
Comment #59 December 1st, 2008 at 7:36 am
Job asks: Why isn’t there a field named “Quantum Physics” anyway? I guess i’ll never know – i mean there is a “Quantum Computing” field and not a “Quantum Physics” field?
Job, your questions find a detailed answer in the 2008 Physics and Astronomy Classification Scheme, which the American Institute of Physics uses to classify all of its articles.
The scheme takes the form of a tree graph in which the word “quantum” appears at (about) 200 different vertices.
We start at “PAC 03: Quantum mechanics, field theories, and special relativity”.
Under which we find “PAC 03.67-a: Quantum information (see also 42.50.Dv Quantum state engineering and measurements; 42.50.Ex Optical implementations of quantum information processing and transfer in quantum optics)”.
Under which we find “PAC 03.67.Lx: Quantum computation architectures and implementations”.
Next to which we find “PAC 03.67.Pp: Quantum error correction and other methods for protection against decoherence (see also 03.65.Yz Decoherence; open systems; quantum statistical methods; for decoherence in Bose–Einstein condensates, see 03.75.Gg)”.
——–
You can see one of the difficulties that the AIP’s library scientists are wrestling with (library science being itself a branch of information theory): the conceptual structure of the quantum information literature is not well-described by a hierarchical tree graph.
But mathematicians should not scoff. Quantum information theory is not particularly well described by hierarchy of theorems either … or by a hierarchy of complexity classes … or a hierarchy of authority … or a hierarchy of priority.
Wikipedia (IMHO) represents a radical attempt to escape the informatic bounds of tree-graph hierarchy. The risks that Wikipedia incurs include apathy, faction, and chaos. It is amazing that it works as well as it does.
Comment #60 December 1st, 2008 at 10:24 am
By the way, as one more “factoid”, I once used a citation index (an old-fashioned paper one!) to estimate how many articles John von Neumann had to read, during the years immediately preceding WWII, in order to keep up with the literature on quantum measurement theory.
The answer was startling: von Neumann had to read only one or two articles per month to keep up with the literature. And of these few, most were only marginally relevant.
So it is not clear whether the present flood of mathematical and scientific literature represents heaven or hell (especially for young people) … perhaps it is a modern purgatory?
And if so, are innovations like Wikipedia lifting us up to heaven, or pulling us down to hell? The answer is far from clear; still we can be optimistic.
If we take a Fred Rogers point-of-view … that we should all work to build a heaven here on earth, rather than wait for heaven to come to us … then I would nominate Terry Tao’s research, teaching, and web-logging as exemplary.
Comment #61 December 1st, 2008 at 12:24 pm
Anon #58: my own tendency is more to blog about the stuff that cannot be easily wikied (e.g. because it’s too much original research for Wikipedia standards but too little original research to write an actual paper about). If it were easily wikied, I’d just wiki it instead.
Comment #62 December 1st, 2008 at 2:02 pm
John Sidles, that fact about von Neumann is quite eye opening. I was thinking the other day how wikipedia, google, or most generally, the internet itself, are indispensable tools when dealing with the volume of information they contain. This first came to my attention a few years ago when working on a physics assignment, and my roommate asked me for the atomic mass of molybdenum, which took about 15 seconds, and I realized I couldn’t have found it so fast if you had handed me a book containing that information and told me the page number (well, maybe).
Two cents: wikipedia happens to have an enormous head start over knol and citizendium, and due to the more restrictive nature of the latter projects, they aren’t likely to catch up soon. Wikipedia’s shortfalls are less concerning to complete laymen (laywomen?) who are just interested in learning some basics of a complicated subject. (If anything, it may promote a healthy attitude of tentativeness towards knowledge in general—it is easy to forget that every book/article/journal makes mistakes.) Additionally, the more logical a subject (such as mathematics), the less likely it will lead to disputes with the uninformed. This is also true as the complexity of an article increases, though in both cases the article’s correctness is best defended by rigorous proof, either by citation in the latter, or formal proof in the former. Edit-war soldiers and deletionist trolls should encounter great difficulty in combating the truth when confronted with a knowledgeable, patient, teacher, who’s motivation isn’t credit but the dissemination of practical and/or pleasurable knowledge, (which I tend to think of as the basic principle of wikipedia).
So why haven’t I added anything? I guess I don’t feel confident enough in what I know to do a good job. (And what I do know is already written!) But I’ll get there sooner or later I think.
Comment #63 December 2nd, 2008 at 7:59 am
@John Sidles My vote for the publication deluge is hell. I have pretty much given up on publications as a way to stay current. A lot of people try to use journal clubs to reduce the magnitude of the task, but I don’t find this particularly effective, either. Going to conferences is the best way I have to keep current in specific fields. When I have a specific question or idea I need to research, then I go to the literature. Usually this is for something well outside of my field. Then I am usually confronted by an avalanche of very current papers which I have to slowly work my way back to something that does not assume so much domain knowledge it makes no sense to me.
Comment #64 December 2nd, 2008 at 8:36 am
You’ve never tried to hold forth on 0.999… = 1, or to convince a relativity denialist, I see.
Comment #65 December 2nd, 2008 at 11:29 am
Yes John A., I am aware that people are very adamant about some silly beliefs, and thats where it becomes so important that we are good at teaching these things. To unconvince the believers (of \neq) requires enormous quantities of patience and creativity. (I have spent a lot of time discussing religious beliefs with fundamentalist christians, so I think I can relate to the struggle.) The key advantage to 0.999… = 1 is that there exists many formal proofs to show it, and none to contradict it. I’ve also dealt with people who are unsatisfied with mathematical proof, but you just have to keep helping them dig through their (incorrect) intuition until you get to the source of their discomfort. I didn’t say it was easy, but for math and hard science it is far easier than say social sciences, or the humanities—and for all the effort it costs, any payoff seems much more beneficial than the result of ignoring the problem.
Comment #66 December 2nd, 2008 at 2:34 pm
Re: critic, comment #53: Why we cannot compare attitudes of social and natural scientists? Science and academia are similar, and usually, social science attitude to technology is much more guarded than that of natural science.
Comment #67 December 2nd, 2008 at 3:14 pm
off topic:
Scott,
what do you think about this paper
arxiv.org/abs/0811.4542 ?
Anton Zeilinger et al. claims that “Our results support the view that quantum randomness is irreducible and a manifestation of mathematical undecidability.”
Comment #68 December 2nd, 2008 at 9:17 pm
wolfgang – can I state an opinion? It looks appalling; another fine contribution to the genre of obscuring the meanings of things for the sake of drawing half-baked analogies. You can see this most clearly in action on pages 5 to 6, where after constructing the great analogy we notice that, um, sometimes the outcome of the measurement is the exact opposite of the proposition it supposedly represents. But oh well, this just means that “the truth values of decidable propositions found in quantum experiments do not necessarily have to be the same as the ones derived by classical logic.” Excuse me while I stick my finger down my throat! Congratulations Anton Zeilinger et al, you have discovered the art of redefining your concepts as you go, so you can keep using the same words even when they should no longer apply. All you have to do is call it “quantum decidability” and you’ll be able to get away with anything. It should at least be worth a New Scientist cover story.
Comment #69 December 3rd, 2008 at 9:40 am
Besides David Eppstein, Vaughan Pratt is another well-known CS theorist who edits WP regularly.
Comment #70 December 7th, 2008 at 11:30 pm
I’m staring at the Conductance entry
http://en.wikipedia.org/wiki/Conductance_(probability)
because I heard that word for the first time in a talk that Michael Mahoney gave at U Mich as applied to social networks. I did a few edits to cross-link it in the direction of the sociology measures I’m familiar with, and would welcome any extra words or paragraphs.
Comment #71 December 8th, 2008 at 3:04 pm
I see many classes having a Wikipedia article assignments; you might want to give it a try.
Comment #72 December 11th, 2008 at 11:23 pm
I don’t like wiki because of no easy way of managing it and making it something that one would really reference. I prefer knol (knol.google.com) since it gives the possibility of having a reference source. I can start a entry for say propositional proof complexity, let people contribute to it and review the contributions.