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

This question is (inspired by)/(shamefully stolen from) a similar question at MathOverflow, but I expect the answers here will be quite different.

We all have favorite papers in our own respective areas of theory. Every once in a while, one finds a paper so astounding (e.g., important, compelling, deceptively simple, etc.) that one wants to share it with everyone. So list these papers here! They don't have to be from theoretical computer science -- anything that you think might appeal to the community is a fine answer.

You can give as many answers as you want; please put one paper per answer! Also, notice this is community wiki, so vote on everything you like!

(Note there has been a previous question about papers in recursion-theoretic complexity but that is quite specialized.)

share|improve this question
51  
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
5  
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
23  
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
show 2 more comments

68 Answers

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

share|improve this answer
6  
It is also very accessible and readable... –  Sariel Har-Peled Sep 12 '10 at 21:22
17  
and with it The Annotated Turing by Charles Petzold [Highly Recommended] –  Pratik Deoghare Sep 13 '10 at 10:28
show 1 more comment

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

share|improve this answer
3  
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
2  
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
show 4 more comments

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.

share|improve this answer
2  
Please, fix the link. It's broken. –  Oscar Mederos Feb 25 '11 at 1:44
show 3 more comments

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.

share|improve this answer
add comment

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

share|improve this answer
2  
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
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
show 5 more comments

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.

share|improve this answer
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
add comment

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)
share|improve this answer
1  
You should watch for combinatorial or support preconditioners. Expander graphs are even used in numerical analysis today. –  Martin Oct 5 '11 at 17:30
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
show 2 more comments

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
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
add comment

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.

share|improve this answer
show 1 more comment

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.

share|improve this answer
add comment

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

share|improve this answer
3  
I'd upvote you once for every Lambda paper if I could. –  jkff Sep 21 '10 at 16:43
add comment

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.

share|improve this answer
show 1 more comment

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.

share|improve this answer
add comment

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

share|improve this answer
18  
Anything by Phil Wadler is a good read. –  Dave Clarke Sep 20 '10 at 10:15
add comment

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.

share|improve this answer
show 1 more comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
show 1 more comment

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.

share|improve this answer
13  
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: mathoverflow.net/questions/28268/do-you-read-the-masters –  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
5  
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
show 4 more comments

How to Write a Proof, by Leslie Lamport.

share|improve this answer
3  
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. –  Marcos Villagra Apr 25 '11 at 5:02
1  
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
add comment

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

share|improve this answer
1  
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
add comment

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

share|improve this answer
4  
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
add comment

protected by Kaveh May 10 '13 at 6:51

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

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

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