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

151–160 of 265 posts

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

#151

Post by KirinDave »

and0 wrote: post #146
KirinDave wrote: post #133

Earlier quoted context omitted.

Check my submission history. I tried twice. I dunno how I "persuade" more.

Complaining that people aren't paying attention to a sorting paper is kinda weird and makes people take you less seriously. Try to write a blog post on Medium that breaks it down and submit it that way.

Why on earth would I write for Medium? Will they pay me?

I think it's weird that the entire industry is not burning a hole in the atmosphere as they run to implement this wherever they can. It's a very big deal.

I suspect the problem is the paper is 80 pages. But I did link to a youtube talk that covers all the core features.

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

#153

Post by KirinDave »

gbacon wrote: post #149
stevenschmatz wrote: post #136

Earlier quoted context omitted.

What's the catch? Are there any preconditions on the input required?

What are the constants hiding inside that 𝒪(𝑛)?

They can be bad. But so was merge sort in its naive implementation and folks worked that out. Radix sort sees a lot of use in the real world and it saves a lot of energy.

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

#155

Post by kageneko »

Oh man... I don't know. There's so many.

I'll need to go with

Gilbert, E., & Karahalios, K. (2009, April). Predicting tie strength with social media. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (pp. 211-220). ACM.

In grad school, it was the paper that kept on giving. I think I cited it every semester for a paper or project. There's a lot of other papers and books that really inspired me, but this one was magic.

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

#156

Post by tom_mellior »

throwawayjava wrote: post #91
tom_mellior wrote: post #47

Earlier quoted context omitted.

Part of the linked paper's point is that because computer systems involve many "levels of failure", even a more careful programmer cannot usually rule out every class of programs. The DAO hack, yes, possibly. But, for example, people have also lost money due to bugs in the Solidity compiler: https://np.reddit.com/r/ethtrader/comments/5foa5p/daily_disc... How many "more careful" Ethereum programmers also check the com…

> Part of the linked paper's point is that because computer systems involve many "levels of failure", even a more careful programmer cannot usually rule out every class of programs. But -- and this is the crucial point -- that doesn't mean we shouldn't strive to be better than we are now. The impossibility of perfectly modeling the world hasn't prevented us from making enormous progress on software safety and securit…

> But -- and this is the crucial point -- that doesn't mean we shouldn't strive to be better than we are now.

Agreed! And I also agree that we are really making progress. But we're far from a world where people can crank out provably correct code (let alone the proofs).

> I'm not sure why these mundane observations receive such attention in computer science. Maybe because with software the model and the system look so similar.

Excellent point, and yes, I think that is the problem. Modeling the world in code is not much different from... er... modeling the world in code :-)

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

#157

Post by kraghen »

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 obtained recently, but only with far more complicated algorithms.

Alas, the fully general proof of optimality eludes us, so nothing has been published yet.

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

#158

Post by amelius »

vaibhavsagar wrote: post #86

There are a ton of fantastic Haskell papers, but if I had to pick one this would be it. It reconciles the pure and lazy functional nature of Haskell with the strict and often messy demands of the real world: State in Haskell. John Launchbury and Simon L. Peyton Jones https://www.microsoft.com/en-us/research/wp-content/uploads/...

I like Haskell papers and books but they often reference the "Core" language, for which an accessible implementation seems to be lacking, which is a missed opportunity, imho. Yes, I know it is part of GHC, but it is buried under several layers of undocumented code. GHC could have been much more open to research if they modularized and documented everything more thoroughly.

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

#159

Post by KirinDave »

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…

I can only do a humble and poor job of explaining this process by analogy to other algorithms. If you've got a better explanation I could rote memorize, I'd be very appreciative.

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

#160

Post by djhworld »

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…

This is a really nice site, but the owner should really enable HTTPS if they want people to give their email address over for the newsletter
Post reply on HN