Thursday, September 08, 2005

Do Wikis Work?

John Stockton put a wiki version of the Complexity Zoo on the Quantum physics Qwiki. For those not up on the nomenclature, a wiki is a specially designed web page that anyone can change usually with mechanisms for tracking and undoing those changes if necessary. Ideally a wiki will allow the zoo to remain up-to-date without continual intervention from Scott. But will it work?

The Wikipedia has a number of entries for various complexity classes. I generally find them for the most part accurate but not complete. Take for example the NL entry which doesn't note that NL is closed under complement but instead has the misleading result that RL=NL (where one allows the randomized machine to have infinite computation paths). Sure I could fix the entry in wikipedia but there are at least two problems:

  • There aren't enough people in the field who have the time and patience to go through all the entries and update them.
  • I firmly believe RL should be what Wikipedia calls RLP. But what right do I have to impose my naming conventions on the whole wikipedia universe.

Sanjeev Arora and Boaz Barak set up Theory Matters as one big wiki. Boaz once said the following in a weblog comment.

Don't give "" as an example to a place that ignores area X. It's a Wiki - if you don't add the material yourself no one will do it for you.
But people are reluctant, for whatever the reason, to edit the wiki. Outside of the "Survey Collection" you can nearly count the number of contributors to the wiki on one hand.

In short wikis, like anything else on the web, can be a good source of information but are often incomplete sometimes in important ways. Just because anyone can edit a wiki doesn't mean that they do.


  1. Some of the students in my undergrad algorithms class last quarter ran a wiki with lecture notes, homework assignments, etc. Usefulness debatable, and I didn't pay a lot of attention myself to how accurate their notes were, but they did seem to keep it active all quarter.

  2. Thanks for the advertising Lance.... You're right in that the effective user number is pretty low right now for most wikis, including Qwiki, Quantiki, and the technical nether regions of Wikipedia. This is partly because there hasn't been enough time for people to acclimate to the young technology but also because people have understandable trepidations (about design issues, which wiki to choose, recognition, time investment, etc.). I could blather on my opinion regarding what I think is best (e.g. non-anonymous entry, blah blah), but I'd like to emphasize another point here: wikis largely suffer an expectations problem.

    People see the potential of how good a wiki can be and are disappointed when it is anything less, and this prevents them from contributing. In reality, it just takes a few perverse people with OCD to make a wiki much more useful than what else is out there for specific technical things. With the handful of contributors we have on Qwiki, we've already made a useful resource that is visited by hundreds of people per day. 40 percent of that is from Google, with some nonsense hits, but also many people searching for relevant things like 'how to build a vacuum chamber' or a particular user name. (Actually it's astonishing at how good Qwiki does on Google already.) So to answer your question, given the small amount of effort we've put into building it, I like to think it already 'works' at some level.

    Of course this is all one big social experiment, so let me know if you think of any way you'd like to change this particular experiment design-wise... we're flexible. By the way, I fixed the wiki complexity zoo so that you can edit it piecemeal which I think was a great suggestion on your part. Thanks!

  3. Hello Lance and Comnpany,

    1/ Wikis only work in very popular websites (e.g.,, and in particular, for their most popular webpages.

    A Wiki cannot work on second-tier websites, like the ones you cited, or with rarely-viewed entries. There are just not enough contributors, as you said.

    2/ I have one reference page on my website that goes up a Wikipedia entry.

    I contributed to the Wikipedia entry, but only by adding links to their "External Links" section.

    I found the textual content so riddled with approximations and errors, that I would have to overhaul everything. I had the same the reservation than you: "But what right do I have to impose my naming conventions on the whole wikipedia universe."

    3/ Conclusion:

    Whether we like it or not, Wikipedia is the only large free encyclopedia. Internauts want free information. This is a big trend. Open-source software fanatics and other "Wisdom of Crowds" believers will continue linking to Wikipedia. Yahoo! and Google support it.

    Our only reasonable position should be contribute and fix the bugs.

    In my experience with the "Prediction Market" webpage at Wikipedia, the two last big contributors were two people with an axe to grind ---each of them wanted to plug one play-money website that they operate or support.

    If we don't contribute, we let a boulevard to those rascals.

    Best regards,

    Chris. F. Masse

  4. I never heard the term RLP before, but I agree that it is indeed a more natural name for the class!

  5. When we set up the theorymatters Wiki (which btw was done by several people and not just Sanjeev&I),
    I found out that the first thing that people think when they hear about the concept of a Wiki is the danger of "vandalism".

    In reality, the problem is not that people do reckless edits but rather that they do not edit at all.
    That's why I urge you and your readers to be brave and "edit first, ask questions later". This holds both for TCS-related Wikipedia entries and for the theorymatters wiki. Remember that it is always very easy to revert back to an earlier version and so you can't do that much harm in editing, even if you completely rewrite the entry.


    p.s. I recently used Wikipedia several times for some pieces of information, and was always pleasantly surprised by the quality of the contents. In terms of breadth, it probably surpasses traditional encyclopedias (how many of those have entries for RL?). The big question is whether each entry eventually converges to high quality (or in other words, who has more energy - the people who know what they're talking about, or the people that think they know what they're talking about).

  6. Probably more interesting than the wiki feature itself is the GNU FDL license that the Wikipedia and Wikibooks uses. That part is much more exciting because it provides good incentives for people to essentially give away their work. The incentive is at least that no one else will "own" it and you'll get wide readership.

    There's going to be a conference on Wikis in San Diego, in conjunction with OOPSLA this October. It will have papers that address some of the flaws.

    To me the worst parts of wikis are: (1) the spammers and vandals -- but if they attack well-watched pages they can be kept in check. (2) lack of respect for experts.

    By (2) I mean the "anti-elitism" spoken by Larry Sanger, who was instrumental to the Wikipedia project. Many of the folks who are involved in Wikipedia earnestly confuse "freedom of speech" with letting total-nuts post their material. They can't stand the notion of removing something "that is true" and give way too much regard to people who don't know what they are talking about.

    I had troubles with this myself, when I started the article on "Type safety". I started it to talk about the fascinating connection between type safety and garbage collection. Some people who knew enough to know what I was talking about, but not enough to believe me tried what they could to rip the article to shreds. Through long debate and repeated citations of solid references, I was able to win them over, and the article is largely as I believe it should be. But that was way too much of a fight to have to do.