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

161–170 of 265 posts

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

#161

Post by andars »

jacobolus wrote: post #142
coherentpony wrote: post #120

An Algorithm for the Machine Calculation of Complex Fourier Series James W. Cooley and John W. Tukey Mathematics of Computation Vol. 19, No. 90 (Apr., 1965), pp. 297-301 https://www.jstor.org/stable/2003354

Apparently this FFT was first discovered by Gauss (1805). http://www.cis.rit.edu/class/simg716/Gauss_History_FFT.pdf As a follow-up, let me recommend Püschel & Moura (2006) “Algebraic Signal Processing Theory”, https://arxiv.org/pdf/cs/0612077.pdf and Püschel’s other papers about similar topics. Or in a different direction, DJB (2008), “Fast multiplication and its applications”, http://cr.yp.to/lineartime/multapps-20…

Interesting to note that Fourier's two works were published in 1807 and 1822, so that work by Gauss also predates Fourier.

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

#162

Post by tom_mellior »

KirinDave wrote: post #133
learningram wrote: post #129

Earlier quoted context omitted.

You really improve your persuasion skills. >Sadly, it seems like the HN crowd won't upvote a paper that's the CS equivalent of breaking the speed of light: Comments like this will turn people off the rest of your post.

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

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

So to persuade more, for this specific post of yours, I would have suggested to replace the first paragraph by something like: "Here is a surprising paper that shows that you can sort general data structures in linear time!"

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

#163

Post by kraghen »

stevenschmatz wrote: post #136
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…

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

All orderings must be specified as a reduction to a primitive order using the fact that if you have an equivalence relation on some type A and a reduction f : B -> A then you have an equivalence on B defined by x = y when f(x) = f(y).

Now, take the rational numbers. For the usual binary comparison we can simply define (a/b) In fact, I'm not aware of any systematic way of deriving discrimination-suitable orderings from binary predicates -- it might be an open research problem, as far as I am aware.

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

#164

Post by KirinDave »

tom_mellior wrote: post #162
KirinDave wrote: post #133

Earlier quoted context omitted.

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

> 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 the TITLE of the paper, itself precisely explaining its domain & method, directly after the statement and end it with a semicolon.

Let's be real here. The paper is a real dragon of a read. If you're not going to go past a single surprising sentence maybe it was pointless for me to mention it anyways.

> "Here is a surprising paper that shows that you can sort general data structures in linear time!"

I have done this twice, tried different tact twice more, and been downvoted or ignored every time. This is the new me, assuming that folks just don't know how their every artifice of computation is backed by sort. And I suppose... why would they? A great many people simply skip even the basic theory of computation as they join the industry now, and maybe that's okay.

But I say it precisely as I do to generate shock. It should be surprising. I've caught people interviewing for principal engineering positions at Google and Amazon off guard with this. It's very, very surprising.

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

#165

Post by KirinDave »

kraghen wrote: post #163
stevenschmatz wrote: post #136

Earlier quoted context omitted.

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

All orderings must be specified as a reduction to a primitive order using the fact that if you have an equivalence relation on some type A and a reduction f : B -> A then you have an equivalence on B defined by x = y when f(x) = f(y). Now, take the rational numbers. For the usual binary comparison we can simply define (a/b) In fact, I'm not aware of any systematic way of deriving discrimination-suitable orderings fro…

> In fact, I'm not aware of any systematic way of deriving discrimination-suitable orderings from binary predicates -- it might be an open research problem, as far as I am aware.

That'd be an even more remarkable discovery in light of the stuff you worked on though, wouldn't it?

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

#166

Post by vsrinivas »

From the perspective of - 'take a fresh look at something we take for granted' - "A Preliminary Architecture for a Basic Data-Flow Processor" (Dennis & Misunas 1975)

Focusing on the flow of data between operators and greedily executing a linear program is what an out-of-order processor is.

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

#167

Post by kraghen »

KirinDave wrote: post #159
kraghen wrote: post #157

Earlier quoted context omitted.

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.

I can't say I have had much success explaining my thesis clearly to anyone except people from the same department, but I can try to give my understanding of discrimination from an implementor's perspective.

The succinct version is that all (discrete) data can be serialised as bit strings and those bit strings can be sorted in linear time by (say) radix sort.

There are two ideas at work here: that all (discrete) data structures ultimately are composed of primitive types that can be sorted in linear time, and that we should only examine each primitive value once.

However, to be fair it should be mentioned that the analysis uses a different machine model (the RAM model) than is usually employed in sorting (where all comparisons are considered to take constant time, which is arguably an inferior model of real computers if you are sorting e.g. strings of variable length).

To be honest, though, the original paper is so well-written that I have a hard time explaining it better.

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

#168

Post by kraghen »

KirinDave wrote: post #165
kraghen wrote: post #163

Earlier quoted context omitted.

All orderings must be specified as a reduction to a primitive order using the fact that if you have an equivalence relation on some type A and a reduction f : B -> A then you have an equivalence on B defined by x = y when f(x) = f(y). Now, take the rational numbers. For the usual binary comparison we can simply define (a/b) In fact, I'm not aware of any systematic way of deriving discrimination-suitable orderings fro…

> In fact, I'm not aware of any systematic way of deriving discrimination-suitable orderings from binary predicates -- it might be an open research problem, as far as I am aware. That'd be an even more remarkable discovery in light of the stuff you worked on though, wouldn't it?

It might, I never really discussed this aspect with Fritz! For my thesis I was mostly focussed on applications to database queries, and I never encountered any concrete examples of orderings that couldn't be dealt with in an obvious way using discrimination based sorting.

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

#170

Post by nikhizzle »

lukateake wrote: post #103
nikhizzle wrote: post #15

Without a doubt. Time, Clocks, and the Ordering of Events in a Distributed System. Leslie Lamport. http://amturing.acm.org/p558-lamport.pdf My first introduction to time scales as a partial ordering. Very mind opening.

Your link is throwing a 404 for me. I found it here: https://www.ics.uci.edu/~cs230/reading/time.pdf

That is not the paper. It appears to be a summary.
Post reply on HN