What papers should everyone read?

Question

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

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 09:46
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
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
see also mathoverflow, What are the most important results (and papers) in complexity theory that every one should know? — vzn, Sep 20 '12 at 05:18
There is a book along similar lines: Ideas That Created the Future: Classic Papers of Computer Science by Harry R Lewis. — Nishant, Jun 10 '23 at 14:00

score 176 · Answer 1 · edited Feb 04 '24 at 10:31

176

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

(Mirror)

edited Feb 04 '24 at 10:31

Ekene E.

121
4

answered Sep 12 '10 at 01:38

Grigory Yaroslavtsev

1,468
1
14
25

The safest general characterization of the Internet is that it consists of a series of footnotes to this paper. – Celal Ergün Mar 25 '19 at 19:52
The Bell Labs link is broken. – rw-nandemo Jul 09 '21 at 20:35
https://en.m.wikipedia.org/wiki/A_Mathematical_Theory_of_Communication#External_links – rofrol Aug 26 '21 at 11:24
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. – Galen Apr 22 '22 at 23:27

score 157 · Answer 2 · edited Aug 16 '12 at 09:00

157

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

edited Aug 16 '12 at 09:00

vorushin

101
3

answered Sep 12 '10 at 01:01

Henry Yuen

3,798
1
21
33

8

It is also very accessible and readable... – Sariel Har-Peled Sep 12 '10 at 21:22
25

and with it The Annotated Turing by Charles Petzold [Highly Recommended] – Pratik Deoghare Sep 13 '10 at 10:28
1

Here is a friendlier link to the paper. – jameshfisher Mar 18 '14 at 20:43
2

@james The problem with friendly links is that they are more likely to break. – domotorp May 18 '21 at 14:09

score 131 · Answer 3 · edited Jan 01 '12 at 19:28

131

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

edited Jan 01 '12 at 19:28

Community

1

answered Sep 12 '10 at 23:18

Jeffε

23,129
10
96
163

6

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 01: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 05:23
5

I would think this paper would be pretty difficult to digest without at least knowing what a compiler is. – Fixee Sep 02 '11 at 04:26
3

In the paper, I think figures 2.1 and 2.2 are swapped. – Dennis Sep 10 '13 at 06:50
3

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. – c69 Oct 29 '17 at 22:59
1

I agree with c69. This is currently the third top rated answer, but there's an enormous interestingness gap between it and the top two papers (by Shannon and Turing). Those two created new branches of mathematics. This one is... cute, I guess. – benrg Aug 13 '20 at 19:11
This paper is really nothing more than a high level introduction to the concept of a quine that goes absolutely off the rails at the end. Thompson's conclusion is that the existence of quines make trojan horses too hard to detect, so he demands the criminal code be updated and pop culture be engineered such that "[t]he act of breaking into a computer system has to have the same social stigma as breaking into a neighbor's house". Ridiculous. – rw-nandemo Jul 09 '21 at 20:56

score 98 · Answer 4 · edited Jul 24 '16 at 07:56

98

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.

edited Jul 24 '16 at 07:56

Bacon

101
3

answered Sep 30 '10 at 01:47

3

Please, fix the link. It's broken. – Oscar Mederos Feb 25 '11 at 01:44
1

Since Oracle acquired Sun, it ruined most of the links from Sun's web page. Although you can reach the original paper from here. – systemsfault Feb 26 '11 at 15:43
could this be it? https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/02Numerics/Double/paper.pdf – Blackle Mori Mar 11 '14 at 17:57
1

Fixed the broken link. – Ryan Dougherty Jul 14 '14 at 19:44

philosodad · Answer 5 · 2012-06-27T13:14:09.720

93

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

edited Jun 27 '12 at 13:14

answered Oct 13 '10 at 18:22

philosodad

101
1
5

