Ask HN: What is your favorite CS paper?

Project:M36 is an implementation of the proposed design from the "Out of the Tarpit" paper.

https://github.com/agentm/project-m36

Damn, did not expect to see this paper on here. When I read it, I wasn't thinking it could be listed under the "all-time favorite CS papers", but the connections are quite interesting and (retrospectively) intuitive.

I'll be interested to see where/(if) it gets published.

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 daunted by an 80 page paper as I am, there is also a talk on it: https://www.youtube.com/watch?v=sz9ZlZIRDAg)

It is possible, with some proper insight and approaches, to sort general datastructures in linear time on modern computing hardware. The speed limit of sort is O(n) with some extra constant cost (often accrued by allocation). It works by decomposing and generalizing something akin to radix sort, leveraging a composable pass of linear discriminators to do the work.

There's a followup paper using this to make a very efficient in-memory database that one could easily generalize under something like kademelia and with care I suspect could make something like a better spark core.

http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl...

I keep submitting and talking about this but no one seems to pick up on it. This paper is crazy important and every runtime environment SHOULD be scrambling to get this entire approach well-integrated into their stdlib.

Unsurprisingly, Kmett has already implemented it in Haskell (it generalized neatly under the dual of the applicative+alternative functor): https://hackage.haskell.org/package/discrimination

Given that I'm an ignorant. Can you ELI5 like what is the impact of this? What does it change? What can you do with it on practical terms?

Yao's minimax principle. It's not a very exciting read or a very exciting conclusion compared to some of these other papers, but it's still interesting, and the conclusion has been practically useful to me a small handful of times.

It concerns randomized algorithms, which are algorithms that try to overcome worst case performance by randomizing their behavior, so that a malicious user can't know which input will be the worst case input this time.

The principle states that the expected cost of a randomized algorithm on a single input is no better or worse than the cost of a deterministic algorithm with random input.

Yao proves this is the case by constructing two zero sum games based around the algorithms' running times and then using game theory (specifically von Neumann's minimax theorem) to show that the two approaches are equivalent. It's a really neat approach!