Most Influential Papers in Computer Science History
113 comments
·January 23, 2025sovietswag
timmg
Seems like you need to have a Harvard account to see the lectures(?)
serviceberry
I actually found this to be an odd mix. Are we selecting papers that had an influence on computer science (as in, the theory of computation), or that had an impact on technology? Or are we just using CS as a catch-all for "all things computer"?
The Turing paper is foundational for CS, but without it, would the technology have evolved differently? Probably not. Most software engineers have not read it. Conversely, the IP standard is a technological cornerstone, but there's hardly any science in it. It's just a specification of a fairly simple protocol that you need to know when doing almost anything network-adjacent.
freetime2
Something doesn't feel quite right to me seeing the PageRank paper in a short list alongside Turing and Shannon's foundational work on computability and information theory. “On Computable Numbers, with an Application to the Entscheidungsproblem” is almost 90 years old at this point and just as true and relevant now as it was then. Is PageRank even as relevant today as it was in 1998, let alone another 50 years from now?
fooker
We can’t estimate what will be relevant 50 years from now.
If quantum or biological computing find some success, none of these are going to be relevant.
That said, pagerank is important to understand the modern tech world. Search is something we take for granted, and it’s great there’s a deeply mathematical (and somewhat counterintuitive) theory behind it.
karmakurtisaani
The foundations of computation won't change with quantum/biological computers. Turing machines stay as relevant as ever.
froh
indeed this was itching me, too.
I wonder how pagerank was influential to CS as a field?
even mapreduce is more a rally clever technique than a boundary pushing or boundary identifying extension of the field. unlike, say, CSP --- which is missing in the list.
still unlike the conciseness and structure of the list. it could evolve into a nice book :-D
fooker
If you haven’t read the pagerank paper, you should. It’s not an obvious thing.
Agreed about map reduce though.
tucnak
Hoare's paper is in the list, no?
bovermyer
An important part of historiography is considering documents and artifacts in the context of their time.
We don't use cuneiform these days, but back in its day, it was as close to a standard writing system as it was possible to get.
tuyguntn
Will it be directly influential in 50 years from now on? Maybe no.
But, indirectly looking, it influenced establishment of Google, which influenced many thousands of innovations in this field.
So yes, PageRank is hugely influential in my opinion.
bjourne
The big insight of the PageRank paper is that you can use MC integration to approximate PR, not PR itself. Hence making the problem much easier to distribute.
cs702
Great list of papers.
I've read five of of the seven papers on the list. The two I haven't read are Cerf and Kahn's, and Berner-Lee's.
Turing's paper on computability was particularly hard to follow, for me, because he used these gothic-font upper-chase characters to name all sorts of objects, and all those characters looked kinda the same to me! I had to use auxiliary materials to be able to make my way through the paper. Today, I would recommend reading it with Charles Petzold's easy-to-follow book on the paper: https://www.amazon.com/Annotated-Turing-Through-Historic-Com...
Cook's paper on NP-completeness was also hard to follow (again, for me). As with Turing's paper, I had to use auxiliary materials to make my way. Today, I would recommend reading instead an introductory book on computational complexity that works through Cook's proof.
Shannon's paper is a work of art, clearly articulated and beautifully written. It's just not casual reading, to put it mildly.
Brin and Page's paper, and Codd's paper, are not hard to follow, at least as I remember them, but understanding Brin and Page's work requires some knowledge of Linear Algebra.
Thank you for sharing this on HN.
generationP
Where does the Brin-and-Page paper require linear algebra? It mentions "eigenvector" once, in a tangential remark. The "simple iterative algorithm" is how you find the fixed point of any contraction mapping, linear or not. Knowing that it is also an eigenvector is just a distraction -- you aren't going to use Gaussian elimination, not if you know what is good for you.
The_suffocated
It doesn't require linear algebra to understand the paper or how the algorithm works, but it does require linear algebra to understand why the algorithm works. In general, since the induced 1-norm of a stochastic matrix S is exactly equal to 1 but not smaller than 1, the mapping x↦Sx is NOT a contraction. Neither convergence of the power method nor uniqueness of fixed point are guaranteed. (If there are multiple fixed points, there are multiple inconsistent rankings.)
In the paper, the significance of the so-called "damping factor" is not clear. However, with linear algebra, we know that the damping factor makes the stochastic matrix positive rather than merely nonnegative. Hence the Perron eigenvalue is "simple" (i.e. of multiplicity one), the Perron vector is unique and the power iteration must converge to it.
generationP
That's easier explained using fixed-point theory: The damping factor makes the mapping x↦Sx into an actual contraction (on the space of probability distributions). Not to mention that it has a simple common-sense justification (you don't want to get stuck in a subnetwork that only links to itself, or drown out a subnetwork that has more outlinks than inlinks).
There is probably some gain from understanding the algorithm specifically as a Markov chain iteration (if nothing else, it provides a great example for Markov chain iteration), but I think it's perfectly possible -- and easier -- to understand it as a fixed-point iteration on a compact space. And I am someone who does algebra for a living and normally explains everything algebraically if ever possible...
mrkeen
Yes, but the paper blathers on and on in prose about history and related work and goals and future work. It might only mention eigenvector once in a tangential remark, but that remark is like 80% of the algorithm content of the paper.
yuppiemephisto
If you can get .tex source files, ask GPT to rename the variables to something nicer, including more than one letter long names. Helps.
cs702
LaTex didn't exist when Turing wrote that paper in the 1930's.
I don't known if anyone has gone through the trouble to re-typeset the original paper in LaTex.
vitus
Oh man, if you think Shannon's A Mathematical Theory of Communication is his most foundational contribution to computer science, you haven't seen his master's thesis from a decade prior.
https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_a...
He outlined how you could use switching elements in circuits (read: transistors) to define boolean logic.
(That's not to downplay the importance of, well, establishing the foundations of the entire field of information theory.)
Tainnor
> He sketches out a hypothetical “Turing Machine,” proving that, if something is computable at all, a machine (in principle) can handle it.
That's not what Turing proved. Instead, what he proved in his paper was that there are some problems which aren't solvable by Turing Machines (and therefore presumably by any machine). That's the Entscheidungsproblem (decision problem) referenced in the title.
What TFA references is the so-called Church-Turing-Thesis, which is exactly that, a thesis. It can't really be proven although we have very strong reason to believe it given that in almost 100 years nobody has found a system of computation more powerful than Turing Machines.
aorloff
And in 100 years we have gone completely the opposite direction in terms of where we think artificial intelligence lies. Rather than constructing a machine with all the known truths, modern searching for artificial intelligence using machines is mostly sifting through human commentary to create an organized feuilleton machine versus Leibniz's axiomatic approach
psychoslave
No, Turing had precisely that approach of feeding the machine with learning material in mind[1], but you have to build a machine apt to consume generic knowledge body before you throw at it anything.
https://philsci-archive.pitt.edu/9085/1/SterrettBringingUpTu...
aorloff
There have also been attempts to canonicalize knowledge on the web (semantic web) and lots of things inside of computers are in fact deterministic.
But that is not the direction that AI seems to be taking, it is "smart" because it does a good job of parroting humans that sound "smart", not because it "knows" truths.
honungsburk
I beleive you are wrong that "nobody has found a system of computation more powerful than Turing Machines". A turing machine can not perform indeterminacy, however, the actor model can.
fooker
This is a misconception.
The actor model is a way to describe that a program exists, not if it’s possible to ‘compute’ that program.
You’re right that it can describe more things than a Turing machine, but doesn’t provide a constructive way to compute them.
tromp
Non-deterministic Turing machines [1] are the standard way to define Non-deterministic complexity classes like NP or NEXP, so there are definitely Turing machines with indeterminacy.
[1] https://en.wikipedia.org/wiki/Nondeterministic_Turing_machin...
mrkeen
I read that sentiment here a few years ago but couldn't get anything more out of it than actors can race, but a turing machine is determistic. I could very well have it wrong.
If you were computing with actors, and you also had a sufficiently-detailed spec about the actor model, is there some particular algorithm you could not compute by just executing a TLA+ spec of your actor algorithm using Turing-ish software?
gundegy_man
Nice work!
I was actually doing something similar on my own, so I might recommend some papers
- RSA: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (1978)
- PageRank: The PageRank Citation Ranking: Bringing Order to the Web (1999)
- MapReduce: MapReduce: simplified data processing on large clusters (2008)
- Bitcoin: Bitcoin: A Peer-to-Peer Electronic Cash System (2008)
- BackProp: Learning representations by back-propagating errors (1986)
- Hoare Logic: An Axiomatic Basis for Computer Programming (1969)
gundegy_man
Oh, never mind about the PageRank paper, it was already in the list
udev4096
Where's the infamous "Evolution of Unix time-sharing systems" by Dennis Ritchie?
berbec
How about "SEQUEL: A Structured English Query Language" Don Chamberlin and Raymond Boyce?
https://web.archive.org/web/20070926212100/http://www.almade...
kleiba
Since everyone likes chiming in with their own additions to the list, here's mine:
While Cook was the first to introduce NP-completeness, Karp's paper presenting 21 problems that could be reduced polynomially to 3SAT was also an enormeous cornerstone that helped kick off a more general interest in Cook's theory.
https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_proble...
twothreeone
Diffie, Whitfield; Hellman, Martin E. (November 1976). "New Directions in Cryptography" ???
mwn
It's not papers but I would give special mention to Why Software Is Eating the World by Marc Andreessen and Amazon's original 1997 letter to shareholders.
"Companies in every industry need to assume that a software revolution is coming. This includes even industries that are software-based today."
https://a16z.com/why-software-is-eating-the-world/
"But this is Day 1 for the Internet and, if we execute well, for Amazon.com."
https://www.aboutamazon.com/news/company-news/amazons-origin...
0x7f1
Just wrote a blog about the explosion of papers titled after Attention Is All You Need [1]. Also figured out the name probably didn’t originate from one of the authors.
[1]https://open.substack.com/pub/0x7f1/p/is-all-you-need-is-all...
AdieuToLogic
Here's another foundational paper:
Hewitt, Carl; Bishop, Peter; Steiger, Richard (1973). "A Universal Modular Actor Formalism for Artificial Intelligence". IJCAI.
Communicating Sequential Processes (Hoare), The Next 700 Programming Languages (Landin), As We May Think (Bush), Can Programming Be Liberated from the von Neumann Style (Backus)
And this seems to be a cool course: https://canvas.harvard.edu/courses/34992/assignments/syllabu... > This course examines papers every computer scientist should have read, from the 1930s to the present. It is meant to be a synthesizing experience for advanced students in computer science: a way for them to see the field as a whole, not through a survey, but by reliving the experience of its creation. The idea is to create a unified view of the field of computer science, for students who already know something about it, by replaying its entire evolution at an accelerated frame rate.