Nice read indeed. – Anthony Labarre Oct 15 '10 at 08: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 04:02
@ChristopherManning thanks for pointing that out. I've updated the link. – philosodad Jun 27 '12 at 13:14
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 07:07
Though I've stumbled across this more than a year later, it's been invaluable to me. I would recommend this paper to everyone! – Morrison Cole Dec 13 '13 at 23:38
I like this ones the best, three-pass approach really helped me comprehending first few papers easily. – Fahad Siddiqui May 30 '17 at 09:09

score 71 · Answer 6 · edited Sep 20 '19 at 01:25

71

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.

edited Sep 20 '19 at 01:25

Joshua Grochow

37,260
4
129
228

answered Sep 12 '10 at 02:26

ilyaraz

1,569
18
33

score 62 · Answer 7 · edited Dec 09 '13 at 14:36

62

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.

edited Dec 09 '13 at 14:36

klingt.net

101
4

answered Sep 12 '10 at 06:26

Daniel Apon

6,001
1
37
53

7

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 01:42
2

@Andras Salamon I agree 100%. – Tayfun Pay Aug 16 '12 at 13:52

score 54 · Answer 8 · answered Sep 12 '10 at 00:51

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.

Working link. https://pdfs.semanticscholar.org/1ce8/9af300d9a7c64d3ee06175b24ca97763f9f2.pdf — scott m gardner, May 16 '19 at 22:09

score 52 · Answer 9 · edited Feb 14 '20 at 09:10

52

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.

edited Feb 14 '20 at 09:10

Jarwain

3
3

answered Sep 12 '10 at 02:26

Robin Kothari

13,617
2
60
116

The link isn't valid. Do you have another source? edit> Searched on google : http://www.wjzeng.net/Ref/Feynman_QuantumMechanicalComputers.pdf Is it this one? – Klaim Oct 01 '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 01 '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? – Student Jan 03 '16 at 10:54

score 50 · Answer 10 · edited Sep 20 '19 at 08:45

50

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)

edited Sep 20 '19 at 08:45

VS.

539
3
15

answered Sep 17 '10 at 08:20

Dai Le

3,664
1
24
37

1

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

score 45 · Answer 11 · answered Oct 01 '10 at 03:49

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.

score 44 · Answer 12 · answered Sep 12 '10 at 01:57

44

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.

answered Sep 12 '10 at 01:57

Aaron Sterling

6,994
6
42
74

Publisher's version: https://doi.org/10.1007/s00446-003-0091-y – András Salamon Oct 09 '18 at 21:54
can you please add the year to the answer – Narek Bojikian Sep 22 '19 at 01:11

Lev Reyzin · Answer 13 · 2010-09-24T14:38:18.273

44

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.

edited Sep 24 '10 at 14:38

answered Sep 12 '10 at 02:18

Lev Reyzin

11,968
13
63
103

score 43 · Answer 14 · edited Sep 06 '11 at 01:37

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.

score 43 · Answer 15 · edited Sep 20 '19 at 07:44

43

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.

edited Sep 20 '19 at 07:44

Klaus Draeger

2,520
1
23
19

answered Sep 21 '10 at 15:36

sclv

1,379
1
14
17

3

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

score 42 · Answer 16 · answered Sep 24 '10 at 13:35

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.

score 37 · Answer 17 · answered Sep 12 '10 at 09:20

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.

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

Radu GRIGore · Answer 18 · 2012-08-14T19:33:15.087

37

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.

edited Aug 14 '12 at 19:33

answered Sep 12 '10 at 12:14

Radu GRIGore

4,796
30
69

score 37 · Answer 19 · answered Sep 20 '10 at 10:00

37

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

answered Sep 20 '10 at 10:00

lyonanderson

101
1
2

25

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

score 34 · Answer 20 · answered Sep 12 '10 at 16:06

34

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.

answered Sep 12 '10 at 16:06

arnab

7,000
1
38
55

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

score 30 · Answer 21 · answered Sep 12 '10 at 04:02

30

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.

answered Sep 12 '10 at 04:02

Michaël Cadilhac

3,946
22
39

1

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

