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

181–190 of 265 posts

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

#181

Post by Analemma_ »

xenophonf wrote: post #117
larkeith wrote: post #79

The Night Watch by James Mickens is always a good read: https://www.usenix.org/system/files/1311_05-08_mickens.pdf

That's a good one, but I think "This World of Ours", Mickens' treatise on the practical realities of operational security (specifically keying material handling), should take the top spot: https://www.usenix.org/system/files/1401_08-12_mickens.pdf

The nice thing about this one is that it actually does have some important kernels of truth amid all the hilarity. Especially this bit about threat models:

> Basically, you’re either dealing with Mossad or not-Mossad. If your adversary is not-Mossad, then you’ll probably be fine if you pick a good password and don’t respond to emails from ChEaPestPAiNPi11s@ virus-basket.biz.ru. If your adversary is the Mossad, YOU’RE GONNA DIE AND THERE’S NOTHING THAT YOU CAN DO ABOUT IT

More security researchers need to learn about that.

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

#182

Post by ehudla »

yaseer wrote: post #37
agentultra wrote: post #31

Most of my favourites have already been listed but one I found particularly interesting was Von Neumann's Theory of Self-Reproducing Automata [0]. [0] http://cba.mit.edu/events/03.11.ASE/docs/VonNeumann.pdf

+1 to this. Von Neumann was well ahead of his time with his automata ideas. I found in interesting how both Von Neumann and Turing turned to analyse biological systems later in their careers.

Some of you might be interested in an essay I wrote about von Neumann and Norbert Wiener that gives some of the background and context of this work.

http://www.ehudlamm.com/outsiders.pdf

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

#183

Post by nicoburns »

majewsky wrote: post #102
oculusthrift wrote: post #90

Earlier quoted context omitted.

maybe i'm a little stringent but if if isn't peer reviewed and in a journal, i don't consider it a paper.

I guess that, given its impact, it's more peer-reviewed than most published papers.

I think that this is an important point: that just because something isn't in a journal, doesn't mean that it hasn't been peer reviewed!

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

#184

Post by exelius »

wrinkl3 wrote: post #171
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.

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 government -- they can afford to hire and train an army of Ken Thompsons for the price of an aircraft carrier.

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

#185

Post by mrlyc »

My favourite is "Targeting Safety-Related Errors During Software Requirements Analysis" by Robyn Lutz at the Jet Propulsion Laboratory. It's available at https://trs.jpl.nasa.gov/bitstream/handle/2014/35179/93-0749...

The article provides a safety checklist for use during the analysis of software requirements for spacecraft and other safety-critical, embedded systems.

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

#186

Post by KirinDave »

throwawayjava wrote: post #40
catnaroek wrote: post #26

Earlier quoted context omitted.

> you will see that the DAO hack and its reversal as inevitable. Honest naïve question. What's the proof?

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.

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

#188

Post by kwillets »

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.

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.

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

#189

Post by exelius »

monocasa wrote: post #34
exelius wrote: post #24

The Mythical Man-Month https://www.cs.drexel.edu/~yfcai/CS451/RequiredReadings/Myth...

And the paper that inspired it, Melvin Conway's "How Do Committees Invent?" http://www.melconway.com/Home/Committees_Paper.html

This is great -- I never knew about this paper but it reinforces a lot of things I learned. Namely, if you want to know how a company really works, ignore the org charts and map the systems architecture (a corollary to the author's thesis).

That it still holds true almost 50 years later is pretty amazing.

Post reply on HN