Ask HN: What is your favorite CS paper? • Hacker News Board

Re: Ask HN: What is your favorite CS paper?

#201

Post by Steeeve » Thu, Aug 24, 2017, 11:19 PM UTC

KirinDave wrote: post #126

I've been trying to get it frontpaged because, despite it's length, it's perhaps one of the most startling papers of this decade. Sadly, it seems like the HN voting gestalt hasn't decided to upvote a paper that's the CS equivalent of breaking the speed of light: "Generic Top-down Discrimination for Sorting and Partitioning in Linear Time" -> http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl... (if you're d…

I have mixed feelings about this one. It certainly has inspired some interesting discussion. The paper itself is obtuse and difficult to absorb.

The methodology isn't _really_ new, but it isn't used frequently. While they showed it as competitive to commonly used sorting algorithms, situationally it can really shine and show significant performance benefits. I'm surprised they didn't show this in one of the graphs (or I missed it in my brief speed-thru).

I don't really see a future for this in standard libraries. I can totally see this methodology being used in the wild in a variety of systems where time = money or entities are looking for a small proprietary distinguishing edge.

Re: Ask HN: What is your favorite CS paper?

#202

Post by phamilton » Thu, Aug 24, 2017, 11:20 PM UTC

The Dynamo Paper. http://www.allthingsdistributed.com/files/amazon-dynamo-sosp...

One of the best practical "How can this improve our business?" technical papers, and an excellent introduction to reading papers.

Re: Ask HN: What is your favorite CS paper?

#203

Post by michaelmior » Thu, Aug 24, 2017, 11:22 PM UTC

efferifick wrote: post #21

Producing Wrong Data without Doing Anything Obviously Wrong. Immediately useful for anyone measuring compiler transformations performance!

Link: https://www.eecs.northwestern.edu/~robby/courses/322-2013-sp...

Re: Ask HN: What is your favorite CS paper?

#204

Post by p4bl0 » Thu, Aug 24, 2017, 11:38 PM UTC

It's not exactly a paper but I really liked "The Limits of Mathematics" by Chaitin. I wrote a blogpost about it a few years back (https://shebang.ws/the-limits-of-mathematics.html), I already submitted it to HN (https://news.ycombinator.com/item?id=1725936).

Re: Ask HN: What is your favorite CS paper?

#205

Post by surement » Thu, Aug 24, 2017, 11:53 PM UTC

The splay trees paper by Sleator and Tarjan (1985) https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf

It's just such a cool result and the paper is very well written. Further, the dynamic optimality conjecture at the end is still an open problem.

Re: Ask HN: What is your favorite CS paper?

#206

Post by Rickasaurus » Thu, Aug 24, 2017, 11:53 PM UTC

"NP-complete Problems and Physical Reality" by Scott Aaronson. It relates NP-complete problems to examples in nature. Excellent paper and a fun read.

https://arxiv.org/abs/quant-ph/0502072

Re: Ask HN: What is your favorite CS paper?

#207

Post by kruhft » Fri, Aug 25, 2017, 12:05 AM UTC

On Formally Undecidable Propositions... by Kurt Godel.

One might argue this is not CS, but it's something everyone should read and understand.

Re: Ask HN: What is your favorite CS paper?

#208

Post by Retra » Fri, Aug 25, 2017, 12:21 AM UTC

icc97 wrote: post #87

chadash wrote: post #13

It might be a cliche one to pick, but I really really really enjoy Alan Turing's "Computing Machinery and Intelligence"[1]. This paper straddles the line between CS and philosophy, but I think it's an important read for anyone in either field. And a bonus is that it's very well-written and readable. [1] https://www.csee.umbc.edu/courses/471/papers/turing.pdf

Given the far reaching importance of the Turing test, it's amazing how readable and understandable the paper is.

I really don't see how anyone would take that as a given.

Re: Ask HN: What is your favorite CS paper?

#209

Post by KirinDave » Fri, Aug 25, 2017, 12:22 AM UTC

Steeeve wrote: post #201

KirinDave wrote: post #126

I've been trying to get it frontpaged because, despite it's length, it's perhaps one of the most startling papers of this decade. Sadly, it seems like the HN voting gestalt hasn't decided to upvote a paper that's the CS equivalent of breaking the speed of light: "Generic Top-down Discrimination for Sorting and Partitioning in Linear Time" -> http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl... (if you're d…

I have mixed feelings about this one. It certainly has inspired some interesting discussion. The paper itself is obtuse and difficult to absorb. The methodology isn't _really_ new, but it isn't used frequently. While they showed it as competitive to commonly used sorting algorithms, situationally it can really shine and show significant performance benefits. I'm surprised they didn't show this in one of the graphs (o…

The follow-up paper I linked is less massive and shows a use case that were I younger I would set out with as a startup.

I'm not sure why stdlibs for some languages shouldn't take this approach though. It's difficult, sure, but so is any new foundational tech. What do you see as the barrier?

Re: Ask HN: What is your favorite CS paper?

#210

Post by KirinDave » Fri, Aug 25, 2017, 12:24 AM UTC

jules wrote: post #198

KirinDave wrote: post #126

I've been trying to get it frontpaged because, despite it's length, it's perhaps one of the most startling papers of this decade. Sadly, it seems like the HN voting gestalt hasn't decided to upvote a paper that's the CS equivalent of breaking the speed of light: "Generic Top-down Discrimination for Sorting and Partitioning in Linear Time" -> http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl... (if you're d…

This is a nice technique in theory, but in practice it isn't so fast, mainly because of the implementation details. Radix sort is actually faster than comparison sorts if implemented well.

Do you have benchmarks of Kmett's Implementation? I'm very curious.