Sadeq Dousti · Answer 22 · 2010-09-12T19:38:36.957

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.

score 28 · Answer 23 · answered Mar 19 '11 at 16:44

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.

score 26 · Answer 24 · answered Sep 12 '10 at 15:35

26

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.

answered Sep 12 '10 at 15:35

Gianluca Della Vedova

453
4
12

pdf: http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf – Attila Lendvai Oct 07 '14 at 13:23

score 25 · Answer 25 · answered Mar 18 '11 at 14:11

25

How to Write a Proof, by Leslie Lamport.

answered Mar 18 '11 at 14:11

Anthony Labarre

3,264
1
25
33

5

I read this and I read A Mathematician's Lament by Lockhart (http://www.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. – Marcos Villagra Apr 25 '11 at 05:02
6

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

score 24 · Answer 26 · answered Sep 12 '10 at 03:22

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.

ilyaraz · Answer 27 · 2011-04-29T21:39:49.177

22

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.

edited Apr 29 '11 at 21:39

answered Jan 19 '11 at 09:15

ilyaraz

1,569
18
33

can you add a link ? – Suresh Venkat Apr 25 '11 at 16:08

score 21 · Answer 28 · answered Sep 17 '10 at 03:34

21

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.

answered Sep 17 '10 at 03:34

Sariel Har-Peled

9,626
31
53

16

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
Fair enough, but IMHO for most of the papers suggested books are a better place to read this stuff. – Sariel Har-Peled Sep 23 '10 at 02:39
I see your point. I think that university scholarship is like one giant paper, in a way, with its own way of thinking. Some branches of philosophy refer to this process as lexification. But when it comes to someone who really invented/wrote or even lexified something huge and unique (like Turing), a mere mortal cannot hope to lexify it completely, and there will always be new secrets waiting there. – ixtmixilix Sep 26 '10 at 22:12
12

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: http://mathoverflow.net/questions/28268/do-you-read-the-masters – Kaveh Sep 29 '10 at 18:35
4

Its great when this happens. I just claim that it is somewhat rare. – Sariel Har-Peled Sep 30 '10 at 04: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
2

@Peter Taylor, I think that's why Sarah is mentioned. :) – Radu GRIGore Feb 09 '11 at 14:32
1

I once read the original paper of Kleene "Representation of Events in Nerve Nets and Finite Automata" in which regular expression are defined for the first time. This paper is far away of the presentation of this material in todays courses, and maybe a little to much complicated, but nevertheless there I learned about nerve nets. But to mention a counter-example from mathematics, I once read the paper "Algebraische Theorie der Körper" by E. Steinitz from 1910(!) when I took a course on Galois Theory and was very impressed by the fact that the theory on fields was almost identically in my cours – StefanH Jan 08 '14 at 23:22
I mean the paper presented the material almost identically to the way it was introduced in the course and terminology was very close. – StefanH Jan 08 '14 at 23:23

score 18 · Answer 29 · edited Sep 17 '10 at 13:08

18

N. Chomsky. Three models for the description of language. IEEE Transactions on Information Theory 3. 1956. doi: 10.1109/TIT.1956.1056813

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

edited Sep 17 '10 at 13:08

András Salamon

19,000
3
64
150

answered Sep 13 '10 at 10:05

mgalle

356
1
3

3

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

score 18 · Answer 30 · edited Dec 16 '10 at 17:42

18

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

edited Dec 16 '10 at 17:42

Konrad Rudolph

351
1
9

answered Oct 15 '10 at 16:04

Giorgio Camerani

6,842
1
34
64

6

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

score 18 · Answer 31 · edited Feb 04 '24 at 12:13

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

score 18 · Answer 32 · edited Jun 30 '13 at 06:27

18

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.

edited Jun 30 '13 at 06:27

Igor Pak

812
5
15

answered Nov 21 '11 at 20:49

Daniel

1
1
2

score 16 · Answer 33 · answered Sep 02 '11 at 19:16

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.

