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

51–60 of 114 posts

Re: Most Influential Papers in Computer Science History

#51

Post by mrkeen »

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.

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.

Re: Most Influential Papers in Computer Science History

#52

Post by mrkeen »

honungsburk wrote: post #42
Tainnor wrote: post #29

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

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.

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?

Re: Most Influential Papers in Computer Science History

#53

Post by kriro »

Solid list. Two that influenced me personally were:

Wolpert, D. H., & Macready, W. G. (1997). No free lunch theorems for optimization. IEEE transactions on evolutionary computation, 1(1), 67-82.

And the corresponding search paper. Got me started in search and optimization (and Prolog).

Licklider, J. C. (1960). Man-computer symbiosis. IRE transactions on human factors in electronics, (1), 4-11.

More of a philosophical outlook but the thought of man-computer symbiosis instead of "computer solves it" has stuck with me (and is quite relevant in this day and age).

Re: Most Influential Papers in Computer Science History

#55

Post by mrkeen »

sho_hn wrote: post #11
65 wrote: post #7

Surprised the Bitcoin paper isn't on here.

It doesn't really add anything to computer science, but then again the Sergey-Brin paper probably doesn't match that rigidity either.

I'm not so sure. In my (under-read) mental model, blockchain takes you from fail-stop fault-tolerance (a la Paxos) to Byzantine fault-tolerance, i.e. how do you compute in a massively distributed system when no node has any reason to trust any other node.

Re: Most Influential Papers in Computer Science History

#56

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

Re: Most Influential Papers in Computer Science History

#57

Post by tromp »

honungsburk wrote: post #42
Tainnor wrote: post #29

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

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.

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

Post reply on HN