<p><a href="https://web.archive.org/web/20150328061529/http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf" rel="nofollow noreferrer">&quot;A mathematical theory of communication&quot;</a> by Claude Shannon, classics of information theory. Very readable.</p>
<p>(<a href="http://www.mast.queensu.ca/%7Emath474/shannon1948.pdf" rel="nofollow noreferrer">Mirror</a>)</p>

CC BY-SA 4.0
2019-03-25T19:52:12.973Z
The safest general characterization of the Internet is that it consists of a series of footnotes to this paper.
Celal Ergün
CC BY-SA 4.0
2021-07-09T20:35:48.187Z
The Bell Labs link is broken.
rw-nandemo
CC BY-SA 4.0
2021-08-26T11:24:53.583Z
https://en.m.wikipedia.org/wiki/A_Mathematical_Theory_of_Communication#External_links
rofrol
CC BY-SA 4.0
2022-04-22T23:27:33.023Z
Just a note for readers of this paper that Shannon assumed that [differential entropy](https://en.wikipedia.org/wiki/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
CC BY-SA 4.0
2010-09-12T01:38:57.067Z
2024-02-04T10:31:40.687Z
2024-02-04T10:31:40.687Z
Grigory Yaroslavtsev
<p>The 1936 paper that arguably started computer science itself:</p>

<ul>
<li>Alan Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society s2-42, 230–265, 1937. <a href="http://dx.doi.org/10.1112/plms/s2-42.1.230">doi: 10.1112/plms/s2-42.1.230</a></li>
</ul>

<p>In just 36 pages, Turing formulates (but does not name) the Turing Machine, recasts Gödel's famous <a href="http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#First_incompleteness_theorem">First Incompleteness Theorem</a> 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).</p>

CC BY-SA 3.0
2014-03-18T20:43:40.370Z
Here is [a friendlier link to the paper](http://classes.soe.ucsc.edu/cmps210/Winter11/Papers/turing-1936.pdf).
jameshfisher
CC BY-SA 4.0
2021-05-18T14:09:45.080Z
@james The problem with friendly links is that they are more likely to break.
domotorp
CC BY-SA 2.5
2010-09-12T21:22:15.853Z
It is also very accessible and readable...
Sariel Har-Peled
CC BY-SA 2.5
2010-09-13T10:28:29.003Z
and with it The Annotated Turing by Charles Petzold [Highly Recommended]
Pratik Deoghare
CC BY-SA 3.0
2010-09-12T01:01:31.037Z
2012-08-16T09:00:39.377Z
2012-08-16T09:00:39.377Z
Henry Yuen
<p>Ken Thompson's "<a href="http://www.ece.cmu.edu/~ganger/712.fall02/papers/p761-thompson.pdf">Reflections on Trusting Trust</a>".  Short, sweet, and mind-blowing.</p>

CC BY-SA 3.0
2011-05-26T05:23:17.073Z
"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
CC BY-SA 3.0
2011-09-02T04:26:47.950Z
I would think this paper would be pretty difficult to digest without at least knowing what a compiler is.
Fixee
CC BY-SA 3.0
2013-09-10T06:50:36.353Z
In the paper, I think figures 2.1 and 2.2 are swapped.
Dennis
CC BY-SA 3.0
2017-10-29T22:59:10.880Z
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
CC BY-SA 4.0
2020-08-13T19:11:10.247Z
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
CC BY-SA 4.0
2021-07-09T20:56:47.033Z
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
CC BY-SA 2.5
2010-09-13T19:05:21.190Z
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
CC BY-SA 2.5
2010-09-15T01:15:44.163Z
just read it -- awesome indeed!
Lev Reyzin
CC BY-SA 3.0
2010-09-12T23:18:27.013Z
2012-01-01T19:28:36.177Z
2012-01-01T19:28:36.177Z
Jeffε
<p>Keshav's <a href="http://doi.acm.org/10.1145/1273445.1273458">How to Read a Paper</a>. You can also download the paper from <a href="http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/07/paper-reading.pdf">here</a>.</p>

CC BY-SA 3.0
2011-04-26T21:00:00.903Z
I always think that CS research papers are written in some foreign language.
Berlin Brown
CC BY-SA 3.0
2011-05-25T13:28:36.183Z
Very good! It is worth to be put on tagline banner on the site to be sure no one student miss that.
Vag
CC BY-SA 3.0
2012-06-21T04:02:12.970Z
The second link is currently broken
Christopher Manning
CC BY-SA 3.0
2012-06-27T13:14:54.960Z
@ChristopherManning thanks for pointing that out. I've updated the link.
philosodad
CC BY-SA 3.0
2013-09-10T07:07:16.237Z
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
CC BY-SA 3.0
2013-12-13T23:38:23.893Z
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
CC BY-SA 3.0
2017-05-30T09:09:29.857Z
I like this ones the best, three-pass approach really helped me comprehending first few papers easily.
Fahad Siddiqui
CC BY-SA 2.5
2010-10-15T08:30:48.137Z
Nice read indeed.
Anthony Labarre
CC BY-SA 3.0
2010-10-13T18:22:00.463Z
2012-06-27T13:14:09.720Z
2012-06-27T13:14:09.720Z
philosodad
<p><a href="https://doi.org/10.4153/CJM-1965-045-4" rel="noreferrer">Paths, Trees and Flowers</a> 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.</p>

CC BY-SA 4.0
2010-09-12T02:26:36.937Z
2019-09-20T01:25:52.450Z
2019-09-20T01:25:52.450Z
ilyaraz
<p><a href="http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf">Reducibility Among Combinatorial Problems</a> 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.</p>

CC BY-SA 3.0
2012-08-16T13:52:50.043Z
@Andras Salamon I agree 100%.
Tayfun Pay
CC BY-SA 2.5
2010-09-13T01:42:03.660Z
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
CC BY-SA 3.0
2010-09-12T06:26:13.563Z
2013-12-09T14:36:21.153Z
2013-12-09T14:36:21.153Z
Daniel Apon
<p>Hartmanis and Stearns, <a href="http://www.ams.org/mathscinet-getitem?mr=0170805">"On the computational complexity of algorithms"</a>, Transactions of the American Mathematical Society 117: 285–306 (1965)</p>

<p>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. </p>

CC BY-SA 4.0
2019-05-16T22:09:59.400Z
Working link. https://pdfs.semanticscholar.org/1ce8/9af300d9a7c64d3ee06175b24ca97763f9f2.pdf
scott m gardner
CC BY-SA 2.5
2010-09-12T00:51:25.603Z
2010-09-12T00:51:25.603Z
Ryan Williams
<p><a href="https://link.springer.com/article/10.1007%2FBF01886518" rel="nofollow noreferrer">Quantum Mechanical Computers</a> <a href="http://www.quantum-dynamic.eu/doc/feynman85_qmc_optics_letters.pdf" rel="nofollow noreferrer">(PDF)</a> by Richard Feynman. </p>

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

<p>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.</p>

CC BY-SA 3.0
2016-01-03T10:54:06.913Z
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
CC BY-SA 2.5
2010-10-01T14:21:26.853Z
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
CC BY-SA 2.5
2010-10-01T23:27:21.600Z
That's the one. I added a new link and a link to it's page on the publisher's website.
Robin Kothari
CC BY-SA 4.0
2010-09-12T02:26:50.610Z
2020-02-14T09:10:58.097Z
2020-02-14T09:10:58.097Z
Robin Kothari
<p><a href="http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf" rel="nofollow noreferrer">Expander graphs and their applications, S. Hoory, N. Linial, and A. Wigderson</a> is an extremely nice survey on expander graphs. No surprise that it won the 2008 AMS Conant Prize. </p>

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

<ul>
<li><a href="https://resources.mpi-inf.mpg.de/departments/d1/teaching/ws10/EG/Reingold_SL.pdf" rel="nofollow noreferrer">log-space algorithm for undirected connectivity</a> (by Reingold, STOC, 2005)</li>
<li><a href="https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-046/" rel="nofollow noreferrer">the alternative proof of the PCP Theorem</a> (by Dinur, ECCC, TR05-046, 2005)</li>
</ul>

<p>and not so recent:</p>

<ul>
<li><a href="https://hungary.pure.elsevier.com/en/publications/on-log-n-sorting-network" rel="nofollow noreferrer">AKS sorting network, which achieves depth <span class="math-container">$O(\log n)$</span> and size <span class="math-container">$O(n \log n)$</span> for sorting <span class="math-container">$n$</span> inputs</a> (by Ajtai, Komlós and Szemerédi, STOC, 1983)</li>
<li><a href="http://www.cs.yale.edu/homes/spielman/Research/ITsuperc.pdf" rel="nofollow noreferrer">Linear-time encodable and decodable error-correcting codes</a> (by Spielman, STOC, 1995)</li>
</ul>

CC BY-SA 3.0
2011-10-05T17:30:00.567Z
You should watch for combinatorial or support preconditioners. Expander graphs are even used in numerical analysis today.
shuhalo
CC BY-SA 4.0
2020-05-22T23:50:49.673Z
@shuhalo Can you give an example?
Elle Najt
CC BY-SA 4.0
2010-09-17T08:20:56.807Z
2019-09-20T08:45:56.500Z
2019-09-20T08:45:56.500Z
Dai Le
<p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.7.9472">Hundreds of Impossibility Results for Distributed Computing</a> 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.</p>

CC BY-SA 4.0
2018-10-09T21:54:46.873Z
Publisher's version: https://doi.org/10.1007/s00446-003-0091-y
András Salamon
CC BY-SA 4.0
2019-09-22T01:11:30.617Z
can you please add the year to the answer
Narek Bojikian
CC BY-SA 2.5
2010-09-12T01:57:31.333Z
2010-09-12T01:57:31.333Z
Aaron Sterling
<p>Les Valiant's <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.94.6289&amp;rep=rep1&amp;type=pdf">Theory of the Learnable</a> (1984) set the agenda for learning theory for decades, and it's a nice and readable paper!</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-12T02:18:31.610Z
2010-09-24T14:38:18.273Z
2010-09-24T14:38:18.273Z
Lev Reyzin
<p><a href="http://arxiv.org/abs/quant-ph/9508027v2">Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer - Peter W. Shor</a> 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 <a href="http://en.wikipedia.org/wiki/Integer_factorization">GNFS</a>.</p>

CC BY-SA 3.0
2010-09-15T05:46:35.900Z
2011-09-06T01:37:51.567Z
2011-09-06T01:37:51.567Z
Pratik Deoghare
<p>Perhaps too basic, but I'm shocked that nobody has mentioned the original Lambda papers by Steele and Sussman: <a href="https://dspace.mit.edu/handle/1721.1/5794" rel="nofollow noreferrer">SCHEME: An Interpreter for Extended Lambda Calculus</a>, <a href="https://dspace.mit.edu/handle/1721.1/5790" rel="nofollow noreferrer">Lambda: The Ultimate Imperative</a>, <a href="https://dspace.mit.edu/handle/1721.1/6091" rel="nofollow noreferrer">Lambda: The Ultimate Declarative</a>.</p>

CC BY-SA 2.5
2010-09-21T16:43:52.210Z
I'd upvote you once for every Lambda paper if I could.
jkff
CC BY-SA 4.0
2010-09-21T15:36:11.563Z
2019-09-20T07:44:47.617Z
2019-09-20T07:44:47.617Z
sclv
<p>John McCarthy's <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.9776">Recursive functions of symbolic expressions and their computation by machine, part I.</a></p>

<p>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.</p>

CC BY-SA 2.5
2010-09-24T13:35:48.070Z
2010-09-24T13:35:48.070Z
Per Vognsen
<p><a href="http://homepages.inf.ed.ac.uk/wadler/papers/dual/dual.pdf">Call-by-value is dual to call-by-name</a> by Philip Wadler is a good read.</p>

CC BY-SA 2.5
2010-09-20T10:15:05.280Z
Anything by Phil Wadler is a good read.
Dave Clarke
CC BY-SA 2.5
2010-09-20T10:00:42.843Z
2010-09-20T10:00:42.843Z
lyonanderson
<p>C.A.R. Hoare, <a href="https://www.google.com/search?q=an+axiomatic+basis+for+computer+programming">An Axiomatic Basis for Computer Programming</a>.</p>

<p>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.</p>

<p>It has six pages that are quite easy to follow.</p>

CC BY-SA 3.0
2010-09-12T12:14:12.037Z
2012-08-14T19:33:15.087Z
2012-08-14T19:33:15.087Z
Radu GRIGore
<p><a href="http://4mhz.de/cook.html">The complexity of theorem-proving procedures</a> 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.</p>

<p>The importance of this result is (at least) twofold: first, it shows that there exist problems in <b>NP</b> which are at least as hard as the whole class, the <b>NP</b>-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.</p>

<p>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 <b>NP</b>-complete with respect to Karp reductions.</p>

CC BY-SA 2.5
2010-09-12T16:42:38.867Z
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
CC BY-SA 2.5
2010-09-12T09:20:24.960Z
2010-09-12T09:20:24.960Z
Antonio E. Porreca
<p>Alon, Matias and Szegedy, <a href="http://dx.doi.org/10.1006/jcss.1997.1545">The space complexity of approximating the frequency moments</a>, JCSS 58(1):137-147, 1999.</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-12T22:09:16.937Z
dang. I was going to add this one :)
Suresh Venkat
CC BY-SA 2.5
2010-09-12T16:06:35.430Z
2010-09-12T16:06:35.430Z
arnab
<p>I recommend reading Savitch's paper. It basically states that, for any function $f(n) \ge \log(n)$,</p>

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

<p>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.</p>

<p><a href="http://linkinghub.elsevier.com/retrieve/pii/S002200007080006X">Savitch, Walter J. (1970), "Relationships between nondeterministic and deterministic tape complexities", Journal of Computer and System Sciences 4 (2): 177–192.</a></p>

CC BY-SA 2.5
2010-09-12T06:29:19.857Z
2010-09-12T19:38:36.957Z
2010-09-12T19:38:36.957Z
Sadeq Dousti
<p>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.</p>

<p><a href="http://www.cs.umass.edu/~immerman/pub/space.ps">N. Immerman, Nondeterministic space is closed under complementation, SIAM Journal on Computing 17, 1988, pp. 935–938.</a></p>

CC BY-SA 3.0
2012-06-27T14:00:33.110Z
To be fair, Szelepcsényi's paper, "The method of forced enumeration for nondeterministic automata," is just as nice.
Lev Reyzin
CC BY-SA 2.5
2010-09-12T04:02:29.320Z
2010-09-12T04:02:29.320Z
Michaël Cadilhac
<p><a href="http://www.cs.berkeley.edu/%7Eluca/pubs/extractor-full.pdf">Extractors and Pseudorandom Generators</a> 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.</p>

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

CC BY-SA 2.5
2010-09-12T03:22:37.557Z
2010-09-12T03:22:37.557Z
ilyaraz
<p><a href="http://www.ma.huji.ac.il/~kalai/kkl.ps">The influence of variables on boolean functions, J. Kahn, G. Kalai and N. Linial</a></p>

<p>This paper introduced Fourier techniques for TCS community and solved very neat open problem.</p>

<p>I find this paper very readable.</p>

CC BY-SA 3.0
2011-04-25T16:08:06.700Z
can you add a link  ?
Suresh Venkat
CC BY-SA 3.0
2011-01-19T09:15:03.213Z
2011-04-29T21:39:49.177Z
2011-04-29T21:39:49.177Z
ilyaraz
<p>If I may quote Sarah Palin on this issue: "All of them". </p>

<p>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.</p>

CC BY-SA 2.5
2011-01-19T11:28:10.043Z
You say "All of them", but don't you then argue for "None of them"?
Peter Taylor
CC BY-SA 2.5
2011-02-09T14:32:20.813Z
@Peter Taylor, I think that's why Sarah is mentioned. :)
Radu GRIGore
CC BY-SA 3.0
2014-01-08T23:22:03.570Z
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
CC BY-SA 3.0
2014-01-08T23:23:07.810Z
I mean the paper presented the material almost identically to the way it was introduced in the course and terminology was very close.
StefanH
CC BY-SA 2.5
2010-09-17T11:35:57.980Z
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
CC BY-SA 2.5
2010-09-23T02:39:00.513Z
Fair enough, but IMHO for most of the papers suggested books are a better place to read this stuff.
Sariel Har-Peled
CC BY-SA 2.5
2010-09-26T22:12:38.150Z
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
CC BY-SA 2.5
2010-09-29T18:35:54.187Z
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
CC BY-SA 2.5
2010-09-30T04:14:26.447Z
Its great when this happens. I just claim that it is somewhat rare.
Sariel Har-Peled
CC BY-SA 2.5
2010-09-17T03:34:50.637Z
2010-09-17T03:34:50.637Z
Sariel Har-Peled
<ul>
<li>N. Chomsky. Three models for the description of language. IEEE Transactions on Information Theory 3. 1956. <a href="http://dx.doi.org/10.1109/TIT.1956.1056813">doi: 10.1109/TIT.1956.1056813</a></li>
</ul>

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

CC BY-SA 2.5
2010-09-17T13:10:35.057Z
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
CC BY-SA 2.5
2010-09-13T10:05:27.600Z
2010-09-17T13:08:15.547Z
2010-09-17T13:08:15.547Z
mgalle
<p>Kurt Gödel's <a href="http://www.csee.wvu.edu/~xinl/library/papers/math/Godel.pdf">On formally undecidable propositions of Principia Mathematica and related systems</a>.</p>

CC BY-SA 3.0
2011-04-26T20:02:57.617Z
This is important, though I do think that later treatments on the subject are easier to read than the original.
Rob
CC BY-SA 2.5
2010-10-15T16:04:44.803Z
2010-12-16T17:42:32.617Z
2010-12-16T17:42:32.617Z
Giorgio Camerani
<p><A HREF="http://www.cs.virginia.edu/~robins/YouAndYourResearch.html">You and Your Research</A> by Richard Hamming.</p>

<p>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.</p>

<p>Update: <a href="http://www.youtube.com/watch?v=a1zDuOPkMSw">here</a> is the later version of this talk.</p>

CC BY-SA 3.0
2011-11-21T20:49:15.660Z
2013-06-30T06:27:09.470Z
2013-06-30T06:27:09.470Z
Daniel
<p><a href="https://dl.acm.org/doi/10.1145/359576.359579" rel="nofollow noreferrer">&quot;Can Programming Be Liberated from the von Neumann Style?</a> A Functional Style and Its Algebra of Programs&quot; 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.</p>
<p>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.</p>

CC BY-SA 4.0
2011-05-28T16:07:27.640Z
2024-02-04T12:13:48.167Z
2024-02-04T12:13:48.167Z
Paul Topping
<p><a href="http://www.sciencedirect.com/science/article/pii/S002200009791494X">Natural Proofs</a> by Razborov and Rudich.</p>

<p>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.</p>

CC BY-SA 3.0
2011-09-02T19:16:11.927Z
2011-09-02T19:16:11.927Z
Ashley Montanaro
<p>Russell Impagliazzo's <a href="http://cseweb.ucsd.edu/~russell/average.ps">A Personal View of Average-Case Complexity</a>. 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.</p>

CC BY-SA 2.5
2011-03-19T16:44:29.237Z
2011-03-19T16:44:29.237Z
Steve Flammia
<p><a href="http://doi.acm.org/10.1145/227683.227684">Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming</a> by Goemans and Williamson.</p>

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

CC BY-SA 3.0
2014-10-07T13:23:49.060Z
pdf: http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf
Attila Lendvai
CC BY-SA 2.5
2010-09-12T15:35:31.230Z
2010-09-12T15:35:31.230Z
Gianluca Della Vedova
<p><a href="http://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-how-to-write.pdf">How to Write a Proof</a>, by Leslie Lamport.</p>

CC BY-SA 3.0
2011-04-25T05:02:46.527Z
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
CC BY-SA 3.0
2011-05-17T11:27:36.903Z
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
CC BY-SA 2.5
2011-03-18T14:11:13.113Z
2011-03-18T14:11:13.113Z
Anthony Labarre
<p>There are two essays (but not paper) which are very handy after reading all the suggested papers:<br>
1.<a href="http://www.wisdom.weizmann.ac.il/~oded/PS/re-writing.pdf">How to write papers</a><br>
2.<a href="http://www.cs.iastate.edu/~honavar/write-not.pdf">How not to write papers</a><br>
Both by Oded Goldreich </p>

CC BY-SA 2.5
2010-11-19T07:35:42.770Z
2010-11-19T07:35:42.770Z
Yasser Sobhdel
<p>Ronald L. Rivest, Adi Shamir, Leonard M. Adleman: <a href="https://people.csail.mit.edu/rivest/Rsapaper.pdf" rel="nofollow noreferrer">A Method for Obtaining Digital Signatures and Public-Key Cryptosystems</a>. Commun. ACM (CACM) 21(2):120-126 (1978)</p>

<p>If your are interested in Crypto/Security, this is a very nice reading.</p>

CC BY-SA 4.0
2011-01-05T16:08:58.120Z
2019-09-20T15:13:21.580Z
2019-09-20T15:13:21.580Z
giuper
<p><a href="https://academic.oup.com/comjnl/article/6/4/308/375725" rel="nofollow noreferrer">The mechanical evaluation of expressions</a> by Peter J. Landin</p>

<p>Introduced:</p>

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

CC BY-SA 4.0
2011-04-26T02:50:06.720Z
2020-02-15T16:45:27.577Z
2020-02-15T16:45:27.577Z
kunjan kshetri
<ul>
<li>Ethan Bernstein and Umesh Vazirani. <a href="http://www.cs.berkeley.edu/~vazirani/pubs/bv.ps"><em>Quantum Complexity Theory</em></a>. SIAM J. Comput. Vol. 26 No. 5, pp. 1411-1473, October 1997. <a href="http://dx.doi.org/10.1137/S0097539796300921">doi: 10.1137/S0097539796300921</a></li>
</ul>

<p>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.</p>

CC BY-SA 2.5
2010-09-12T23:41:34.500Z
2010-11-18T23:35:52.373Z
2010-11-18T23:35:52.373Z
Marcos Villagra
<p><a href="http://arxiv.org/abs/quant-ph/9605043">A fast quantum mechanical algorithm for database search
- Lov K. Grover</a></p>

CC BY-SA 2.5
2010-09-15T05:48:10.187Z
2010-09-15T05:48:10.187Z
Pratik Deoghare
<p><a href="http://www.math.elte.hu/~lovasz/scans/lll.pdf">Factoring Polynomials with Rational Coefficients</a> 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.</p>

<p>While the algorithm has since been optimized and the polynomial factoring algorithm has been simplified (see <a href="http://cs.nyu.edu/yap/book/berlin/">Yap's book</a>, <a href="http://cs.nyu.edu/~yap/book/alge/ftpSite/l9.ps.gz">chap. 9</a>, for a good reference), the original paper has a good description of the lattice reduction algorithm.</p>

CC BY-SA 2.5
2010-09-12T06:53:57.537Z
2010-09-12T07:07:45.407Z
2010-09-12T07:07:45.407Z
user834
<p><a href="http://dx.doi.org/10.1090/S0002-9904-1944-08111-1">Emil Post's "Recursively enumerable sets of positive integers and their decision problems."</a>  Bull. Amer. Math. Soc. 50 (1944), 284-316. </p>

<p>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:</p>

<ul>
<li>Many-one reduction (and one-one reduction)</li>
<li>Truth-table reduction</li>
<li>Simple sets (=complements of immune sets), hypersimple sets</li>
<li>Creative sets (later used in papers regarding the Berman-Hartmanis isomorphism conjecture)</li>
</ul>

<p>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.</p>

CC BY-SA 2.5
2010-10-02T16:57:48.023Z
Definitely an evergreen classic.
András Salamon
CC BY-SA 2.5
2010-09-20T19:04:35.547Z
2010-09-20T19:04:35.547Z
Joshua Grochow
<ul>
<li>E. Mark Gold, <em>Language Identification in the Limit</em>, Information and Control <strong>10</strong>, 447–474, 1967. <a href="http://dx.doi.org/10.1016/S0019-9958%2867%2991165-5">doi: 10.1016/S0019-9958(67)91165-5</a></li>
</ul>

<p>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.</p>

CC BY-SA 2.5
2010-09-16T17:17:18.320Z
2010-09-17T11:34:01.213Z
2010-09-17T11:34:01.213Z
András Salamon
<p><a href="http://people.csail.mit.edu/rivest/BlumFloydPrattRivestTarjan-TimeBoundsForSelection.pdf">Time bounds for Selection</a> by Blum, Floyd, Pratt, Rivest and Tarjan. </p>

<p>Very elegant algorithm. Plus it has four Turing award winners as authors.</p>

CC BY-SA 2.5
2010-10-14T13:43:03.063Z
2010-10-14T13:43:03.063Z
yzll
<p><a href="http://www.lri.fr/perso/~mdr/pcp-newproof.pdf">PCP Theorem by Gap Amplification</a> by Irit Dinur</p>

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

CC BY-SA 3.0
2012-07-10T21:26:06.227Z
2012-07-10T21:26:06.227Z
Bill Fahle
<p>Another very nice paper in proof complexity is</p>

<p><a href="http://www.cs.technion.ac.il/~eli/papers/width-journal03.ps">Ben-Sasson, Wigderson - Short proofs are narrow, Resolution made simple</a></p>

<p>Notice that even this paper gives a new technique which simplifies previous results.</p>

CC BY-SA 2.5
2010-09-18T10:38:17.687Z
2010-09-18T10:38:17.687Z
MassimoLauria
<blockquote>
  <p><a href="http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf">PRIMES in
  P</a>
  by Agrawal, Kayal, Saxena</p>
</blockquote>

<p>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. </p>

<p>The authors received the Gödel Prize and the Fulkerson Prize for this work.</p>

CC BY-SA 3.0
2013-09-10T00:45:26.540Z
2013-09-10T00:45:26.540Z
Subhayan
<p>Alan Turing's <a href="http://www.cs.umbc.edu/courses/471/papers/turing.pdf">Computing Machinery and Intelligence</a>.</p>

CC BY-SA 2.5
2010-10-15T16:11:42.587Z
2010-10-15T16:11:42.587Z
Giorgio Camerani
<p>R. Moser and G. Tardos: <a href="http://arxiv.org/abs/0903.0544">A constructive proof of the general Lovasz Local Lemma</a></p>

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

<p>Great result and nice paper!</p>

CC BY-SA 2.5
2011-03-22T23:38:39.917Z
2011-03-22T23:38:39.917Z
Marc Bury
<p>This is a classic!</p>

<p><a href="http://dx.doi.org/10.1109/SFCS.1977.24">Probabilistic Computations: Toward a Unified Measure of Complexity</a>. Andrew Yao. FOCS'77.</p>

<p>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.</p>

CC BY-SA 3.0
2011-04-25T05:08:34.853Z
2011-04-25T05:08:34.853Z
Marcos Villagra
<p><a href="http://arxiv.org/abs/cs/0111050">Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time</a> by Daniel Spielman and Shang-Hua Teng for introducing smoothed analysis and showing it's success in explaining the behavior of the simplex algorithm.</p>

CC BY-SA 3.0
2011-11-21T21:29:55.390Z
2011-11-21T21:29:55.390Z
Opt
<p>The paper <a href="http://dx.doi.org/10.1145/3149.214121">Impossibility of distributed consensus with one faulty process</a> 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 <strong>indistinguishability</strong> 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.</p>

CC BY-SA 3.0
2011-11-22T02:31:32.703Z
2011-11-22T02:46:30.467Z
2011-11-22T02:46:30.467Z
Peter
<p>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).</p>

<p>The first one is </p>

<p><a href="http://www.cs.toronto.edu/~toni/Papers/beame-pitassi.ps">Beame, Pitassi - Simplified and improved Resolution lower bounds</a></p>

<p>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.</p>

CC BY-SA 2.5
2010-09-18T10:33:07.163Z
2010-09-18T10:33:07.163Z
MassimoLauria
<p>Shafi Goldwasser, Silvio Micali: <a href="https://groups.csail.mit.edu/cis/pubs/shafi/1984-jcss.pdf" rel="nofollow noreferrer">Probabilistic Encryption</a>. J. Comput. Syst. Sci. 28(2): 270-299 (1984)</p>

<p>This paper is the theoretical foundations of modern Cryptography. </p>

CC BY-SA 4.0
2011-01-05T16:05:36.363Z
2019-09-20T15:13:34.900Z
2019-09-20T15:13:34.900Z
giuper
<p>Bill Gasarch's <a href="http://www.cs.umd.edu/~gasarch/papers/poll.pdf">P v NP poll</a></p>

<p>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.</p>

CC BY-SA 2.5
2010-09-12T12:02:22.243Z
2010-09-12T12:02:22.243Z
Mugizi Rwebangira
<p>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 <a href="http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz" rel="noreferrer">Dancing Links</a> a very interesting read. </p>

<p>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 <a href="http://en.wikipedia.org/wiki/Exact_cover" rel="noreferrer">exact cover problem</a> 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.</p>

CC BY-SA 3.0
2011-07-06T06:24:24.670Z
2011-07-06T06:24:24.670Z
thorsten muller
<p>Guy E. Blelloch: <a href="http://dx.doi.org/10.1145/227234.227246" rel="noreferrer">Programming Parallel Algorithms</a></p>

<p>Very clear introduction to parallel algorithms.</p>

CC BY-SA 3.0
2011-12-09T09:59:05.440Z
2011-12-09T09:59:05.440Z
Raphael
<p><a href="http://www.princeton.edu/~pkrugman/interstellar.pdf" rel="nofollow">The theory of <strong>interstellar trade</strong> by Paul Krugman</a></p>

CC BY-SA 2.5
2010-09-17T11:32:17.690Z
How does interstellar arbitrage (while undoubtedly interesting) relate to theoretical computer science?
András Salamon
CC BY-SA 2.5
2010-09-24T08:30:33.253Z
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
CC BY-SA 2.5
2010-10-14T19:39:36.467Z
The critique in the paper applies to TCS as well
Noam
CC BY-SA 2.5
2010-09-15T05:44:17.840Z
2010-09-15T21:01:42.823Z
2010-09-15T21:01:42.823Z
Pratik Deoghare
<p>Allen Newell and Herbert A. Simon’s <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.104.2482&amp;rep=rep1&amp;type=pdf" rel="noreferrer">“Computer Science as Empirical Inquiry: Symbols and Search”</a> (direct PDF link).  </p>

<p>This quote summarizes it:  </p>

<blockquote>
  <p>“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”</p>
</blockquote>

<p>It's also very readable!</p>

CC BY-SA 3.0
2011-05-25T12:51:17.827Z
2011-05-25T12:51:17.827Z
Agos
<p>Some great suggestions are included in the reading list of the <a href="http://www.cs.berkeley.edu/~christos/classics/cs298.html" rel="noreferrer">Reading the Classics</a> course given by Christos Papadimitriou at Berkeley. Some of them have been mentioned in previous answers already. Notable exception: <a href="http://www.cs.berkeley.edu/~christos/classics/euler.pdf" rel="noreferrer">Euler's Königsberg Bridge Problem</a>.</p>

CC BY-SA 3.0
2011-11-25T23:59:51.750Z
2011-11-25T23:59:51.750Z
Dimitris
<p><a href="http://arxiv.org/abs/quant-ph/0012090" rel="nofollow"><strong>Quantum Walks On Graphs</strong> 
Authors: Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh Vazirani</a></p>

CC BY-SA 2.5
2010-09-15T05:50:13.510Z
2010-09-15T05:50:13.510Z
Pratik Deoghare
<p>The RSA cryptosystem was described in a <a href="http://people.csail.mit.edu/rivest/Rsapaper.pdf" rel="nofollow">short elegant paper</a>; it's very readable and created quite a stir even among non-scientists.</p>

CC BY-SA 3.0
2011-11-23T10:36:46.437Z
This is the Rivest/Shamir/Adleman paper as suggested by giuper, but this version has been typeset in TeX.
András Salamon
CC BY-SA 3.0
2011-09-02T04:33:21.343Z
2011-09-02T04:33:21.343Z
Fixee
<p><a href="http://www.sciencedirect.com/science/article/pii/S0020019097001178" rel="nofollow">On Universal Learning Algorithms</a>, Oded Goldreich and Dana Ron (1997), Information Processing Letters, Volume 63, Issue 3, pp. 131-136. (see also the <a href="http://www.wisdom.weizmann.ac.il/~oded/p_ul.html" rel="nofollow">updated version</a>)</p>

<p>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): <em>"if a concept class is learnable, this algorithm will learn it, optimally."</em></p>

