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
18
$\begingroup$

You and Your Research by Richard Hamming.

Not a peer reviewed paper, but the transcript of a seminar given in 1986. It's a great write up about lessons learned for becoming a great researcher.

Update: here is the later version of this talk.

Improve this answer
$\endgroup$
18
$\begingroup$

"Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs" by John Backus. This is the 1977 ACM Turing Award Lecture in which Backus introduces functional programming to the world. ACM honored Backus with this award for his seminal work on FORTRAN and for being the B in BNF notation used for describing programming language syntax. I found this work to be really inspiring. It caused me to look at computers and programming languages in a whole new way.

It also represents the kind of paper I wish there were more of. It exposes the inspiration and thought processing behind a nest of ideas without the rigorous but limiting tone of a research paper. It is a shame that researchers have to wait for an opportunity like the ACM Turing Award to be able to express themselves in this mode. Of course, few researchers can write like John Backus. This papers clarity of vision amazes me.

Improve this answer
$\endgroup$
16
$\begingroup$

Natural Proofs by Razborov and Rudich.

The original paper is clearly written, easy to read and requires very little background knowledge. Yet it proves what is (in my opinion) one of the most important known results in computational complexity, by showing that most naive or "natural" approaches one could think of for proving P != NP are doomed to failure. Worth reading at least as much for the mind-expanding nature of the proof as for the result itself.

Improve this answer
$\endgroup$
15
$\begingroup$

Alan Turing's Computing Machinery and Intelligence.

Improve this answer
$\endgroup$
15
$\begingroup$

R. Moser and G. Tardos: A constructive proof of the general Lovasz Local Lemma

In general the lovasz local lemma is used to (noncronstructively) prove the existence of some (combinatorial) object. Moser and Tardos showed that you can efficiently find this object with a very simple algorithm (in most applications of the LLL).

Great result and nice paper!

Improve this answer
$\endgroup$
15
$\begingroup$

PRIMES in P by Agrawal, Kayal, Saxena

Also known as the AKS primality test, was the first deterministic, (unconditional,) polynomial time primality testing algorithm, that was proposed in the paper, in 2002.

The authors received the Gödel Prize and the Fulkerson Prize for this work.

Improve this answer
$\endgroup$
14
$\begingroup$

This paper formalized quantum Turing machines and quantum complexity theory, introducing the class of efficient quantum algorithms BQP and showed the first example of a problem (Fourier sampling) in BQP but not known to be in BPP. Although there is also a previous conference paper from 1993 and Bernstein's PhD thesis, this paper in particular is very well written, easy to understand, and fun to read.

Improve this answer
$\endgroup$
14
$\begingroup$

There are two essays (but not paper) which are very handy after reading all the suggested papers:
1.How to write papers
2.How not to write papers
Both by Oded Goldreich

Improve this answer
$\endgroup$
14
$\begingroup$

Ronald L. Rivest, Adi Shamir, Leonard M. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Commun. ACM (CACM) 21(2):120-126 (1978)

If your are interested in Crypto/Security, this is a very nice reading.

Improve this answer
$\endgroup$
14
$\begingroup$

The mechanical evaluation of expressions by Peter J. Landin

Introduced:

  1. the lambda calculus as a basis for defining a programming language,

  2. abstract syntax,

  3. the idea of meta-language to explain other languages,

  4. imperative constructs to the lambda calculus.

Improve this answer
$\endgroup$
13
$\begingroup$

Factoring Polynomials with Rational Coefficients by Lenstra, Lenstra and Lovasz. They present the LLL lattice reduction algorithm for finding short vectors on integer lattices and show an application for factoring polynomials with rational coefficients in polynomial time.