score 15 · Answer 34 · answered Sep 10 '13 at 00:45

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.

score 15 · Answer 35 · answered Oct 15 '10 at 16:11

15

Alan Turing's Computing Machinery and Intelligence.

answered Oct 15 '10 at 16:11

Giorgio Camerani

6,842
1
34
64

score 15 · Answer 36 · answered Mar 22 '11 at 23:38

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!

score 14 · Answer 37 · edited Nov 18 '10 at 23:35

Ethan Bernstein and Umesh Vazirani. Quantum Complexity Theory. SIAM J. Comput. Vol. 26 No. 5, pp. 1411-1473, October 1997. doi: 10.1137/S0097539796300921

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.

score 14 · Answer 38 · answered Nov 19 '10 at 07:35

14

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

answered Nov 19 '10 at 07:35

Yasser Sobhdel

654
6
16

score 14 · Answer 39 · edited Sep 20 '19 at 15:13

14

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.

edited Sep 20 '19 at 15:13

VS.

539
3
15

answered Jan 05 '11 at 16:08

giuper

1
2
2

score 14 · Answer 40 · edited Feb 15 '20 at 16:45

14

The mechanical evaluation of expressions by Peter J. Landin

Introduced:

the lambda calculus as a basis for defining a programming language,
abstract syntax,
the idea of meta-language to explain other languages,
imperative constructs to the lambda calculus.

edited Feb 15 '20 at 16:45

gadmm

307
1
8

answered Apr 26 '11 at 02:50

kunjan kshetri

101
1
4

score 13 · Answer 41 · edited Sep 12 '10 at 07:07

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.

score 13 · Answer 42 · answered Sep 15 '10 at 05:48

13

A fast quantum mechanical algorithm for database search - Lov K. Grover

answered Sep 15 '10 at 05:48

Pratik Deoghare

1,924
18
26

score 13 · Answer 43 · answered Sep 20 '10 at 19:04

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.

Definitely an evergreen classic. – András Salamon Oct 02 '10 at 16:57 — András Salamon, Oct 02 '10 at 16:57

András Salamon · Answer 44 · 2010-09-17T11:34:01.213

E. Mark Gold, Language Identification in the Limit, Information and Control 10, 447–474, 1967. doi: 10.1016/S0019-9958(67)91165-5

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.

score 11 · Answer 45 · answered Jul 10 '12 at 21:26

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

score 11 · Answer 46 · answered Sep 18 '10 at 10:38

11

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.

answered Sep 18 '10 at 10:38

MassimoLauria

1,841
16
21

score 11 · Answer 47 · answered Oct 14 '10 at 13:43

11

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

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

answered Oct 14 '10 at 13:43

yzll

428
1
3
9

score 10 · Answer 48 · answered Apr 25 '11 at 05:08

10

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.

answered Apr 25 '11 at 05:08

Marcos Villagra

3,290
27
45

score 10 · Answer 49 · answered Nov 21 '11 at 21:29

10

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.

answered Nov 21 '11 at 21:29

Opt

1,311
14
20

Peter · Answer 50 · 2011-11-22T02:46:30.467

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.

score 8 · Answer 51 · answered Sep 18 '10 at 10:33

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.

score 8 · Answer 52 · edited Sep 20 '19 at 15:13

8

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

This paper is the theoretical foundations of modern Cryptography.

edited Sep 20 '19 at 15:13

VS.

539
3
15

answered Jan 05 '11 at 16:05

giuper

1
2
2

score 7 · Answer 53 · edited Sep 15 '10 at 21:01

7

The theory of interstellar trade by Paul Krugman

edited Sep 15 '10 at 21:01

Martin Schwarz

5,496
25
41

answered Sep 15 '10 at 05:44

Pratik Deoghare

1,924
18
26

2

How does interstellar arbitrage (while undoubtedly interesting) relate to theoretical computer science? – András Salamon Sep 17 '10 at 11:32
5

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 08:30
4