<p>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.</p>

CC BY-SA 3.0
2015-10-19T14:10:36.803Z
2015-10-19T14:10:36.803Z
Clement C.
<p>Fischer Black and Myron Scholes, The Pricing of Options and Corporate Liabilities
<a href="http://www.cs.princeton.edu/courses/archive/fall09/cos323/papers/black_scholes73.pdf%22The%20Pricing%20of%20Options%20and%20Corporate%20Liabilities%22" rel="nofollow noreferrer">https://web.archive.org/web/20231114103316/https://www.cs.princeton.edu/courses/archive/fall09/cos323/papers/black_scholes73.pdf</a></p>
<p>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.</p>

CC BY-SA 3.0
2011-05-30T17:20:37.197Z
http://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Encryption/Probabilistic_Encryption.pdf
Andrea Girardi
CC BY-SA 4.0
2011-05-24T17:03:15.757Z
2024-02-04T12:11:09.730Z
2024-02-04T12:11:09.730Z
Raymond Hettinger
<p><a href="http://arxiv.org/abs/quant-ph/0301040" rel="noreferrer">A Simple Proof that Toffoli and Hadamard are Quantum Universal</a>, D. Aharonov summarising a result found by Yaoyun Shi.</p>

<p>Because it is a simple, well written, 4 pages paper which makes you think and realise that  Quantum Computation can be done with just <em>two</em> elementary blocks, from which <em>one</em> is a universal classical gate.</p>

