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

  • 62
    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
  • 29
    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
  • 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. – ixtmixilix Sep 26 '10 at 22:07
  • 1

68 Answers 68

The 1936 paper that arguably started computer science itself:

  • Alan Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society s2-42, 230–265, 1937. doi: 10.1112/plms/s2-42.1.230

In just 36 pages, Turing formulates (but does not name) the Turing Machine, recasts Gödel's famous First Incompleteness Theorem in terms of computation, describes the concept of universality, and in the appendix shows that computability by Turing machines is equivalent to computability by $\lambda$-definable functions (as studied by Church and Kleene).

Ken Thompson's "Reflections on Trusting Trust". Short, sweet, and mind-blowing.

  • 5
    Also, very approachable. I read it quite some time ago, when I had basically no CS background, no programming experience and didn't even know what a compiler was. – Jörg W Mittag Sep 13 '10 at 19:05
  • just read it -- awesome indeed! – Lev Reyzin Sep 15 '10 at 1:15
  • 1
    "Last week, Googler Ken Thompson was awarded the Japan Prize in Information and Communications for his early work on the UNIX operating system." (src: Buzz post from Life at Google) – Sebastián Grignoli May 26 '11 at 5:23
  • 4
    I would think this paper would be pretty difficult to digest without at least knowing what a compiler is. – Fixee Sep 2 '11 at 4:26
  • 2
    In the paper, I think figures 2.1 and 2.2 are swapped. – Dennis Sep 10 '13 at 6:50

What Every Computer Scientist Should Know About Floating-Point Arithmetic

This paper explains and reinforces the notion that floating point isn't magic. It explains overflow, underflow, what denormalized numbers are, what NaNs are, what inf is, and all the things these imply. After reading this paper, you'll know why a == a + 1.0 can be true, why a==a can be false, why running your code on two different machines can give you two different answers, why summing numbers in a different order can give you an order of magnitude difference and all the wacky stuff that happens in the world of mapping an uncountably infinite set of numbers onto a countably finite set.

An edited version is also available on the web.

Keshav's How to Read a Paper. You can also download the paper from here.

  • Nice read indeed. – Anthony Labarre Oct 15 '10 at 8:30
  • I always think that CS research papers are written in some foreign language. – Berlin Brown Apr 26 '11 at 21:00
  • 3
    Very good! It is worth to be put on tagline banner on the site to be sure no one student miss that. – Vag May 25 '11 at 13:28
  • The second link is currently broken – Christopher Manning Jun 21 '12 at 4:02
  • 2
    This is my favourite from the the list. Also note that this is a living document, unlike most papers which do not receive updates after being published. – Dennis Sep 10 '13 at 7:07

Paths, Trees and Flowers by J. Edmonds. This paper about classic combinatorial optimization problem is not only well written, but also states that the notion of "polynomial-time algorithms" is essentially a synonym for efficiency.

Reducibility Among Combinatorial Problems by Richard Karp. The paper contains what's often referred to as Karp's "original 21 NP-complete problems." In many ways, this paper truly motivated the study of NP-completeness by demonstrating its applicability to a wider domain. Very readable.

  • 5
    I like this paper, but some of the reductions are really sketchy and hard to follow. See any complexity text for more details. – András Salamon Sep 13 '10 at 1:42
  • 2
    @Andras Salamon I agree 100%. – Tayfun Pay Aug 16 '12 at 13:52

Hartmanis and Stearns, "On the computational complexity of algorithms", Transactions of the American Mathematical Society 117: 285–306 (1965)

This was the first paper that took the study of time complexity seriously, and surely was the primary impetus for Hartmanis and Stearns' joint Turing award. While their initial definitions are not quite what we use today, the paper remains extremely readable. You really get the feeling of how things were in the old "Wild West" frontier of the 60's.

Quantum Mechanical Computers (PDF) by Richard Feynman.

He introduces the idea of quantum computation, describes quantum circuits, explains how classical circuits can be simulated by quantum circuits, and shows how quantum circuits can compute functions without lots of garbage qubits (using uncomputation).

He then shows how any classical circuit can be encoded into a time-independent Hamiltonian! His proof goes through for quantum circuits too, therefore showing that time evolving Hamiltonians is BQP-hard! His Hamiltonian construction is also used in the proof of the quantum version of the Cook-Levin theorem, proved by Kitaev, which shows that k-local Hamiltonian is QMA-complete.

  • The link isn't valid. Do you have another source? edit> Searched on google : Is it this one? – Klaim Oct 1 '10 at 14:21
  • That's the one. I added a new link and a link to it's page on the publisher's website. – Robin Kothari Oct 1 '10 at 23:27
  • Did the notions of BQP and QMA exist when Feynman wrote this paper? Or is there a recent paper which draws this connection? Any reference/exposition of this fact that k-local Hamiltonian is QMA complete? – Anirbit Jan 3 '16 at 10:54