The critique in the paper applies to TCS as well – Noam Oct 14 '10 at 19:39

score 6 · Answer 54 · answered Sep 12 '10 at 12:02

6

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.

answered Sep 12 '10 at 12:02

Mugizi Rwebangira

1,278
10
18

score 6 · Answer 55 · answered Jul 06 '11 at 06:24

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.

score 6 · Answer 56 · answered Dec 09 '11 at 09:59

6

Guy E. Blelloch: Programming Parallel Algorithms

Very clear introduction to parallel algorithms.

answered Dec 09 '11 at 09:59

Raphael

4,565
28
48

score 5 · Answer 57 · answered May 25 '11 at 12:51

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!

score 5 · Answer 58 · answered Nov 21 '11 at 21:41

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.

score 5 · Answer 59 · answered Nov 25 '11 at 23:59

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.

score 4 · Answer 60 · answered Sep 15 '10 at 05:50

4

Quantum Walks On Graphs Authors: Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh Vazirani

answered Sep 15 '10 at 05:50

Pratik Deoghare

1,924
18
26

score 4 · Answer 61 · answered Oct 19 '15 at 14:10

On Universal Learning Algorithms, Oded Goldreich and Dana Ron (1997), Information Processing Letters, Volume 63, Issue 3, pp. 131-136. (see also the updated version)

Adapting Levin's argument for the existence of an optimal algorithm for NP, the authors show that there exists a universal learning algorithm (in several learning settings, including PAC): "if a concept class is learnable, this algorithm will learn it, optimally."

Beyond the result itself, and perhaps more strikingly, this is also (as pointed out and discussed in the paper) a great illustration of the dangers of abusing $O(\cdot)$ notations and asymptotics.

score 4 · Answer 62 · edited Feb 04 '24 at 12:11

4

Fischer Black and Myron Scholes, The Pricing of Options and Corporate Liabilities https://web.archive.org/web/20231114103316/https://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.

edited Feb 04 '24 at 12:11

Ekene E.

121
4

answered May 24 '11 at 17:03

Raymond Hettinger

1
1

1

http://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Encryption/Probabilistic_Encryption.pdf – Andrea Girardi May 30 '11 at 17:20

score 4 · Answer 63 · answered Sep 02 '11 at 04:33

4

The RSA cryptosystem was described in a short elegant paper; it's very readable and created quite a stir even among non-scientists.

answered Sep 02 '11 at 04:33

Fixee

1,003
8
15

1

This is the Rivest/Shamir/Adleman paper as suggested by giuper, but this version has been typeset in TeX. – András Salamon Nov 23 '11 at 10:36

Aram Harrow · Answer 64 · 2019-05-08T15:08:03.990

My favorite piece of scientific writing is Charles Bennett's 1979 On Random and Hard-to-Describe Numbers which describes Chaitin's number. You should read it not because its scientific content will be useful to you, although it may be, but just for the quality of the writing. If you already know about Chaitin's number, just skip to the last paragraph on page 6 and read from there on.

I don't want to quote too much from the article, but here is the last sentence of the abstract.

