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

Ask HN: What is your favorite CS paper?

news.ycombinator.com

Post reply on HN
Print view View original

171–180 of 265 posts

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

#171

Post by wrinkl3 »

joaobatalha wrote: post #76

"Reflections on Trusting Trust" by Ken Thompson is one of my favorites. Most papers by Jon Bentley (e.g. A Sample of Brilliance) are also great reads. I'm a frequent contributor to Fermat's Library, which posts an annotated paper (CS, Math and Physics mainly) every week. If you are looking for interesting papers to read, I would strongly recommend checking it out - http://fermatslibrary.com/ - Reflections on Trusting…

The Ken Thompson Hack is a haunting idea. The intelligence agencies almost certainly would've tried to implement it at some point.

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

#172

Post by nokcha »

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…

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

There is a well-known proof from information theory that the problem of sorting n distinct items has a worst-case time complexity of Ω(n log n) fixed-bitwidth operations: (1) Since each of the n items is distinct, the average number of bits needed to encode each item is Ω(log n). (2) In the worst case, in order to correctly sort the items, each bit of each item needs to be read. (3) Therefore, sorting the list requires reading Ω(n log n) bits.

So, I'm not sure how to understand the claim that their algorithm operates in "linear time". Are they saying O(n) operations where each operation operates on O(log n) bits?

[Edit: See below response from kraghen: The time is linear in the total size of the data, not in the number of items. I'll leave this comment up in case anyone has the same misunderstanding that I had.]

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

#173

Post by kraghen »

nokcha wrote: post #172
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…

>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). There is a well-known proof from information theory that the problem of sorting n distinct items has a worst-case time complexity of Ω( n log n ) fixed-bitwidth operations: (1) Since each of th…

Discrimination runs in linear time not in the number of items but in the total size of the data. If you have n items each of size k it takes O(kn). Conventional sorting often assumes that you can compare keys of size k in constant time and therefore gets O(n lg n) but a more honest analysis would yield O(kn log n) for (say) merge sort.

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

#174

Post by NewEntryHN »

nokcha wrote: post #172
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…

>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). There is a well-known proof from information theory that the problem of sorting n distinct items has a worst-case time complexity of Ω( n log n ) fixed-bitwidth operations: (1) Since each of th…

> Are they saying O(n) operations where each operation operates on O(log n) bits

Yes, as in any other claimed complexity about an algorithm. According to your proof finding the maximum in a list is Ω(n log n), which isn't the commonly used measure.

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

#175

Post by chowells »

The Essence of the Iterator Pattern, by Gibbons and Oliveira.

This paper develops a precise model for internal iteration of a data structure, such that exactly the necessary information is exposed and no more.

It's a fantastic exploration of improving a well-known design space with justified removal of details. I keep its lessons in mind whenever I am facing code that seems to have a lot of incidental complexity.

https://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator...

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

#176

Post by ibdknox »

kraghen wrote: post #157
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'm happy to see this excellent paper mentioned. Fritz Henglein (the author) was my thesis supervisor last year, and I worked on developing some of his ideas further. In particular, I generalised discrimination (and added a touch of linear algebra) to devise a simple multi-way join algorithm that computes the join of any number of relations in optimal time (in a specific technical sense). Such results have been obtai…

Is there anything written about your multi-way join algorithm? We've done some really interesting implementations of Generic Join and the like and are always interested in hearing about other potentially better join algorithms.

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

#177

Post by s_gourichon »

KirinDave wrote: post #164
tom_mellior wrote: post #162

Earlier quoted context omitted.

> I dunno how I "persuade" more. In your original post, the first paragraph made you sound like a crank. You said the paper is like breaking the speed of light, but you don't even mention the topic of the paper. I almost stopped reading at that point. Similarly for the sentence towards the end saying that this is "crazy important". People can decide that for themselves. They can decide even better if you put stuff in…

> In your original post, the first paragraph made you sound like a crank. You said the paper is like breaking the speed of light, but you don't even mention the topic of the paper. I almost stopped reading at that point. Similarly for the sentence towards the end saying that this is "crazy important". People can decide that for themselves. They can decide even better if you put stuff into context. I literally mention…

> I have done this twice, tried different tact twice more, and been downvoted or ignored every time.

You should have tried this: "This weird trick by a dad sorts in linear time. Check it out!" Proven to work on so many ad-ridden clickbait websites, so why shouldn't it work on HN? ;-)

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

#178

Post by [deleted] »

nokcha wrote: post #172
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…

>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). There is a well-known proof from information theory that the problem of sorting n distinct items has a worst-case time complexity of Ω( n log n ) fixed-bitwidth operations: (1) Since each of th…

[deleted]

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

#179

Post by KirinDave »

s_gourichon wrote: post #177
KirinDave wrote: post #164

Earlier quoted context omitted.

> In your original post, the first paragraph made you sound like a crank. You said the paper is like breaking the speed of light, but you don't even mention the topic of the paper. I almost stopped reading at that point. Similarly for the sentence towards the end saying that this is "crazy important". People can decide that for themselves. They can decide even better if you put stuff into context. I literally mention…

> I have done this twice, tried different tact twice more, and been downvoted or ignored every time. You should have tried this: "This weird trick by a dad sorts in linear time. Check it out!" Proven to work on so many ad-ridden clickbait websites, so why shouldn't it work on HN? ;-)

"I don't want to live on this planet anymore."

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

#180

Post by nokcha »

kraghen wrote: post #173
nokcha wrote: post #172

Earlier quoted context omitted.

>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). There is a well-known proof from information theory that the problem of sorting n distinct items has a worst-case time complexity of Ω( n log n ) fixed-bitwidth operations: (1) Since each of th…

Discrimination runs in linear time not in the number of items but in the total size of the data. If you have n items each of size k it takes O(kn). Conventional sorting often assumes that you can compare keys of size k in constant time and therefore gets O(n lg n) but a more honest analysis would yield O(kn log n) for (say) merge sort.

Thank you, that cleared up my misunderstanding.
Post reply on HN