Expander graphs and their applications, S. Hoory, N. Linial, and A. Wigderson is an extremely nice survey on expander graphs. No surprise that it won the 2008 AMS Conant Prize.

I want to recall that expander graphs are the key ingredient in recent breakthroughs in TCS, eg.

  • log-space algorithm for undirected connectivity (by Reingold, STOC, 2005)
  • the alternative proof of the PCP Theorem (by Dinur, ECCC, TR05-046, 2005)

and not so recent:

  • AKS sorting network, which achieves depth $O(\log n)$ and size $O(n \log n)$ for sorting $n$ inputs (by Ajtai, Komlós and Szemerédi, STOC, 1983)
  • Linear-time encodable and decodable error-correcting codes (by Spielman, STOC, 1995)
  • 1
    You should watch for combinatorial or support preconditioners. Expander graphs are even used in numerical analysis today. – shuhalo Oct 5 '11 at 17:30

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer - Peter W. Shor This paper showed that the discrete logarithm problem can be solved in $O((log N)^3)$ time when the corresponding classical algorithm takes considerably longer specifically $O\left(\exp\left(\left(\begin{matrix}\frac{64}{9}\end{matrix} b\right)^{1\over3} (\log b)^{2\over3}\right)\right)$ which is the runtime of GNFS.

I'm surprised that no one has come up with Hastad's "Some Optimal Inapproximability Results" (JACM 2001; originally STOC 1997). This landmark paper has been written so well, you can come to it with little other than mathematical maturity and it will make you want to learn several things well, such as its Fourier techniques, parallel repetition, gadgets, and whatnot.

Hundreds of Impossibility Results for Distributed Computing by Fich and Ruppert. A readable, pictorial survey that really does present hundreds of impossibility results, including the core questions of the field. A remarkable piece of expository writing.

Les Valiant's Theory of the Learnable (1984) set the agenda for learning theory for decades, and it's a nice and readable paper!

There's also quite a bit of intuitive explanation in the paper that makes it fun and compelling. Various parts of this paper are still routinely quoted in COLT/ALT talks.

Perhaps too basic, but I'm shocked that nobody has mentioned the original Lambda papers by Steele and Sussman

  • 3
    I'd upvote you once for every Lambda paper if I could. – jkff Sep 21 '10 at 16:43

John McCarthy's Recursive functions of symbolic expressions and their computation by machine, part I.

This is the foundational paper on Lisp. Here we find the first metacircular evaluator, fitting on a single page. Its impact cannot be overstated, and it is still eminently readable.

The complexity of theorem-proving procedures by Stephen A. Cook. This paper proves that all the languages decided by polytime nondeterministic Turing machines can be (Cook-)reduced to the set of propositional tautologies.

The importance of this result is (at least) twofold: first, it shows that there exist problems in NP which are at least as hard as the whole class, the NP-complete problems; furthermore, it provides a concrete example of such a problem, which can then be reduced to others in order to prove them complete.

Nowadays Karp reductions are more commonly used than Cook reductions, but the main proof of this paper can be easily adapted to show that SAT is NP-complete with respect to Karp reductions.

  • 5
    This is one of those conference papers for which no journal version ever appeared, but this one is definitely worth going back to: well written and full of great side comments. – András Salamon Sep 12 '10 at 16:42

Call-by-value is dual to call-by-name by Philip Wadler is a good read.

  • 25
    Anything by Phil Wadler is a good read. – Dave Clarke Sep 20 '10 at 10:15

C.A.R. Hoare, An Axiomatic Basis for Computer Programming.

From the abstract: In this paper an attempt is made to explore the logical foundations of computer programming by use of techniques which were first applied in the study of geometry and have later been extended to other branches of mathematics.

It has six pages that are quite easy to follow.

  • 1
    Please fix the link. – Randomblue Aug 10 '12 at 16:37

Alon, Matias and Szegedy, The space complexity of approximating the frequency moments, JCSS 58(1):137-147, 1999.

This rather magical paper was the first one to formalize streaming algorithms and prove rigorous upper and lower bounds for foundational tasks in the streaming model. Its techniques are simple, its proofs are beautiful, and its impact has been profound. The work won Alon, Matias and Szegedy the Gödel Prize in 2005.

  • dang. I was going to add this one :) – Suresh Venkat Sep 12 '10 at 22:09

