493
$\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.)

Improve this question
$\endgroup$
6
  • 71
    $\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
    Commented Sep 12, 2010 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
    Commented Sep 12, 2010 at 16:22
  • 32
    $\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
    Commented Sep 16, 2010 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
    Commented Sep 26, 2010 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
    Commented Sep 20, 2012 at 5:18

72 Answers 72

Reset to default
1 2
3
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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Nov 23, 2011 at 10:36
4
$\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.

Improve this answer
$\endgroup$
4
$\begingroup$

Fischer Black and Myron Scholes, The Pricing of Options and Corporate Liabilities https://web.archive.org/web/20231114103316/https://www.cs.princeton.edu/courses/archive/fall09/cos323/papers/black_scholes73.pdf

This paper is still one of the clearest descriptions of the options pricing problem and its closed-form solution. More fundamentally, it addresses how to price risk by convolving a probability distribution with a non-smooth payoff curve.

Improve this answer
$\endgroup$
1
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.

Improve this answer
$\endgroup$
3
$\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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
2
$\begingroup$

Ray Solomonoff:

  • A formal theory of inductive inference. Part I and Part II, 1964.

  • Complexity-based induction systems: Comparisons and convergence theorems. 1978

Kolmogorov:

  • Three Approaches to the Quantitative Definition of Information. 1965

Martin-Löf:

  • The definition of random sequences. 1966

Marvin Minsky said: The most important discovery since G"odel was the discovery by Chaitin, Solomonoff and Kolmogorov of the concept called Algorithmic Probability which is a fundamental new theory of how to make predictions given a collection of experiences and this is a beautiful theory, everybody should learn it, but it's got one problem, that is, that you cannot actually calculate what this theory predicts because it is too hard, it requires an infinite amount of work. However, it should be possible to make practical approximations to the Chaitin, Kolmogorov, Solomonoff theory that would make better predictions than anything we have today. Everybody should learn all about that and spend the rest of their lives working on it.

Improve this answer
$\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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
$\begingroup$

Expanders are special graph which are sparse yet highly connected. The challenge is to give an explicit construction of expanders. See the survey by Hoory-Linial-Wigderson-Expander Graphs and their Application for several applications of expanders. The most useful expanders are the ones with constant degree.If we have constant-sized object then we can freely use it without having to find a nice description for it. Also we can always find constant size in constant time by brute force approach.

An Elementary Construction of Constant-Degree Expanders by Alon-Schwartz-Shapira appeared in SODA 2007 and gave a wonderful construction of expanders using Replacement Product. In my opinion, the construction is so nice that this ought to be a part of lectures on Expanders. They apply the Replacement product only twice on Cayley expanders to obtain a constant-degree expanders. The construction is so combinatorial that one can even visualise the edges coming out of a cut.

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Dec 30, 2012 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.

Improve this answer
$\endgroup$
1 2
3

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