While the algorithm has since been optimized and the polynomial factoring algorithm has been simplified (see Yap's book, chap. 9, for a good reference), the original paper has a good description of the lattice reduction algorithm.

Improve this answer
$\endgroup$
13
$\begingroup$

Emil Post's "Recursively enumerable sets of positive integers and their decision problems." Bull. Amer. Math. Soc. 50 (1944), 284-316.

Not only is the paper readable, but it was (I believe) the first paper to introduce each of the following notions, many of which were later adapted to polynomial-time either as central ideas or for interesting results:

  • Many-one reduction (and one-one reduction)
  • Truth-table reduction
  • Simple sets (=complements of immune sets), hypersimple sets
  • Creative sets (later used in papers regarding the Berman-Hartmanis isomorphism conjecture)

Especially recommended for anyone interested in history and/or computability theory. As far as I can tell, it's also a good survey of all of computability theory up to 1944, and was really the starting point for the blossoming of the field.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Definitely an evergreen classic. $\endgroup$
    – András Salamon
    Commented Oct 2, 2010 at 16:57
12
$\begingroup$

Gold proves (for a simple model) that it is not possible to learn even very simple languages (like those generated by regular grammars) if only strings that occur in the language are presented. In contrast, if one can query whether arbitrary strings are in the language, then languages generated by quite complex grammars can be learned. This set the scene for countless papers (well, at least 2660 according to Google Scholar), many of them dealing with, starting from, or criticizing the hypothesis that natural language cannot be learned without negative examples. Whether you agree or disagree with this foundation of Chomskian universal grammar, Gold's paper is well-written and clearly argued, and makes no claims about whether natural language can be learned or not. The model is simple, the results elegant, the consequences misunderstood -- read it and make up your own mind.

Improve this answer
$\endgroup$
11
$\begingroup$

Another very nice paper in proof complexity is

Ben-Sasson, Wigderson - Short proofs are narrow, Resolution made simple

Notice that even this paper gives a new technique which simplifies previous results.

Improve this answer
$\endgroup$
11
$\begingroup$

Time bounds for Selection by Blum, Floyd, Pratt, Rivest and Tarjan.

Very elegant algorithm. Plus it has four Turing award winners as authors.

Improve this answer
$\endgroup$
11
$\begingroup$

PCP Theorem by Gap Amplification by Irit Dinur

This paper should be of interest to anyone who uses the PCP theorem for approximation algorithms. It gives an alternate proof which arises much more naturally from approximation algorithms than the original proof. This one is a so-called "combinatorial proof".

Improve this answer
$\endgroup$
10
$\begingroup$

This is a classic!

Probabilistic Computations: Toward a Unified Measure of Complexity. Andrew Yao. FOCS'77.

Here Yao gives his famous Minmax principle. I read it and is so easy to read and fun. And the proof is just beautiful and the result amazing.

Improve this answer
$\endgroup$
10
$\begingroup$

Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time by Daniel Spielman and Shang-Hua Teng for introducing smoothed analysis and showing it's success in explaining the behavior of the simplex algorithm.

Improve this answer
$\endgroup$
9
$\begingroup$

The paper Impossibility of distributed consensus with one faulty process by Fisher, Lynch and Paterson shows that it is impossible to reach agreement in an asynchronous distributed system if 1 process might crash, no matter how many other (correct) processes are in the system! While this impossibility result can be circumvented using randomization, the methods of this paper, i.e. using indistinguishability to show that processes must behave in a certain way, have turned out to be highly useful for showing subsequent lower bound/impossibility for problems unrelated to fault-tolerant consensus (e.g. graph problems). As a plus, the paper is short but self-contained and a nice introductory read for someone new to distributed computing.

Improve this answer
$\endgroup$
8
$\begingroup$

I'll point a couple of papers in Proof Complexity, they are clear and explain most of the relevant techniques in the field (at least for Resolution system).

The first one is

Beame, Pitassi - Simplified and improved Resolution lower bounds

the paper really nails down the core of previous pigeon hole principle lower bounds. And that's why I think it is a pleasure to be read.

Improve this answer
$\endgroup$
8
$\begingroup$

Shafi Goldwasser, Silvio Micali: Probabilistic Encryption. J. Comput. Syst. Sci. 28(2): 270-299 (1984)

This paper is the theoretical foundations of modern Cryptography.

Improve this answer
$\endgroup$
7
$\begingroup$

The theory of interstellar trade by Paul Krugman

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ How does interstellar arbitrage (while undoubtedly interesting) relate to theoretical computer science? $\endgroup$
    – András Salamon
    Commented Sep 17, 2010 at 11:32
  • 5
    $\begingroup$ In the question's explanation there is a sentence : They don't have to be from theoretical computer science -- anything that you think might appeal to the community is a fine answer. $\endgroup$
    – Pratik Deoghare
    Commented Sep 24, 2010 at 8:30
  • 4
    $\begingroup$ The critique in the paper applies to TCS as well $\endgroup$
    – Noam
    Commented Oct 14, 2010 at 19:39
6
$\begingroup$

Bill Gasarch's P v NP poll

Not a paper like the others mentioned but certainly interesting and still very relevant today since no significant progress has been made in proving lower bounds.

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

Improve this answer
$\endgroup$
6
$\begingroup$

Guy E. Blelloch: Programming Parallel Algorithms

Very clear introduction to parallel algorithms.

Improve this answer
$\endgroup$
5
$\begingroup$

Allen Newell and Herbert A. Simon’s “Computer Science as Empirical Inquiry: Symbols and Search” (direct PDF link).

This quote summarizes it:

“We come now to the evidence for the hypotesis that physical symbol systems are capable of intelligent action, and that general intelligent action calls for a physical symbol system”

It's also very readable!

Improve this answer
$\endgroup$
5
$\begingroup$

A Simple Proof that Toffoli and Hadamard are Quantum Universal, D. Aharonov summarising a result found by Yaoyun Shi.

Because it is a simple, well written, 4 pages paper which makes you think and realise that Quantum Computation can be done with just two elementary blocks, from which one is a universal classical gate.

Improve this answer
$\endgroup$
5
$\begingroup$

Some great suggestions are included in the reading list of the Reading the Classics course given by Christos Papadimitriou at Berkeley. Some of them have been mentioned in previous answers already. Notable exception: Euler's Königsberg Bridge Problem.

Improve this answer
$\endgroup$
1
2
3

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