Immerman's paper proving the theorem now known as the Immerman–Szelepcsényi theorem, is a great example of easy-to-read, clever and short paper. I love the story told in the intro.

N. Immerman, Nondeterministic space is closed under complementation, SIAM Journal on Computing 17, 1988, pp. 935–938.

  • To be fair, Szelepcsényi's paper, "The method of forced enumeration for nondeterministic automata," is just as nice. – Lev Reyzin Jun 27 '12 at 14:00

I recommend reading Savitch's paper. It basically states that, for any function $f(n) \ge \log(n)$,

$\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^2\right).$

The result establishes, for example, that $\text{NPSPACE} = \text{PSPACE}$; a surprising result which its "time" counterpart ($\text{P}$ vs. $\text{NP}$) is a long-standing open problem.

Savitch, Walter J. (1970), "Relationships between nondeterministic and deterministic tape complexities", Journal of Computer and System Sciences 4 (2): 177–192.

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming by Goemans and Williamson.

A fine example of introducing a new technique to obtain results that are much better than those known before.

Russell Impagliazzo's A Personal View of Average-Case Complexity. This is a great paper because it is cleverly written, and it summarizes the state of affairs in five "worlds" where our conjectures about complexity are resolved in various ways, giving real-world consequences in each case.

Extractors and Pseudorandom Generators by Luca Trevisan. In this paper good randomness extractor is built by the means of error-correcting codes and combinatorial designs. Construction is quite easy to understand but it is completely stunning, because it is not obvious at all what is the connection between extractors, codes and designs.

After all, it is a good example of a result in TCS that requires some fancy combinatorics.

How to Write a Proof, by Leslie Lamport.

  • 4
    I read this and I read A Mathematician's Lament by Lockhart ( IMHO I believe that the strategy that Lamport suggest goes against what Lockhart's argues on the beauty of mathematics. – Marcos Villagra Apr 25 '11 at 5:02
  • 2
    Very interesting read. I understand your opinion, but if I'm not mistaken, Lamport aims his message towards people who are more "mathematically educated" than those targeted by Lockhart, who aims at helping students develop a taste for mathematics. I'll also admit that following a strict format makes proofs quite dull to read, but I agree with Lamport on the idea of proofs by levels: you do not always want/need/have time to read everything in detail, and even when you do, having a summary of what's to come can be quite helpful. Quite a lot more than those "easy to see/clearly/wlog/..." ;-) – Anthony Labarre May 17 '11 at 11:27

If I may quote Sarah Palin on this issue: "All of them".

More seriously, I think most papers should not be read in the original. As time passes people figure out better way of understanding and presenting the original problem/solution. Except for the Turing original paper, which is of historical importance, I would not recommend reading most original papers if there is followup work that cleaned it up. In particular, of a lot of stuff is presented much better in books than in the original.

  • 15
    This comment is true in general, but Ryan explicitly asks for examples for which this is not true. There are many classic papers that contain conjectures not yet proved, techniques that have been overlooked, or results that tend to be forgotten but could be dusted off and put to new uses. – András Salamon Sep 17 '10 at 11:35
  • 11
    I disagree. It is true that original papers sometime are unreadable and secondary works give better exposition of the results, but sometimes the original papers contain ideas which are omitted in later works. Also reading original papers can teach us how the author came up with the idea. Take a look at this post of Timothy Chow on MO: – Kaveh Sep 29 '10 at 18:35
  • 3
    Its great when this happens. I just claim that it is somewhat rare. – Sariel Har-Peled Sep 30 '10 at 4:14
  • 6
    You say "All of them", but don't you then argue for "None of them"? – Peter Taylor Jan 19 '11 at 11:28
  • 1
    @Peter Taylor, I think that's why Sarah is mentioned. :) – Radu GRIGore Feb 9 '11 at 14:32

The influence of variables on boolean functions, J. Kahn, G. Kalai and N. Linial

This paper introduced Fourier techniques for TCS community and solved very neat open problem.

I find this paper very readable.

Chomsky analyzes how mathematical models can be used to describe natural language, from a linguistic point of view.

  • 2
    By the way, I am not advocating this paper -- just edited to fix typos and add a link. I prefer Gold's paper if one wants a classic paper about language. – András Salamon Sep 17 '10 at 13:10

Kurt Gödel's On formally undecidable propositions of Principia Mathematica and related systems.

  • 5
    This is important, though I do think that later treatments on the subject are easier to read than the original. – Rob Apr 26 '11 at 20:02

protected by Kaveh May 10 '13 at 6:51

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

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.