Live data from Hacker News

Ask HN: What is your favorite CS paper?

news.ycombinator.com

91–100 of 265 posts

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

#91

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.

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 security over the past 30 odd years. Today, if you care to, you can easily write code that is free of buffer overflows and command injection attacks. In the 00's SQL injection attacks were extremely easy to find; now they're comparatively rare.

Smith's paper tells us that code-as-law is probably a bad idea. But it is not -- and wasn't intended to be -- an indict of static analysis or model-based engineering more generally. Every structural engineer knows the difference between a bridge and a model of a bridge; a paper pointing out the difference without substantively critiquing the practical usefulness of a particular type of model would probably elicit eye-rolls. 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.

But to be sure, the impossibility of codifying human morality is a pretty lame excuse for failing to use static analysis tools or better languages or quality frameworks to prevent known classes of attacks. So I doubt that's what Smith is advocating.

> How many "more careful" Ethereum programmers also check the compiler for correctness?

Yes, we should obviously check compilers for correctness, and we're making slow but sure progress toward a world where our critical infrastructure comes with strong -- of course, never perfect -- correctness guarantees.

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

#92
post #70

The Anatomy of a Large-Scale Hypertextual Web Search Engine, by Brin and Page. Not only for the historical value of changing the world, and for the fact that it's very interesting and readable; It has personal value to me: the first CS paper I've ever read and it inspired me and changed the course of my life, literally. Also, it has some very amusingly naive (in hindsight) stuff in it, like: "Google does not have any…

I was hoping this one would show up. It's a startlingly simple paper, which both made the idea easy to implement (PageRank algorithm can be implemented in around 10 lines of Python, give or take), and easy to game (viz. the rise of link farms). Recommended for anyone with the prerequisite 1 semester of linear algebra or equivalent.

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

#94
The Flajolet-Martin paper on counting unique items in an infinite stream with constant space [1]: a great, well-written introduction to streaming algorithms that triggered my first "aha" moment in the field. You never forget your first.

[1] http://algo.inria.fr/flajolet/Publications/FlMa85.pdf

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

#97
I'll take a broad interpretation of 'CS' and throw out a couple of personal highlights.

C. Shannon, "A Symbolic Analysis of Relay and Switching Circuits" (1940): https://dspace.mit.edu/bitstream/handle/1721.1/11173/3454142...

Shannon's master's thesis, which introduces boolean algebra to the field of digital circuit design.

R.W. Hamming, "Error Detecting and Error Correcting Codes" (1950): https://ia801903.us.archive.org/1/items/bstj29-2-147/bstj29-...

In Hamming's own words: "Damn it, if the machine can detect an error, why can't it locate the position of the error and correct it?"

J.T. Kajiya, "The Rendering Equation" (1986): http://cseweb.ucsd.edu/~ravir/274/15/papers/p143-kajiya.pdf

Kajiya introduces the integral rendering equation, which is the basis for most current techniques of physically based rendering.

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

#99

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.

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.

The programmer only has to comply with the specification. The specification is a finite syntactic entity. If the specification doesn't capture what the user really wants, or compliance is undecidable, or , then the one at fault is the specification writer, not the programmer.

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

#100

"Interactive Indirect Illumination Using Voxel Cone Tracing" by Crassin et al. As an architectural lighting guy, seeing realtime global illumination look this good in a game engine was fantastic. Parts of the algorithm I can understand, parts go over my head still, but the results are amazing. A big part of what I do at work is radiosity simulations in AGI32 which is of course more accurate (because it's trying to ac…

That link doesn't work for me, even though the same link is presented in a Google search. Also, for some reason I can't find it via search by DOI.

http://research.nvidia.com/publication/interactive-indirect-... has the paper plus presentation available, plus abstract and other links.

Post reply on HN