Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.)

share|improve this question
55  
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... –  Jukka Suomela Sep 12 '10 at 9:46
6  
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) –  Ryan Williams Sep 12 '10 at 16:22
25  
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. –  Robin Kothari Sep 16 '10 at 19:18

68 Answers 68

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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!

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

"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.

share|improve this answer

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.

share|improve this answer

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

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

share|improve this answer

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.

share|improve this answer

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".

share|improve this answer

The theory of interstellar trade by Paul Krugman

share|improve this answer
1  
How does interstellar arbitrage (while undoubtedly interesting) relate to theoretical computer science? –  András Salamon Sep 17 '10 at 11:32
4  
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. –  Pratik Deoghare Sep 24 '10 at 8:30
4  
The critique in the paper applies to TCS as well –  Noam Oct 14 '10 at 19:39

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.

share|improve this answer

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.

share|improve this answer

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

This paper is the theoretical foundations of modern Cryptography.

share|improve this answer

"The mechanical evaluation of expressions" by Peter J. Landin

Introduced

  1. 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 !!!

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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!

share|improve this answer

Fischer Black and Myron Scholes, The Pricing of Options and Corporate Liabilities http://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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

protected by Kaveh May 10 '13 at 6:51

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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