455
$\begingroup$

This question is (inspired by)/(shamefully stolen from) a similar question at MathOverflow, but I expect the answers here will be quite different.

We all have favorite papers in our own respective areas of theory. Every once in a while, one finds a paper so astounding (e.g., important, compelling, deceptively simple, etc.) that one wants to share it with everyone. So list these papers here! They don't have to be from theoretical computer science -- anything that you think might appeal to the community is a fine answer.

You can give as many answers as you want; please put one paper per answer! Also, notice this is community wiki, so vote on everything you like!

(Note there has been a previous question about papers in recursion-theoretic complexity but that is quite specialized.)

$\endgroup$
  • 65
    $\begingroup$ In the answers, I'd like to see more emphasis on whether it really is a good idea to read the original paper nowadays (or if it makes much more sense to read a modern textbook exposition of it). I have too often seen TCS papers that are truly seminal, but I'd rather save my colleagues from the pain of trying to decipher the original write-up – which is far too often a hastily-written 10-page conference abstract, with references to a "full version" that never appeared... $\endgroup$ – Jukka Suomela Sep 12 '10 at 9:46
  • 7
    $\begingroup$ Yes, I hope it is clear that papers of this type are not good for the list (if you want to share it with everyone, then it shouldn't be a pain to read) $\endgroup$ – Ryan Williams Sep 12 '10 at 16:22
  • 30
    $\begingroup$ Too many people are just posting one-liners. Any one can post 100s of unique papers without putting any thought into it. Please post why you think everyone should read those papers. This means justifying why they should read that paper instead of someone else's writeup of that result, and what is so awesome about the paper that everyone should read it. $\endgroup$ – Robin Kothari Sep 16 '10 at 19:18
  • $\begingroup$ Good question. My opinion is that if you want to understand the minds of the inventors, and possibly understand how to invent things, you have to read their own words. The more you labor, the closer you get to their actual thought process. $\endgroup$ – ixtmixilix Sep 26 '10 at 22:07
  • 1
    $\begingroup$ see also mathoverflow, What are the most important results (and papers) in complexity theory that every one should know? $\endgroup$ – vzn Sep 20 '12 at 5:18

70 Answers 70

4
$\begingroup$

I guess this question will be searched by some amateurs like me. While everybody proficient in the field will most likely know it, I found Donald Knuth's paper Dancing Links a very interesting read.

It doesn't require too much theoretical background and still gives an interesting impression on how we can find new ways to solve well known problems with some creative thinking. And it directly leads to the exact cover problem which again provided some interesting insights. This especially for everybody who may try his skills in areas like solving Sudokus or the N queens problem.

$\endgroup$
4
$\begingroup$

The RSA cryptosystem was described in a short elegant paper; it's very readable and created quite a stir even among non-scientists.

$\endgroup$
  • 1
    $\begingroup$ This is the Rivest/Shamir/Adleman paper as suggested by giuper, but this version has been typeset in TeX. $\endgroup$ – András Salamon Nov 23 '11 at 10:36
4
$\begingroup$

My favorite piece of scientific writing is Charles Bennett's 1979 On Random and Hard-to-Describe Numbers which describes Chaitin's number. You should read it not because its scientific content will be useful to you, although it may be, but just for the quality of the writing. If you already know about Chaitin's number, just skip to the last paragraph on page 6 and read from there on.

I don't want to quote too much from the article, but here is the last sentence of the abstract.

Other, Cabalistic properties of $\Omega$ [Chaitin's number] are pointed out for the first time.

$\endgroup$
3
$\begingroup$

Although not published in a scientific journal, Vannevar Bush's As We May Think has influenced much work in the computer science field, including hypertext, the personal computer, digital libraries, and the Internet. It even has it's own Wikipedia article, for god's sake.

$\endgroup$
3
$\begingroup$

On Universal Learning Algorithms, Oded Goldreich and Dana Ron (1997), Information Processing Letters, Volume 63, Issue 3, pp. 131-136. (see also the updated version)

Adapting Levin's argument for the existence of an optimal algorithm for NP, the authors show that there exists a universal learning algorithm (in several learning settings, including PAC): "if a concept class is learnable, this algorithm will learn it, optimally."

Beyond the result itself, and perhaps more strikingly, this is also (as pointed out and discussed in the paper) a great illustration of the dangers of abusing $O(\cdot)$ notations and asymptotics.

$\endgroup$
2
$\begingroup$

Time/space tradeoffs for reversible computation (1989) by Charles Bennett: In this paper, Bennett introduces a pebble game to show that reversible computation can emulate any conventional computation with very reasonable space/time overheads. This method of emulating conventional computation with reversible computation will become increasingly practical in the future when energy efficient reversible computers and quantum computers become prominent.

$\endgroup$
2
$\begingroup$

Not specifically a topic in theoretical computer science, but I think an area that is fundamental to much of the work in data analysis and machine learning is a foundational paper in what are currently known as Graphical Models:

Lauritzen, Steffen L. and Spiegelhalter, David J., ( 1988) "Local Computations with Probabilities on Graphical Structures and their Application to Expert Systems", Journal of the Royal Statistical Society, Series B (Methodological)", 50(2) pp 157--224.

The way they solve the probability updating problem harkens back to earlier work on optimizing elimination orders for linear systems, and, subsequently is expanded on by Lauritzen to a larger class of dynamic programming style problems.

$\endgroup$
1
$\begingroup$

Rumelhart, David E.; Hinton, Geoffrey E., Williams, Ronald J. (8 October 1986). "Learning representations by back-propagating errors". Nature 323 (6088): 533–536. DOI:10.1038/323533a0

The paper that introduced backpropagation and resuscitated neural networks.

$\endgroup$
-1
$\begingroup$

The Base Rate Fallacy and its implications for the Difficulty of Intrusion Detection

Stefan Axelsson, "The Base-Rate Fallacy and its Implications for the Difficulty Of Intrusion", 1999

For those poor saps stuck waiting for IDS alerts, this shows that even if you're signature is 99% accurate, if it's a packet based IDS then you will still be overrun with false positives.

Comment - More generally an understanding of how Bayes rule applies to probabilistic inference, and how probabilistic graphical models are used illuminates many fallacies that arise in working with statistical data.

$\endgroup$
  • 4
    $\begingroup$ I think, in the context of this site, "everyone" should mean "every theoretical computer scientist". So why should we all be persuaded to read something that isn't even theoretical computer science? $\endgroup$ – David Eppstein Dec 30 '12 at 18:36
-1
$\begingroup$

The paper Multidimensional Divide-and-conquer by Jon L. Bentley discussed multidimensional divide-and-conquer, an algorithmic paradigm to solve problems in multidimensional divide-and-conquer.

It is really easy to read and helpful to solve lots of high-dimensional computation problem.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.