Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Most Influential Papers in Computer Science History

terriblesoftware.org

Post reply on HN
Print view View original

71–80 of 114 posts

Re: Most Influential Papers in Computer Science History

#71

Post by bjourne »

freetime2 wrote: post #40
serviceberry wrote: post #24

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…

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…

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.

Re: Most Influential Papers in Computer Science History

#72

Post by The_suffocated »

generationP wrote: post #34
cs702 wrote: post #2

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…

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

Re: Most Influential Papers in Computer Science History

#74

Post by zipy124 »

baq wrote: post #38

The Part-Time Parliament by Leslie Lamport, written in such a style it is its own complementary material. (This is the Paxos paper.)

I think any list like this has to include: "Time, clocks, and the ordering of events in a distributed system" By Lamport also, in almost any networked system having strict ordering is fantastically useful. And of course how could we also forget "The Byzantine generals problem".

Re: Most Influential Papers in Computer Science History

#75

Post by 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...

Re: Most Influential Papers in Computer Science History

#77

Post by wslh »

Tainnor wrote: post #31
gorby91 wrote: post #23

Earlier quoted context omitted.

Is there a particular paper to point to?

We have Shannon's "Communication Theory of Secrecy Systems" as arguably the beginning of modern cryptography and then Diffie & Hellman's "New Directions in Cryptography" which first introduced public-key cryptography.

And FHE, MPC, ZK, among breakthroughs. Easy to check on the Wikipedia Turing Awards page [1]. Use Gödel prize as a "helper" [2].

[1] https://en.wikipedia.org/wiki/Turing_Award

[2] https://en.wikipedia.org/wiki/G%C3%B6del_Prize

Re: Most Influential Papers in Computer Science History

#78

Post by udev4096 »

65 wrote: post #7

Surprised the Bitcoin paper isn't on here.

BTC is just combining all the past research into an application, which has it's own place but sadly not here. You might wanna read this [0] for all the past ideas that satoshi took

[0] - https://queue.acm.org/detail.cfm?id=3136559

Re: Most Influential Papers in Computer Science History

#79

Post by bovermyer »

freetime2 wrote: post #40
serviceberry wrote: post #24

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…

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…

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.

Post reply on HN