481
$\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$
5
  • 68
    $\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$ 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$ Sep 12 '10 at 16:22
  • 31
    $\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$ 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

72 Answers 72

173
$\begingroup$

"A mathematical theory of communication" by Claude Shannon, classics of information theory. Very readable.

(Mirror)

$\endgroup$
3
  • $\begingroup$ The safest general characterization of the Internet is that it consists of a series of footnotes to this paper. $\endgroup$ Mar 25 '19 at 19:52
  • $\begingroup$ The Bell Labs link is broken. $\endgroup$
    – rw-nandemo
    Jul 9 at 20:35
  • $\begingroup$ en.m.wikipedia.org/wiki/… $\endgroup$
    – rofrol
    Aug 26 at 11:24
154
$\begingroup$

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

$\endgroup$
4
  • 8
    $\begingroup$ It is also very accessible and readable... $\endgroup$ Sep 12 '10 at 21:22
  • 25
    $\begingroup$ and with it The Annotated Turing by Charles Petzold [Highly Recommended] $\endgroup$ Sep 13 '10 at 10:28
  • 1
    $\begingroup$ Here is a friendlier link to the paper. $\endgroup$ Mar 18 '14 at 20:43
  • 1
    $\begingroup$ @james The problem with friendly links is that they are more likely to break. $\endgroup$
    – domotorp
    May 18 at 14:09
128
$\begingroup$

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

$\endgroup$
8
  • 6
    $\begingroup$ 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. $\endgroup$ Sep 13 '10 at 19:05
  • 1
    $\begingroup$ "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) $\endgroup$ May 26 '11 at 5:23
  • 5
    $\begingroup$ I would think this paper would be pretty difficult to digest without at least knowing what a compiler is. $\endgroup$
    – Fixee
    Sep 2 '11 at 4:26
  • 3
    $\begingroup$ In the paper, I think figures 2.1 and 2.2 are swapped. $\endgroup$
    – Dennis
    Sep 10 '13 at 6:50
  • 3
    $\begingroup$ Disagree - nothing awesome or mindblowing in this paper. TL;DR 6 pages from mid-80s about "need to change criminal code to start punishing hackers [just like thieves or burglars]". O yeah, mentions a quine, without calling it by name. $\endgroup$
    – c69
    Oct 29 '17 at 22:59
95
$\begingroup$

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.

$\endgroup$
4
89
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ Nice read indeed. $\endgroup$ Oct 15 '10 at 8:30
  • $\begingroup$ I always think that CS research papers are written in some foreign language. $\endgroup$ Apr 26 '11 at 21:00
  • 3
    $\begingroup$ Very good! It is worth to be put on tagline banner on the site to be sure no one student miss that. $\endgroup$
    – Vag
    May 25 '11 at 13:28
  • $\begingroup$ The second link is currently broken $\endgroup$ Jun 21 '12 at 4:02
  • 2
    $\begingroup$ 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. $\endgroup$
    – Dennis
    Sep 10 '13 at 7:07
71
$\begingroup$

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.

$\endgroup$
0
61
$\begingroup$

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.

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

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.

$\endgroup$
1
52
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ The link isn't valid. Do you have another source? edit> Searched on google : wjzeng.net/Ref/Feynman_QuantumMechanicalComputers.pdf Is it this one? $\endgroup$
    – Klaim
    Oct 1 '10 at 14:21
  • $\begingroup$ That's the one. I added a new link and a link to it's page on the publisher's website. $\endgroup$ Oct 1 '10 at 23:27
  • $\begingroup$ 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? $\endgroup$
    – Anirbit
    Jan 3 '16 at 10:54
50
$\begingroup$

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.

and not so recent:

$\endgroup$
2
  • 1
    $\begingroup$ You should watch for combinatorial or support preconditioners. Expander graphs are even used in numerical analysis today. $\endgroup$
    – shuhalo
    Oct 5 '11 at 17:30
  • $\begingroup$ @shuhalo Can you give an example? $\endgroup$
    – Elle Najt
    May 22 '20 at 23:50
44
$\begingroup$

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.

$\endgroup$
2
44
$\begingroup$

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.

$\endgroup$
44
$\begingroup$

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.

$\endgroup$
43
$\begingroup$

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.

$\endgroup$
43
$\begingroup$

Perhaps too basic, but I'm shocked that nobody has mentioned the original Lambda papers by Steele and Sussman: SCHEME: An Interpreter for Extended Lambda Calculus, Lambda: The Ultimate Imperative, Lambda: The Ultimate Declarative.

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

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.

$\endgroup$
37
$\begingroup$

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.

$\endgroup$
1
  • 7
    $\begingroup$ 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. $\endgroup$ Sep 12 '10 at 16:42
37
$\begingroup$

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

$\endgroup$
1
  • 25
    $\begingroup$ Anything by Phil Wadler is a good read. $\endgroup$ Sep 20 '10 at 10:15
37
$\begingroup$

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.

$\endgroup$
0
34
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ dang. I was going to add this one :) $\endgroup$ Sep 12 '10 at 22:09
30
$\begingroup$

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.

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

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.

$\endgroup$
27
$\begingroup$

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.

$\endgroup$
26
$\begingroup$

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.

$\endgroup$
1
24
$\begingroup$

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.

$\endgroup$
24
$\begingroup$

How to Write a Proof, by Leslie Lamport.

$\endgroup$
2
  • 5
    $\begingroup$ I read this and I read A Mathematician's Lament by Lockhart (maa.org/devlin/LockhartsLament.pdf). IMHO I believe that the strategy that Lamport suggest goes against what Lockhart's argues on the beauty of mathematics. $\endgroup$ Apr 25 '11 at 5:02
  • 6
    $\begingroup$ 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/..." ;-) $\endgroup$ May 17 '11 at 11:27
21
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ can you add a link ? $\endgroup$ Apr 25 '11 at 16:08
19
$\begingroup$

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.

$\endgroup$
9
  • 16
    $\begingroup$ 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. $\endgroup$ Sep 17 '10 at 11:35
  • 12
    $\begingroup$ 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: mathoverflow.net/questions/28268/do-you-read-the-masters $\endgroup$
    – Kaveh
    Sep 29 '10 at 18:35
  • 4
    $\begingroup$ Its great when this happens. I just claim that it is somewhat rare. $\endgroup$ Sep 30 '10 at 4:14
  • 6
    $\begingroup$ You say "All of them", but don't you then argue for "None of them"? $\endgroup$ Jan 19 '11 at 11:28
  • 2
    $\begingroup$ @Peter Taylor, I think that's why Sarah is mentioned. :) $\endgroup$ Feb 9 '11 at 14:32
18
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$ Sep 17 '10 at 13:10
18
$\begingroup$

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

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

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