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

211–220 of 265 posts

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

#211

Post by [deleted] »

KirinDave wrote: post #186
throwawayjava wrote: post #40

Earlier quoted context omitted.

FWIW I think this is a very fair question. Parent's post veers a bit further toward defeatism than I think Smith's paper advocates for or justifies. In particular, of course the DAO hack wasn't inevitable -- a more careful programmer could've foreseen and prevented that attack and whole other classes of attack.

Given how bad the tooling is for Eth right now, it probably was inevitable. Their tooling isn't just a mess semantically and syntactically, it's was riddled with double-operation bugs.

[deleted]

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

#212

Post by kwindla »

Alexia Massalin’s 1992 PhD thesis describing the Synthesis Operating System.

  http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.4871&rep=rep1&type=pdf
Here's Valerie Aurora’s description of Synthesis:

... a completely lock-free operating system optimized using run-time code generation, written from scratch in assembly running on a homemade two-CPU SMP with a two-word compare-and-swap instruction — you know, nothing fancy.

Which (necessarily) undersells by a very large margin just how impressive, innovative, and interesting this thesis is.

If you’re interested in operating systems, or compilers, or concurrency, or data structures, or real-time programming, or benchmarking, or optimization, you should read this thesis. Twenty-five years after it was published, it still provides a wealth of general inspiration and specific food for thought. It’s also clearly and elegantly written. And, as a final bonus, it’s a snapshot from an era in which Sony made workstations and shipped its own, proprietary, version of Unix. Good times.

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

#214

Post by kwillets »

kraghen wrote: post #195
kwillets wrote: post #188

Earlier quoted context omitted.

The bound on string sorting is typically written as O(n log n + D), where D is the sum of distinguishing prefixes, ie input length minus some fluff. Since D >= n log n we already have linearity on input length.

Are you saying that you can sort strings in O(n log n + D) using a conventional sorting algorithm such as merge sort? If so, I don't understand why D would be an additive factor implying that each string is only involved in a constant number of comparisons. (I wasn't, by the way, only considering strings when discussing variable sized keys -- the beauty of discrimination is that we essentially reduce all sorting prob…

A conventional sorting algorithm such as Multikey Quicksort.

http://people.mpi-inf.mpg.de/~sanders/courses/algdat03/salgd...

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

#215

Post by Steeeve »

KirinDave wrote: post #209
Steeeve wrote: post #201

Earlier quoted context omitted.

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?

complex to do right, limited usefulness, potential for a great deal of memory usage, lack of a common understanding of proper use cases.

I can totally see it as part of any number of extended libraries.

Just my opinion though. I would be happy to be wrong.

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

#216

Post by defined »

akkartik wrote: post #36

Peter Naur, "Programming as theory building." (1985) “…programming properly should be regarded as an activity by which the programmers form or achieve a certain kind of insight, a theory, of the matters at hand. This suggestion is in contrast to what appears to be a more common notion, that programming should be regarded as a production of a program and certain other texts.” http://pages.cs.wisc.edu/~remzi/Naur.pdf h…

This really is a paper with deep implications.

One of them, as I understand it, is that in any significant software project, regardless of the volume and quality of the documentation, or quality of the code base, maintainers not involved in building the original project will not be able to build the "theory" correctly in their minds, and will consequently make changes that are clumsy or detrimental. (I'm summarizing, so some important aspects have been skipped).

I see this aspect of the paper as related to the "conceptual integrity" discussed in the Mythical Man-Month.

This paper has long been one of my favorites, and was first brought to my attention when I was reading (IIRC) one of Alistair Cockburn's books. Sadly, few of the people I shared it with found it interesting.

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

#217

Post by vaibhavsagar »

amelius wrote: post #158
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.

I think SPJ would agree with you. Have you seen https://www.youtube.com/watch?v=uR_VzYxvbxg?

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

#218

Post by manigandham »

djhworld wrote: post #160
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

Why? Emails are not private information.

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

#219

Post by exikyut »

exelius wrote: post #184
wrinkl3 wrote: post #171

Earlier quoted context omitted.

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

They have -- this is basically what Stuxnet did. Some of the equation group leaks were even further advanced -- they installed themselves in the hard drive firmware, then hid the sectors where the exploit code was stored even from the BIOS . So point is, it's been done. That's why the Equation Group malware operated undetected for almost a decade (and maybe longer than that). Never underestimate the power of a govern…

> they installed themselves in the hard drive firmware, then hid the sectors where the exploit code was stored even from the BIOS.

Where can I read more technical details (such as code analysis) about this?

I've never heard of anything like this hiding for 10 years before.

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

#220

Post by Denzel »

learningram wrote: post #129
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…

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.

Different people have different reactions. That line is actually what piqued my interest.

Since AP CompSci in HS it's been hammered into students that any sort based on comparisons has a strict lower bound of O(n*log n).

And sorting is particularly important in search engines, of which I've been working on.

So, an algorithm that drastically improves the speed of sorting would actually open up a few more possibilities to consider.

Thanks for sharing the paper KirinDave, I plan to read it.

Post reply on HN