490
$\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
    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
    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
    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
    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
    Sep 20, 2012 at 5:18

72 Answers 72

Reset to default
1
2 3
176
$\begingroup$

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

(Mirror)

Improve this answer
$\endgroup$
4
  • $\begingroup$ The safest general characterization of the Internet is that it consists of a series of footnotes to this paper. $\endgroup$
    – Celal Ergün
    Mar 25, 2019 at 19:52
  • $\begingroup$ The Bell Labs link is broken. $\endgroup$
    – rw-nandemo
    Jul 9, 2021 at 20:35
  • $\begingroup$ en.m.wikipedia.org/wiki/… $\endgroup$
    – rofrol
    Aug 26, 2021 at 11:24
  • $\begingroup$ Just a note for readers of this paper that Shannon assumed that differential entropy would inherit all the desired properties of Shannon's Entropy. One of these properties is non-negativity, which differential entropy does not guarantee. $\endgroup$
    – Galen
    Apr 22, 2022 at 23:27
157
$\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).

Improve this answer
$\endgroup$
4
  • 8
    $\begingroup$ It is also very accessible and readable... $\endgroup$
    – Sariel Har-Peled
    Sep 12, 2010 at 21:22
  • 25
    $\begingroup$ and with it The Annotated Turing by Charles Petzold [Highly Recommended] $\endgroup$
    – Pratik Deoghare
    Sep 13, 2010 at 10:28
  • 1
    $\begingroup$ Here is a friendlier link to the paper. $\endgroup$
    – jameshfisher
    Mar 18, 2014 at 20:43
  • 2
    $\begingroup$ @james The problem with friendly links is that they are more likely to break. $\endgroup$
    – domotorp
    May 18, 2021 at 14:09
131
$\begingroup$

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

Improve this answer
$\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$
    – Jörg W Mittag
    Sep 13, 2010 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$
    – Sebastián Grignoli
    May 26, 2011 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, 2011 at 4:26
  • 3
    $\begingroup$ In the paper, I think figures 2.1 and 2.2 are swapped. $\endgroup$
    – Dennis
    Sep 10, 2013 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, 2017 at 22:59
98
$\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.

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

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

Improve this answer
$\endgroup$
8
  • $\begingroup$ Nice read indeed. $\endgroup$
    – Anthony Labarre
    Oct 15, 2010 at 8:30
  • $\begingroup$ I always think that CS research papers are written in some foreign language. $\endgroup$
    – Berlin Brown
    Apr 26, 2011 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, 2011 at 13:28
  • $\begingroup$ The second link is currently broken $\endgroup$
    – Christopher Manning
    Jun 21, 2012 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, 2013 at 7:07
72
$\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.

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

Improve this answer
$\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$
    – András Salamon
    Sep 13, 2010 at 1:42
  • 2
    $\begingroup$ @Andras Salamon I agree 100%. $\endgroup$
    – Tayfun Pay
    Aug 16, 2012 at 13:52
54
$\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.

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

Improve this answer
$\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, 2010 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$
    – Robin Kothari
    Oct 1, 2010 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$
    – Student
    Jan 3, 2016 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:

Improve this answer
$\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, 2011 at 17:30
  • $\begingroup$ @shuhalo Can you give an example? $\endgroup$
    – Elle Najt
    May 22, 2020 at 23:50
45
$\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.

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

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

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

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

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ I'd upvote you once for every Lambda paper if I could. $\endgroup$
    – jkff
    Sep 21, 2010 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.

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

Improve this answer
$\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$
    – András Salamon
    Sep 12, 2010 at 16:42
37
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 25
    $\begingroup$ Anything by Phil Wadler is a good read. $\endgroup$
    – Dave Clarke
    Sep 20, 2010 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.

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ dang. I was going to add this one :) $\endgroup$
    – Suresh Venkat
    Sep 12, 2010 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.

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

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

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

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

How to Write a Proof, by Leslie Lamport.

Improve this answer
$\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$
    – Marcos Villagra
    Apr 25, 2011 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$
    – Anthony Labarre
    May 17, 2011 at 11:27
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.

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ can you add a link ? $\endgroup$
    – Suresh Venkat
    Apr 25, 2011 at 16:08
21
$\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.

Improve this answer
$\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$
    – András Salamon
    Sep 17, 2010 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, 2010 at 18:35
  • 4
    $\begingroup$ Its great when this happens. I just claim that it is somewhat rare. $\endgroup$
    – Sariel Har-Peled
    Sep 30, 2010 at 4:14
  • 6
    $\begingroup$ You say "All of them", but don't you then argue for "None of them"? $\endgroup$
    – Peter Taylor
    Jan 19, 2011 at 11:28
  • 2
    $\begingroup$ @Peter Taylor, I think that's why Sarah is mentioned. :) $\endgroup$
    – Radu GRIGore
    Feb 9, 2011 at 14:32
18
$\begingroup$

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

Improve this answer
$\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$
    – András Salamon
    Sep 17, 2010 at 13:10
18
$\begingroup$

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

Improve this answer
$\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, 2011 at 20:02
1
2 3

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