HN Explorer

Ask HN: What are some interesting papers in CS for a beginner?

534 points by avinassh ↗ HN
I am looking for papers which are easy to understand, papers which are for undergraduates. I often stumble upon papers which require lots of reading to do and soon I have dug into a recursive rabbit hole. I would like to know about papers which have minimal citations/dependencies and only require knowledge of CS basics.

A good example of such paper would be Bitcoin. You don't need to be a CS wizard to understand the paper. Plus, you can ignore the math part and yet appreciate the beauty of Bitcoin.

Some other examples: Bit Torrent, TOTP RFC.

93 comments

[ 3.0 ms ] story [ 192 ms ] thread
iainmerrick
Pixar published a lot of great, groundbreaking graphics papers in their early days. (They still do, but as the field is more mature now there's a lot more background reading required.)

For example, I think this one on their rendering pipeline REYES (Render Everything You Ever Saw) is pretty readable, and gives a great overview of how they rendered stuff like Red's Dream, in the years leading up to Toy Story: http://graphics.pixar.com/library/Reyes/paper.pdf

(Edit to add: in fact, just check out the overviews at http://graphics.pixar.com/library/ which are much better than I can describe here)

luvbb
I suggest Alan Turning's 1950 Computing Machinery and Intelligence. Many of the ideas first written in this paper are commonly referenced. It's good to have read the primary source. Do machines think? If you know what a theoretical Turning Machine is you'll have all the prerequisite knowledge. If not you can skip over that part. Do they still teach Turning Machines in Highschool?

http://www.loebner.net/Prizef/TuringArticle.html

luckyt
> Alan Turning

> Turning Machine

His name's Turing

fhood
Benefit of the doubt. He could just be used to automatically typing turning. I add apostrophes to want (wan't) all the time.
moomin
It’s also a pretty common autocorrect. A fair few of us post using our phones and I’m always horrified to see what actually got posted when I look at it 61 minutes later.
mercer
Ha, I literally had 'What are Turing machines?' as my Question of the Week. Thanks for the link. Any other good links to help me find the best answer to this question?
dharmon
The original paper can get a bit dense at times. I recommend Petzold's "The Annotated Turing" for a guided tour.
potbelly83
The original paper was the 1936 one. This is a different paper.
inputcoffee
I suggest that the undergrads be encouraged to go to Arxiv and browse papers, try to work through them and see the range of papers.

The reason for this is that many papers aren't all that well written and well argued. Many are, to be sure, but it will get undergrads to understand what is clear, what is not.

It will also ensure that they are not intimidated by papers and the math on them. They should know they can dive into one and learn something and come out the other end.

But if you want specific recommendations, I find that the HCI (Human Computer Interaction) papers are very readable. Maybe its the people drawn to the field?

Here is just a random example:

https://arxiv.org/pdf/1711.03115.pdf

anddyyyy
Duplicated in my other reply, but the Weiser paper on ubiquitous computing is excellent.
nmca
Playing Atari with deep q learning :)
robotresearcher
Lamport's 'Time, Clocks and the Ordering of Events in a Distributed System'. Very readable and, if you are new to distributed systems, really fast way to get a useful new mental model.

https://www.microsoft.com/en-us/research/publication/time-cl...

tincholio
That is a really wonderful paper, indeed. It's very clearly written (as anything by Lamport), and provides a simple and elegant solution to a complicated problem.
henrik_w
On the subject on distributed systems, I like this quote by Lamport:

"A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable." Leslie Lamport

hood_syntax
Finally got around to reading that paper after seeing your comment. What a great piece! The logic was clearly laid out and simple to follow. I'll have to read through the proof in the appendix later.
robotresearcher
Thanks for the feedback! I've assigned that paper to hundreds of 4th year undergrads, and I always enjoy discussing it with them. I've also had my grad students read it as a model for how to structure a paper.
josefdlange
The Raft paper [0] is a great read but context of distributed systems and the importance of consensus algorithms is probably a prerequisite. Once you understand the context, it's a nice read that it small enough to contain within your mind in one or two reads.

[0]: https://raft.github.io/raft.pdf

mixermf
The Byzantine Generals Problem's only prereq is familiarity with basic mathematical notation and a willingness to read carefully. The paper is seminal; it articulates a major computer security concern, the concern that rogue nodes in a network may lie in their communications.

https://www.microsoft.com/en-us/research/wp-content/uploads/...

pjmorris
I really like 'Hints for Computer System Design', Butler Lampson [0]. He passes on useful experience without demanding much in preparation from the reader.

[0] https://www.microsoft.com/en-us/research/wp-content/uploads/...

aloukissas
+1 everyone building any sort of system should read this. Often.
glangdale
Yup, came here to post this one. There are many great papers that someone should read but this one is more or less a good read for everyone.
yueq
Google's classic papers on PageRank, MapReduce, BigTable and GFS.

Amazon's Dynamo.

Twitter's Cassandra.

halayli
It’s hard reading random papers like that without deeply understanding the problem they are trying to solve. Sometimes understanding the true problem is more difficult than the solution in the papers.

What I would suggest instead as a learning exercise is to pick a domain you want to tackle and reinvent the wheel by implementing it. while doing so you’ll naturally find yourself digging into research papers. The advantage here is that during implementation you’d have understood the problem and the context much better and can relate to what the authors are discussing and trying to solve. Instead of moving backwards from solution to problem.

drharby
>reinvent the wheel, it's how we get better wheels

-john carmack

    -michael scott
joaobatalha
"Reflections on Trusting Trust" by Ken Thompson is one of my favorites, and fairly self contained.

Most papers by Jon Bentley (e.g. "A Sample of Brilliance") are also great reads and usually pretty short.

I'm a frequent contributor to Fermat's Library (https://fermatslibrary.com), which posts an annotated paper (CS, Math and Physics mainly) every week. In the annotations you will usually find a concise piece of knowledge that helps you understand some part of the paper without having to spend a long time in the "recursive rabbit hole". For instance, in the Bitcoin paper, there is an annotation with a succinct explanation of the essential cryptography concepts (Hash functions, Public Key Cryptography, Signatures) you need to know to understand the paper. And the nice thing is that if you feel so inclined, you can add your own annotations and make the paper easier to grasp for the next person who reads it :)

- Reflections on Trusting Trust (Annotated Version) - http://fermatslibrary.com/s/reflections-on-trusting-trust

- A Sample of Brilliance (Annotated Version) - http://fermatslibrary.com/s/a-sample-of-brilliance

- Bitcoin: A Peer-to-Peer Electronic Cash System - https://fermatslibrary.com/s/bitcoin

faizshah
I like Pugh's paper on skip lists [1], Shannon's "Mathematical Theory of Communication" [2], and these two might be a stretch but I also like Rong's "Word2vec Parameter Learning Explained" [3] and Levy & Goldberg's "Word2vec Explained" [4]. In any case use the recommended papers to learn paper reading skills e.g look at references when you don't understand a concept, find an introductory textbook to clarify a proof method, write a summary to make your understanding concrete. Good Luck!

[1]: http://courses.cs.vt.edu/cs2604/fall05/wmcquain/Notes/Supple...

[2]: http://math.harvard.edu/~ctm/home/text/others/shannon/entrop...

[3]: https://arxiv.org/pdf/1411.2738.pdf

[4]: https://arxiv.org/pdf/1402.3722.pdf

shanusmagnus
Great suggestions. I wish Fermat's Library would do the Shannon paper -- I suggested it, it seems an obvious choice, but no dice :(