Other, Cabalistic properties of $\Omega$ [Chaitin's number] are pointed out for the first time.

score 3 · Answer 65 · answered Nov 21 '11 at 21:07

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.

score 2 · Answer 66 · edited Feb 04 '24 at 12:12

Time/space tradeoffs for reversible computation (1989) by Charles Bennett: In this paper, Bennett introduces a pebble game to show that reversible computation can emulate any conventional computation with very reasonable space/time overheads. This method of emulating conventional computation with reversible computation will become increasingly practical in the future when energy efficient reversible computers and quantum computers become prominent.

score 2 · Answer 67 · answered Apr 13 '21 at 08:00

Ray Solomonoff:

A formal theory of inductive inference. Part I and Part II, 1964.
Complexity-based induction systems: Comparisons and convergence theorems. 1978

Kolmogorov:

Three Approaches to the Quantitative Definition of Information. 1965

Martin-Löf:

The definition of random sequences. 1966

Marvin Minsky said: The most important discovery since G"odel was the discovery by Chaitin, Solomonoff and Kolmogorov of the concept called Algorithmic Probability which is a fundamental new theory of how to make predictions given a collection of experiences and this is a beautiful theory, everybody should learn it, but it's got one problem, that is, that you cannot actually calculate what this theory predicts because it is too hard, it requires an infinite amount of work. However, it should be possible to make practical approximations to the Chaitin, Kolmogorov, Solomonoff theory that would make better predictions than anything we have today. Everybody should learn all about that and spend the rest of their lives working on it.

score 2 · Answer 68 · edited Sep 20 '19 at 08:46

Not specifically a topic in theoretical computer science, but I think an area that is fundamental to much of the work in data analysis and machine learning is a foundational paper in what are currently known as Graphical Models:

Lauritzen, Steffen L. and Spiegelhalter, David J., ( 1988) "Local Computations with Probabilities on Graphical Structures and their Application to Expert Systems", Journal of the Royal Statistical Society, Series B (Methodological)", 50(2) pp 157--224.

The way they solve the probability updating problem harkens back to earlier work on optimizing elimination orders for linear systems, and, subsequently is expanded on by Lauritzen to a larger class of dynamic programming style problems.

score 1 · Answer 69 · answered Jun 27 '12 at 20:49

Rumelhart, David E.; Hinton, Geoffrey E., Williams, Ronald J. (8 October 1986). "Learning representations by back-propagating errors". Nature 323 (6088): 533–536. DOI:10.1038/323533a0

The paper that introduced backpropagation and resuscitated neural networks.

score 1 · Answer 70 · answered Apr 06 '21 at 06:24

Expanders are special graph which are sparse yet highly connected. The challenge is to give an explicit construction of expanders. See the survey by Hoory-Linial-Wigderson-Expander Graphs and their Application for several applications of expanders. The most useful expanders are the ones with constant degree.If we have constant-sized object then we can freely use it without having to find a nice description for it. Also we can always find constant size in constant time by brute force approach.

An Elementary Construction of Constant-Degree Expanders by Alon-Schwartz-Shapira appeared in SODA 2007 and gave a wonderful construction of expanders using Replacement Product. In my opinion, the construction is so nice that this ought to be a part of lectures on Expanders. They apply the Replacement product only twice on Cayley expanders to obtain a constant-degree expanders. The construction is so combinatorial that one can even visualise the edges coming out of a cut.

score -1 · Answer 71 · edited Sep 20 '19 at 08:46

-1

The paper Multidimensional Divide-and-conquer by Jon L. Bentley discussed multidimensional divide-and-conquer, an algorithmic paradigm to solve problems in multidimensional divide-and-conquer.

It is really easy to read and helpful to solve lots of high-dimensional computation problem.

edited Sep 20 '19 at 08:46

VS.

539
3
15

answered Sep 09 '13 at 22:00

xiaom

41
4

score -1 · Answer 72 · edited Jun 27 '12 at 23:28

-1

The Base Rate Fallacy and its implications for the Difficulty of Intrusion Detection

Stefan Axelsson, "The Base-Rate Fallacy and its Implications for the Difficulty Of Intrusion", 1999

For those poor saps stuck waiting for IDS alerts, this shows that even if you're signature is 99% accurate, if it's a packet based IDS then you will still be overrun with false positives.

Comment - More generally an understanding of how Bayes rule applies to probabilistic inference, and how probabilistic graphical models are used illuminates many fallacies that arise in working with statistical data.

edited Jun 27 '12 at 23:28

Kaveh

21,577
8
82
183

answered May 25 '11 at 01:51

user5283

1
1

4

I think, in the context of this site, "everyone" should mean "every theoretical computer scientist". So why should we all be persuaded to read something that isn't even theoretical computer science? – David Eppstein Dec 30 '12 at 18:36

What papers should everyone read?

72 Answers72

Linked