It would be interesting to see the opposite of this; which papers are really interesting and look useful, but did not end up having a significant impact?
Plan9
Most Influential Papers in Computer Science History
91–100 of 114 posts
Re: Most Influential Papers in Computer Science History
#92Earlier quoted context omitted.
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 n…
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
Hoare's paper is in the list, no?
Re: Most Influential Papers in Computer Science History
#93Communicating 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 exper…
Seems like you need to have a Harvard account to see the lectures(?)
Re: Most Influential Papers in Computer Science History
#94Earlier quoted context omitted.
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.
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 fixe…
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...
Re: Most Influential Papers in Computer Science History
#95Earlier quoted context omitted.
Does anyone actually use Paxos in real life? And let me ask the same question for all other academic distributed algorithms right away. I recall seeing a study some 10 years ago checking the major cloud providers for Byzantine fault tolerance and finding none of them to exhibit the qualities that the known algorithms would guarantee; apparently they would just rely on timing and hoping things don't get too twisted.
Yes, if you’re using any sort of multi master db, you’re using a variant of paxos, raft or something which you shouldn’t really trust until aphyr blasts it into the low earth orbit. The paper itself is very approachable and worth spending an hour or so on.
I remember trying to read the paper and giving up somewhere early in the proof. I certainly don't think it gives a great intuition why the algorithm holds, so "approachability" is a matter of definition (does it tell a fun story? sure yeah).
Re: Most Influential Papers in Computer Science History
#96Earlier quoted context omitted.
Does anyone actually use Paxos in real life? And let me ask the same question for all other academic distributed algorithms right away. I recall seeing a study some 10 years ago checking the major cloud providers for Byzantine fault tolerance and finding none of them to exhibit the qualities that the known algorithms would guarantee; apparently they would just rely on timing and hoping things don't get too twisted.
> Does anyone actually use Paxos in real life? Yes, it's very widely used at Google through Chubby, which underpins many core pieces of infrastructure, including name resolution. (It used to be common practice to depend more directly on Chubby for synchronization of state via shared global files, but that fell out of favor about 6 years ago due to reliability risks associated with just blasting out changes globally w…
Ah, so Raft is what everyone uses, and Paxos is used by the very big providers nowadays. Good to know!
I can't find the study any more, though I'm pretty sure I saw it on HN...
Re: Most Influential Papers in Computer Science History
#97Not a single woman? No Barbara Liskov - Programming with abstract data types? No Grace Hopper - The education of a computer? No Frances Allen - Program optimization?
Did you just assume their gender?
Re: Most Influential Papers in Computer Science History
#98I thought we were going to get through without any LLM bullshit, but no, they snuck it in at the end.
Come on, we now have systems that can believably answer arbitrary questions in human language. This is literally what I dreamed of when I got into computing like 25 years ago, and would be considered science fiction only 5 years ago. As a side effect, entire tasks as important as machine translation and summarization have pretty much been solved for major languages.
Regardless of whether you buy the full hype or you think they're just stochastic parrots, I think it more than qualifies to make the second list (and probably the first, but I get that there's no perspective to be so sure about that).
The paper itself (as a paper, i.e. an explanation of the underlying results) is quite bad, by the way. It's better to learn about Transformers from one of the many good blog posts. But that doesn't detract from its influence.
Re: Most Influential Papers in Computer Science History
#99I wonder how someone could make such a list and completely ignore cryptography. No, it is not enough to mention NP-completeness.
diffie-hellman should be on that list... maybe instead of he pagerank one imho.
Re: Most Influential Papers in Computer Science History
#100[deleted]