CC BY-SA 3.0
2011-11-21T21:41:10.643Z
2011-11-21T21:41:10.643Z
Juan Bermejo Vega
<p>Although not published in a scientific journal, Vannevar Bush's <a href="http://www.theatlantic.com/magazine/archive/1945/07/as-we-may-think/3881/" rel="nofollow">As We May Think</a> has influenced much work in the computer science field, including hypertext, the personal computer, digital libraries, and the Internet. It even has it's <a href="http://en.wikipedia.org/wiki/As_We_May_Think" rel="nofollow">own Wikipedia article</a>, for god's sake.</p>

CC BY-SA 3.0
2011-11-21T21:07:28.170Z
2011-11-21T21:07:28.170Z
Adam Mikeal
<p>My favorite piece of scientific writing is Charles Bennett's 1979 <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.3492" rel="nofollow noreferrer">On Random and Hard-to-Describe Numbers</a> 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.</p>

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

<blockquote>
  <p>Other, Cabalistic properties of <span class="math-container">$\Omega$</span> <em>[Chaitin's number]</em> are pointed out for the first time.</p>
</blockquote>

CC BY-SA 4.0
2019-05-08T15:01:48.520Z
2019-05-08T15:08:03.990Z
2019-05-08T15:08:03.990Z
Aram Harrow
<p>Ray Solomonoff:</p>
<ul>
<li><p>A formal theory of inductive inference. Part I and Part II, 1964.</p>
</li>
<li><p>Complexity-based induction systems: Comparisons and convergence theorems. 1978</p>
</li>
</ul>
<p>Kolmogorov:</p>
<ul>
<li>Three Approaches to the Quantitative Definition of Information. 1965</li>
</ul>
<p>Martin-Löf:</p>
<ul>
<li>The definition of random sequences. 1966</li>
</ul>
<blockquote>
<p>Marvin Minsky said: The most important discovery since G&quot;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.</p>
</blockquote>

CC BY-SA 4.0
2021-04-13T08:00:11.897Z
2021-04-13T08:00:11.897Z
Xi Li
<p>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:</p>

<p>Lauritzen, Steffen L. and Spiegelhalter, David J., ( 1988) "<a href="https://www.jstor.org/stable/2345762?seq=1#metadata_info_tab_contents" rel="nofollow noreferrer">Local Computations with Probabilities on Graphical Structures and their Application to Expert Systems</a>", Journal of the Royal Statistical Society, Series B (Methodological)", 50(2) pp 157--224.</p>

<p>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. </p>

CC BY-SA 4.0
2011-07-06T01:07:52.477Z
2019-09-20T08:46:00.020Z
2019-09-20T08:46:00.020Z
John Mark Agosta
<p><a href="https://web.archive.org/web/20220505020435/https://mathweb.ucsd.edu/%7Esbuss/CourseWeb/Math268_2013W/Bennett_Tradeoffs.pdf" rel="nofollow noreferrer">Time/space tradeoffs for reversible computation (1989)</a> 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.</p>

CC BY-SA 4.0
2018-10-08T15:45:49.730Z
2024-02-04T12:12:50.487Z
2024-02-04T12:12:50.487Z
Joseph Van Name
<p>Rumelhart, David E.; Hinton, Geoffrey E., Williams, Ronald J. (8 October 1986). "Learning representations by back-propagating errors". Nature 323 (6088): 533–536. DOI:<a href="http://dx.doi.org/10.1038/323533a0" rel="nofollow">10.1038/323533a0</a></p>

<p>The paper that introduced backpropagation and resuscitated neural networks.</p>

CC BY-SA 3.0
2012-06-27T20:49:11.590Z
2012-06-27T20:49:11.590Z
mrig
<p>Expanders are special graph which are sparse yet highly connected. The challenge is to give an explicit construction of expanders. See the survey by <em>Hoory-Linial-Wigderson-Expander Graphs and their Application</em> 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.</p>
<p><a href="http://www.cs.tau.ac.il/%7Enogaa/PDFS/expander7.pdf" rel="nofollow noreferrer">An Elementary Construction of Constant-Degree Expanders</a> by <em>Alon-Schwartz-Shapira</em> 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.</p>

CC BY-SA 4.0
2021-04-06T06:24:22.190Z
2021-04-06T06:24:22.190Z
akr_
<p>The Base Rate Fallacy and its implications for the Difficulty of Intrusion Detection</p>

<p>Stefan Axelsson, "<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.432" rel="nofollow">The Base-Rate Fallacy and its Implications for the Difficulty Of Intrusion</a>", 1999 </p>

<p>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.</p>

<p><em>Comment</em> - 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. </p>

CC BY-SA 3.0
2012-12-30T18:36:56.113Z
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
CC BY-SA 3.0
2011-05-25T01:51:01.547Z
2012-06-27T23:28:24.410Z
2012-06-27T23:28:24.410Z
user5283
<p>The paper <a href="http://akira.ruc.dk/~keld/teaching/algoritmedesign_f04/Artikler/12/Bentley80.pdf" rel="nofollow noreferrer">Multidimensional Divide-and-conquer</a> by Jon L. Bentley discussed multidimensional divide-and-conquer, an algorithmic paradigm to solve problems in multidimensional divide-and-conquer.</p>

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

CC BY-SA 4.0
2013-09-09T22:00:45.990Z
2019-09-20T08:46:10.050Z
2019-09-20T08:46:10.050Z
xiaom
<p>This question is (inspired by)/(shamefully stolen from) a <a href="https://mathoverflow.net/questions/2144/a-single-paper-everyone-should-read">similar question at MathOverflow</a>, but I expect the answers here will be quite different. </p>

<p>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 <em>have</em> to be from theoretical computer science -- anything that you think might appeal to the community is a fine answer.</p>

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

<p>(Note there has been a previous question about <a href="https://cstheory.stackexchange.com/questions/811/what-are-the-classic-papers-from-the-recursion-theoretic-area-of-complexity-theor">papers in recursion-theoretic complexity</a> but that is quite specialized.)</p>

CC BY-SA 3.0
2012-09-20T05:18:11.397Z
see also mathoverflow, [What are the most important results (and papers) in complexity theory that every one should know?](http://mathoverflow.net/questions/34487/what-are-the-most-important-results-and-papers-in-complexity-theory-that-every)
vzn
CC BY-SA 4.0
2023-06-10T14:00:21.913Z
There is a book along similar lines: **Ideas That Created the Future: Classic Papers of Computer Science** by Harry R Lewis.
Nishant
CC BY-SA 2.5
2010-09-12T09:46:21.163Z
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
CC BY-SA 2.5
2010-09-12T16:22:48.360Z
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
CC BY-SA 2.5
2010-09-16T19:18:47.757Z
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
CC BY-SA 2.5
2010-09-26T22:07:15.357Z
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
<big-list><soft-question>
What papers should everyone read?
Ryan Williams
# What papers should everyone read?

(Asked by: username_0 on 2010-09-12)

This question is (inspired by)/(shamefully stolen from) a [similar question at MathOverflow](https://mathoverflow.net/questions/2144/a-single-paper-everyone-should-read), 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](https://cstheory.stackexchange.com/questions/811/what-are-the-classic-papers-from-the-recursion-theoretic-area-of-complexity-theor) but that is quite specialized.)

**Tags:** big-list, soft-question

> **Comments:**
> **username_3**: 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...  
> **username_0**: 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)  
> **username_4**: 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.  
> **username_5**: 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.  
> **username_1**: see also mathoverflow, [What are the most important results (and papers) in complexity theory that every one should know?](http://mathoverflow.net/questions/34487/what-are-the-most-important-results-and-papers-in-complexity-theory-that-every)  
> **username_2**: There is a book along similar lines: **Ideas That Created the Future: Classic Papers of Computer Science** by Harry R Lewis.  

---

## 70 answers

### Answer by username_6 on 2010-09-12. Score: 177

["A mathematical theory of communication"](https://web.archive.org/web/20150328061529/http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf) by Claude Shannon, classics of information theory. Very readable.

([Mirror](http://www.mast.queensu.ca/%7Emath474/shannon1948.pdf))

> **Comments:**
> **username_7**: The safest general characterization of the Internet is that it consists of a series of footnotes to this paper.  
> **username_8**: The Bell Labs link is broken.  
> **username_9**: https://en.m.wikipedia.org/wiki/A_Mathematical_Theory_of_Communication#External_links  
> **username_10**: Just a note for readers of this paper that Shannon assumed that [differential entropy](https://en.wikipedia.org/wiki/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.  

---

### Answer by username_11 on 2010-09-12. Score: 158

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](http://dx.doi.org/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](http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#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).

> **Comments:**
> **username_14**: It is also very accessible and readable...  
> **username_15**: and with it The Annotated Turing by Charles Petzold [Highly Recommended]  
> **username_12**: Here is [a friendlier link to the paper](http://classes.soe.ucsc.edu/cmps210/Winter11/Papers/turing-1936.pdf).  
> **username_13**: @james The problem with friendly links is that they are more likely to break.  

---

### Answer by username_16 on 2010-09-12. Score: 132

Ken Thompson's "[Reflections on Trusting Trust](http://www.ece.cmu.edu/~ganger/712.fall02/papers/p761-thompson.pdf)". Short, sweet, and mind-blowing.

> **Comments:**
> **username_22**: 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.  
> **username_23**: just read it -- awesome indeed!  
> **username_17**: "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)  
> **username_18**: I would think this paper would be pretty difficult to digest without at least knowing what a compiler is.  
> **username_19**: In the paper, I think figures 2.1 and 2.2 are swapped.  
> **username_20**: 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.  
> **username_21**: I agree with username_20. 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.  
> **username_8**: 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.  

---

### Answer by username_24 on 2010-10-13. Score: 94

Keshav's [How to Read a Paper](http://doi.acm.org/10.1145/1273445.1273458). You can also download the paper from [here](http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/07/paper-reading.pdf).

> **Comments:**
> **username_30**: Nice read indeed.  
> **username_25**: I always think that CS research papers are written in some foreign language.  
> **username_26**: Very good! It is worth to be put on tagline banner on the site to be sure no one student miss that.  
> **username_27**: The second link is currently broken  
> **username_24**: @ChristopherManning thanks for pointing that out. I've updated the link.  
> **username_19**: 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.  
> **username_28**: Though I've stumbled across this more than a year later, it's been invaluable to me. I would recommend this paper to everyone!  
> **username_29**: I like this ones the best, three-pass approach really helped me comprehending first few papers easily.  

---

### Answer by username_31 on 2010-09-12. Score: 72

[Paths, Trees and Flowers](https://doi.org/10.4153/CJM-1965-045-4) 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.


---

### Answer by username_32 on 2010-09-12. Score: 63

[Reducibility Among Combinatorial Problems](http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf) 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.

> **Comments:**
> **username_34**: I like this paper, but some of the reductions are really sketchy and hard to follow.  See any complexity text for more details.  
> **username_33**: @Andras Salamon I agree 100%.  

---

### Answer by username_0 on 2010-09-12. Score: 54

Hartmanis and Stearns, ["On the computational complexity of algorithms"](http://www.ams.org/mathscinet-getitem?mr=0170805), 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.

> **Comments:**
> **username_35**: Working link. https://pdfs.semanticscholar.org/1ce8/9af300d9a7c64d3ee06175b24ca97763f9f2.pdf  

---

### Answer by username_4 on 2010-09-12. Score: 52

[Quantum Mechanical Computers](https://link.springer.com/article/10.1007%2FBF01886518) [(PDF)](http://www.quantum-dynamic.eu/doc/feynman85_qmc_optics_letters.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.

> **Comments:**
> **username_37**: 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?  
> **username_4**: That's the one. I added a new link and a link to it's page on the publisher's website.  
> **username_36**: 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?  

---

### Answer by username_38 on 2010-09-17. Score: 50

[Expander graphs and their applications, S. Hoory, N. Linial, and A. Wigderson](http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf) 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](https://resources.mpi-inf.mpg.de/departments/d1/teaching/ws10/EG/Reingold_SL.pdf) (by Reingold, STOC, 2005)
* [the alternative proof of the PCP Theorem](https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-046/) (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](https://hungary.pure.elsevier.com/en/publications/on-log-n-sorting-network) (by Ajtai, Komlós and Szemerédi, STOC, 1983)
* [Linear-time encodable and decodable error-correcting codes](http://www.cs.yale.edu/homes/spielman/Research/ITsuperc.pdf) (by Spielman, STOC, 1995)

> **Comments:**
> **username_39**: You should watch for combinatorial or support preconditioners. Expander graphs are even used in numerical analysis today.  
> **username_40**: @username_39 Can you give an example?  

---

### Answer by username_41 on 2010-09-12. Score: 44

[Hundreds of Impossibility Results for Distributed Computing](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.7.9472) 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.

> **Comments:**
> **username_34**: Publisher's version: https://doi.org/10.1007/s00446-003-0091-y  
> **username_42**: can you please add the year to the answer  

---

### Answer by username_23 on 2010-09-12. Score: 44

Les Valiant's [Theory of the Leusername_50le](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.94.6289&rep=rep1&type=pdf) (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.


---

### Answer by username_15 on 2010-09-15. Score: 43

[Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer - username_78 W. Shor](http://arxiv.org/abs/quant-ph/9508027v2) 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](http://en.wikipedia.org/wiki/Integer_factorization).


---

### Answer by username_43 on 2010-09-21. Score: 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](https://dspace.mit.edu/handle/1721.1/5794), [Lambda: The Ultimate Imperative](https://dspace.mit.edu/handle/1721.1/5790), [Lambda: The Ultimate Declarative](https://dspace.mit.edu/handle/1721.1/6091).

> **Comments:**
> **username_44**: I'd upvote you once for every Lambda paper if I could.  

---

### Answer by username_45 on 2010-09-24. Score: 42

John McCarthy's [Recursive functions of symbolic expressions and their computation by machine, part I.](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.9776)

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.


---

### Answer by username_46 on 2010-09-20. Score: 37

[Call-by-value is dual to call-by-name](http://homepages.inf.ed.ac.uk/wadler/papers/dual/dual.pdf) by Philip Wadler is a good read.

> **Comments:**
> **username_47**: Anything by Phil Wadler is a good read.  

---

### Answer by username_48 on 2010-09-12. Score: 37

C.A.R. Hoare, [An Axiomatic Basis for Computer Programming](https://www.google.com/search?q=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.


---

### Answer by username_49 on 2010-09-12. Score: 37

[The complexity of theorem-proving procedures](http://4mhz.de/cook.html) 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.

> **Comments:**
> **username_34**: 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.  

---

### Answer by username_50 on 2010-09-12. Score: 34

Alon, Matias and Szegedy, [The space complexity of approximating the frequency moments](http://dx.doi.org/10.1006/jcss.1997.1545), 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.

> **Comments:**
> **username_51**: dang. I was going to add this one :)  

---

### Answer by username_52 on 2010-09-12. Score: 30

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.](http://linkinghub.elsevier.com/retrieve/pii/S002200007080006X)


---

### Answer by username_53 on 2010-09-12. Score: 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.](http://www.cs.umass.edu/~immerman/pub/space.ps)

> **Comments:**
> **username_23**: To be fair, Szelepcsényi's paper, "The method of forced enumeration for nondeterministic automata," is just as nice.  

---

### Answer by username_63 on 2011-03-19. Score: 28

Russell Impagliazzo's [A Personal View of Average-Case Complexity](http://cseweb.ucsd.edu/~russell/average.ps). 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.


---

### Answer by username_64 on 2010-09-12. Score: 26

[Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming](http://doi.acm.org/10.1145/227683.227684) by Goemans and Williamson.

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

> **Comments:**
> **username_65**: pdf: http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf  

---

### Answer by username_30 on 2011-03-18. Score: 25

[How to Write a Proof](http://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-how-to-write.pdf), by Leslie Lamport.

> **Comments:**
> **username_66**: 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.  
> **username_30**: 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/..." ;-)  

---

### Answer by username_31 on 2010-09-12. Score: 24

[Extractors and Pseudorandom Generators](http://www.cs.berkeley.edu/%7Eluca/pubs/extractor-full.pdf) 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.


---

### Answer by username_31 on 2011-01-19. Score: 22

[The influence of variables on boolean functions, J. Kahn, G. Kalai and N. Linial](http://www.ma.huji.ac.il/~kalai/kkl.ps)

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

I find this paper very readable.

> **Comments:**
> **username_51**: can you add a link  ?  

---

### Answer by username_14 on 2010-09-17. Score: 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.

> **Comments:**
> **username_34**: 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.  
> **username_14**: Fair enough, but IMHO for most of the papers suggested books are a better place to read this stuff.  
> **username_5**: 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.  
> **username_56**: 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  
> **username_14**: Its great when this happens. I just claim that it is somewhat rare.  
> **username_54**: You say "All of them", but don't you then argue for "None of them"?  
> **username_48**: @username_54, I think that's why Sarah is mentioned. :)  
> **username_55**: 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  
> **username_55**: I mean the paper presented the material almost identically to the way it was introduced in the course and terminology was very close.  

---

### Answer by username_57 on 2010-09-13. Score: 18

* N. Chomsky. Three models for the description of language. IEEE Transactions on Information Theory 3. 1956. [doi: 10.1109/TIT.1956.1056813](http://dx.doi.org/10.1109/TIT.1956.1056813)

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

> **Comments:**
> **username_34**: 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.  

---

### Answer by username_58 on 2010-10-15. Score: 18

Kurt Gödel's [On formally undecidable propositions of Principia Mathematica and related systems](http://www.csee.wvu.edu/~xinl/library/papers/math/Godel.pdf).

> **Comments:**
> **username_59**: This is important, though I do think that later treatments on the subject are easier to read than the original.  

---

### Answer by username_60 on 2011-11-21. Score: 18

[You and Your Research](http://www.cs.virginia.edu/~robins/YouAndYourResearch.html) 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](http://www.youtube.com/watch?v=a1zDuOPkMSw) is the later version of this talk.


---

### Answer by username_61 on 2011-05-28. Score: 18

["Can Programming Be Liberated from the von Neumann Style?](https://dl.acm.org/doi/10.1145/359576.359579) 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.


---

### Answer by username_62 on 2011-09-02. Score: 16

[Natural Proofs](http://www.sciencedirect.com/science/article/pii/S002200009791494X) 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.


---

### Answer by username_75 on 2013-09-10. Score: 15

> [PRIMES in
> P](http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf)
> 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.


---

### Answer by username_58 on 2010-10-15. Score: 15

Alan Turing's [Computing Machinery and Intelligence](http://www.cs.umbc.edu/courses/471/papers/turing.pdf).


---

### Answer by username_76 on 2011-03-22. Score: 15

R. Moser and G. Tardos: [A constructive proof of the general Lovasz Local Lemma](http://arxiv.org/abs/0903.0544)

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!


---

### Answer by username_67 on 2010-11-19. Score: 14

There are two essays (but not paper) which are very handy after reading all the suggested papers:  
1.[How to write papers](http://www.wisdom.weizmann.ac.il/~oded/PS/re-writing.pdf)  
2.[How not to write papers](http://www.cs.iastate.edu/~honavar/write-not.pdf)  
Both by Oded Goldreich


---

### Answer by username_68 on 2011-01-05. Score: 14

Ronald L. Rivest, Adi Shamir, Leonard M. Adleman: [A Method for Obtaining Digital Signatures and Public-Key Cryptosystems](https://people.csail.mit.edu/rivest/Rsapaper.pdf). Commun. ACM (CACM) 21(2):120-126 (1978)

If your are interested in Crypto/Security, this is a very nice reading.


---

### Answer by username_69 on 2011-04-26. Score: 14

[The mechanical evaluation of expressions](https://academic.oup.com/comjnl/article/6/4/308/375725) by username_78 J. Landin

Introduced:

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


---

### Answer by username_66 on 2010-09-12. Score: 14

* Ethan Bernstein and Umesh Vazirani. [*Quantum Complexity Theory*](http://www.cs.berkeley.edu/~vazirani/pubs/bv.ps). SIAM J. Comput. Vol. 26 No. 5, pp. 1411-1473, October 1997. [doi: 10.1137/S0097539796300921](http://dx.doi.org/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.


---

### Answer by username_15 on 2010-09-15. Score: 13

[A fast quantum mechanical algorithm for database search
- Lov K. Grover](http://arxiv.org/abs/quant-ph/9605043)


---

### Answer by username_70 on 2010-09-12. Score: 13

[Factoring Polynomials with Rational Coefficients](http://www.math.elte.hu/~lovasz/scans/lll.pdf) 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](http://cs.nyu.edu/yap/book/berlin/), [chap. 9](http://cs.nyu.edu/~yap/book/alge/ftpSite/l9.ps.gz), for a good reference), the original paper has a good description of the lattice reduction algorithm.


---

### Answer by username_71 on 2010-09-20. Score: 13

[Emil Post's "Recursively enumerable sets of positive integers and their decision problems."](http://dx.doi.org/10.1090/S0002-9904-1944-08111-1) 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.

> **Comments:**
> **username_34**: Definitely an evergreen classic.  

---

### Answer by username_34 on 2010-09-16. Score: 12

* E. Mark Gold, *Language Identification in the Limit*, Information and Control **10**, 447–474, 1967. [doi: 10.1016/S0019-9958(67)91165-5](http://dx.doi.org/10.1016/S0019-9958%2867%2991165-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.


---

### Answer by username_72 on 2010-10-14. Score: 11

[Time bounds for Selection](http://people.csail.mit.edu/rivest/BlumFloydPrattRivestTarjan-TimeBoundsForSelection.pdf) by Blum, Floyd, Pratt, Rivest and Tarjan.

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


---

### Answer by username_73 on 2012-07-10. Score: 11

[PCP Theorem by Gap Amplification](http://www.lri.fr/perso/~mdr/pcp-newproof.pdf) 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".


---

### Answer by username_74 on 2010-09-18. Score: 11

Another very nice paper in proof complexity is

[Ben-Sasson, Wigderson - Short proofs are narrow, Resolution made simple](http://www.cs.technion.ac.il/~eli/papers/width-journal03.ps)

Notice that even this paper gives a new technique which simplifies previous results.


---

### Answer by username_66 on 2011-04-25. Score: 10

This is a classic!

[Probabilistic Computations: Toward a Unified Measure of Complexity](http://dx.doi.org/10.1109/SFCS.1977.24). 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.


---

### Answer by username_77 on 2011-11-21. Score: 10

[Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time](http://arxiv.org/abs/cs/0111050) by username_60 Spielman and Shang-Hua Teng for introducing smoothed analysis and showing it's success in explaining the behavior of the simplex algorithm.


---

### Answer by username_78 on 2011-11-22. Score: 9

The paper [Impossibility of distributed consensus with one faulty process](http://dx.doi.org/10.1145/3149.214121) 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.


---

### Answer by username_74 on 2010-09-18. Score: 8

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](http://www.cs.toronto.edu/~toni/Papers/beame-pitassi.ps)

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.


---

### Answer by username_68 on 2011-01-05. Score: 8

Shafi Goldwasser, Silvio Micali: [Probabilistic Encryption](https://groups.csail.mit.edu/cis/pubs/shafi/1984-jcss.pdf). J. Comput. Syst. Sci. 28(2): 270-299 (1984)

This paper is the theoretical foundations of modern Cryptography.


---

### Answer by username_15 on 2010-09-15. Score: 7

[The theory of **interstellar trade** by Paul Krugman](http://www.princeton.edu/~pkrugman/interstellar.pdf)

> **Comments:**
> **username_34**: How does interstellar arbitrage (while undoubtedly interesting) relate to theoretical computer science?  
> **username_15**: 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.*  
> **username_82**: The critique in the paper applies to TCS as well  

---

### Answer by username_79 on 2010-09-12. Score: 6

Bill Gasarch's [P v NP poll](http://www.cs.umd.edu/~gasarch/papers/poll.pdf)

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.


---

### Answer by username_80 on 2011-07-06. Score: 6

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](http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz) 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](http://en.wikipedia.org/wiki/Exact_cover) 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.


---

### Answer by username_81 on 2011-12-09. Score: 6

Guy E. Blelloch: [Programming Parallel Algorithms](http://dx.doi.org/10.1145/227234.227246)

Very clear introduction to parallel algorithms.


---

### Answer by username_83 on 2011-05-25. Score: 5

Allen Newell and Herbert A. Simon’s [“Computer Science as Empirical Inquiry: Symbols and Search”](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.104.2482&rep=rep1&type=pdf) (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!


---

### Answer by username_84 on 2011-11-25. Score: 5

Some great suggestions are included in the reading list of the [Reading the Classics](http://www.cs.berkeley.edu/~christos/classics/cs298.html) 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](http://www.cs.berkeley.edu/~christos/classics/euler.pdf).


---

### Answer by username_88 on 2011-11-21. Score: 5

[A Simple Proof that Toffoli and Hadamard are Quantum Universal](http://arxiv.org/abs/quant-ph/0301040), 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.


---

### Answer by username_15 on 2010-09-15. Score: 4

[**Quantum Walks On Graphs**
Authors: Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh Vazirani](http://arxiv.org/abs/quant-ph/0012090)


---

### Answer by username_18 on 2011-09-02. Score: 4

The RSA cryptosystem was described in a [short elegant paper](http://people.csail.mit.edu/rivest/Rsapaper.pdf); it's very readable and created quite a stir even among non-scientists.

> **Comments:**
> **username_34**: This is the Rivest/Shamir/Adleman paper as suggested by username_68, but this version has been typeset in TeX.  

---

### Answer by username_85 on 2015-10-19. Score: 4

[On Universal Learning Algorithms](http://www.sciencedirect.com/science/article/pii/S0020019097001178), Oded Goldreich and Dana Ron (1997), Information Processing Letters, Volume 63, Issue 3, pp. 131-136. (see also the [updated version](http://www.wisdom.weizmann.ac.il/~oded/p_ul.html))

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 leusername_50le, 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.


---

### Answer by username_86 on 2011-05-24. Score: 4

Fischer Black and Myron Scholes, The Pricing of username_77ions and Corporate Liabilities
[https://web.archive.org/web/20231114103316/https://www.cs.princeton.edu/courses/archive/fall09/cos323/papers/black\_scholes73.pdf](http://www.cs.princeton.edu/courses/archive/fall09/cos323/papers/black_scholes73.pdf%22The%20Pricing%20of%20username_77ions%20and%20Corporate%20Liabilities%22)

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.

> **Comments:**
> **username_87**: http://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Encryption/Probabilistic_Encryption.pdf  

---

### Answer by username_89 on 2011-11-21. Score: 3

Although not published in a scientific journal, Vannevar Bush's [As We May Think](http://www.theatlantic.com/magazine/archive/1945/07/as-we-may-think/3881/) 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](http://en.wikipedia.org/wiki/As_We_May_Think), for god's sake.


---

### Answer by username_90 on 2019-05-08. Score: 3

My favorite piece of scientific writing is Charles Bennett's 1979 [On Random and Hard-to-Describe Numbers](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.3492) 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.


---

### Answer by username_91 on 2021-04-13. Score: 2

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.


---

### Answer by username_92 on 2011-07-06. Score: 2

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](https://www.jstor.org/stable/2345762?seq=1#metadata_info_tab_contents)", 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.


---

### Answer by username_93 on 2018-10-08. Score: 2

[Time/space tradeoffs for reversible computation (1989)](https://web.archive.org/web/20220505020435/https://mathweb.ucsd.edu/%7Esbuss/CourseWeb/Math268_2013W/Bennett_Tradeoffs.pdf) 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.


---

### Answer by username_94 on 2012-06-27. Score: 1

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](http://dx.doi.org/10.1038/323533a0)

The paper that introduced backpropagation and resuscitated neural networks.


---

### Answer by username_95 on 2021-04-06. Score: 1

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](http://www.cs.tau.ac.il/%7Enogaa/PDFS/expander7.pdf) 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.


---

### Answer by username_96 on 2011-05-25. Score: -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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.432)", 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.

> **Comments:**
> **username_97**: 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?  

---

### Answer by username_98 on 2013-09-09. Score: -1

The paper [Multidimensional Divide-and-conquer](http://akira.ruc.dk/~keld/teaching/algoritmedesign_f04/Artikler/12/Bentley80.pdf) 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.


---

