1. 54

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.

  1.  

  2. 15

    I’d strongly suggest digging around over at cat-v for interesting papers. They tend to be extremely approachable memos (informal, even!) and have a degree of practicality that I feel is missing from most academic CS that I’ve seen.

    Some good ones there:

    Plan 9 is a hell of a drug.

    1. 12

      Try http://paperswelove.org.

      | Papers We Love is a repository of academic computer science papers and a community who loves reading them.

      It’s a git repo of classic CS papers and a website for people who want to get together to discuss them. Some of the papers are easy, some hard, but a treasure trove to work your way through.

      1. 6

        Thanks for the PWL shout-out. PWL was started as a reading group within our old company, and we began with Out of the Tarpit and Communicating Sequential Processes. Those were the first papers I read, and I found them widely applicable, interesting, and approachable.

        1. 3

          In the same spirit, I really enjoy Fermat’s Library. I don’t really read the annotated versions most of the times, as the website is set up in a way that makes it annoying for me (which is a shame, the comments are normally pretty great), but use it mostly as a feed of interesting papers to read on different areas.

          1. 1

            It’s a huge repo, any guidelines to find the ones which are easy/beginner friendly?

            1. 6

              The section on design is a good start, especially “No Silver Bullet” (NSB) and “Out of the Tarpit” mentioned above.

              Fred Brooks, who wrote NSB, also wrote another classic before that called “The Mythical Man Month” which is sold on Amazon as a collection of papers, including NSB.

              A Mathematical Theory of Communication” by Claude Shannon is the foundational work in information theory.

              Reflections on Trusting Trust” is a great read and eye opening as an intro to security.

              The Unix Time-Sharing System” by Dennis Ritchie and Ken Thompson is the classic intro to Unix.

              In addition to these and others from PWL, I’d also add Dijkstra’s paper “Go To Statement Considered Harmful”. Whether you agree or disagree, it’s the seminal paper on structured programming.

              I’d start with those, follow interesting footnotes and references to see where they lead you.

          2. 9

            An absolute must: On computable numbers, with an application to the Entscheidungsproblem - Turing, 1936

            It’s very readable, if the finicky details are skipped over. This paper defines Turing Machines, universal machines and computability, shows that the “decision problem” (Entsheidungsproblem) is unsolvable and (in an appendix) shows that these notions of Turing Machines and “computable” are exactly equivalent to Alonzo Church’s notions of lambda calculus and “effectively calculable”.

            1. 6

              Not quite CS but definitely for Software Engineer, I suggest ones that inform system design:

              Unix Program Design: Designing programs that do one thing.

              http://harmful.cat-v.org/cat-v/unix_prog_design.pdf

              End-to-end Argument in System Design: Where to put various aspects of a system and why putting them in some places is a worse idea than otherwise.

              http://web.mit.edu/Saltzer/www/publications/endtoend/endtoend.pdf

              On the Criteria of Decomposing a System into Modules: How to split a system up (tl;dr information hiding).

              https://www.cs.umd.edu/class/spring2003/cmsc838p/Design/criteria.pdf

              1. 5

                Here’s a few I found in whilst digging around in my library.

                • Iterative and Incremental Development: A Brief History (pdf) (DOI). In case you thought the approach in agile was new.
                • On Understanding Data Abstraction, Revisited (pdf) (DOI). Good discussion of ADTs and objects. Now that I suggest it, I should probably read it again!
                • SELF: The Power of Simplicity (pdf]) (DOI). You’ll learn a lot if you study David Ungar’s work.
                • Static Typing Where Possible, Dynamic Typing When Needed (pdf) A bit of a classic, and good jumping off point. Not terribly technical.
                • Recursive Functions of Symbolic Expressions and Their Computation by Machine (see http://www-formal.stanford.edu/jmc/recursive.html). The original Lisp paper from 1959/1960. Slightly advanced, but once you grok it, you’re on your way to enlightenment.
                • How Complex Systems Fail (pdf). Not a paper – not even CS or engineering – but worth reading if you work with computers.

                In general, papers from the 70s are easier to get through because they don’t rely on excessive references and don’t contain too much handwriting in comparison to the 60s and earlier. (And trust me, most of the principles you need can be found in papers from the 70s.) Once you get to the 80s, things shift a bit, but there is still lots of good stuff there. Things start to get hairier in the 90s. Look for survey papers; they tend to summarize more and are longer.

                Happy reading!

                1. 4

                  Propositions as Types - Philip Wadler 2014

                  1. 4

                    Some favorites:

                    1. 4

                      I enjoyed the Scuttlebutt/flow-gossip paper https://www.cs.cornell.edu/home/rvr/papers/flowgossip.pdf Has some cool use-cases: https://staltz.com/an-off-grid-social-network.html

                      1. 4

                        Some of the greatest revelations I had in CS literature where:

                        I would also ask if you have a link/citation/DOI for the papers you mention, I would like to check some of them out!

                        1. 2

                          Although the “Floating Point” paper is quite long and technical, it pays to read the first 10% or thereabouts. You really need to get an appreciation for how difficult floating point is in a computer compared to outside of the computer. I waited too long to read it.

                        2. 4

                          A prior submission whose original post and comments had stuff that might interest you:

                          https://lobste.rs/s/8spf4d/10_papers_every_programmer_should_read_at

                          Per Brinch Hansen also had quite a bit of influence on OS’s and such without many knowing it. He wrote some great papers on tech such as RC 4000, Solo, Concurrent Pascal, Edison (ran on PDP 11/45), and so on. His Evolution of Operating Systems has nice summaries except for MULTICS where you should go to the Multicians instead.

                          http://brinch-hansen.net/papers/

                            1. 2

                              That’s the one I was looking for! Just couldn’t remember the words in the title. Thanks!

                            2. 2

                              I’ll have to find my original and post it someplace. It looks like the link is down.

                              1. 2

                                Definitely do. Already got a nice pot of gold in this thread and its links. More gold is good. :)

                            3. 4

                              A short, readable and widely cited paper, and the author won a Turing award recently:

                              Time, Clocks and the Ordering of Events in a Distributed System by Lamport

                              https://amturing.acm.org/p558-lamport.pdf

                              Threads I’ve saved from HN and reddit:

                              https://news.ycombinator.com/item?id=2922108

                              https://www.reddit.com/r/programming/comments/9220o/ask_proggit_recommender_a_compsci_paper_for_me_to/

                              (Ha, Lamport’s paper is #1 there!)

                              1. 3

                                http://alistair.cockburn.us/Characterizing+people+as+non-linear%2c+first-order+components+in+software+development

                                It’s a handy reminder that the absolute number one top problem (and solution) in the whole damn field is….

                                People.

                                1. 2

                                  I wish I could +1 this thread several times. Pure gold :) Great responses all!

                                  1. 2

                                    My favorite is “Equal Rights for Functional Objects” http://home.pipeline.com/~hbaker1/ObjectIdentity.html

                                    In which Henry Baker proposes the egal equality predicate and why it’s so common for languages to get equality semantics wrong. In particular the notion that two objects are effectively identical if the language offers no way to meaningfully tell them apart (usually by mutating one and comparing) is very helpful even beyond FP languages. (Lua implements this, for instance.)

                                    1. 2

                                      Also asked – with the exact same wording (by the same person?) – on HN.

                                      1. 2

                                        There usually aren’t too many machine learning papers on this list so I have to suggest a few.

                                        Bandit based Monte-Carlo planning

                                        This is the paper that introduced Monte-Carlo tree search and is a core part of AlphaGo. The algorithm is super simple and most of paper is the theory behind it, which is actually not incomprehensible.

                                        Statistical Modeling: The Two Cultures

                                        Leo Breiman’s paper on how Machine Learning people solve problems vs statisticians is as timeless as the day it was first written. Notably he doesn’t take sides which is very refreshing.

                                        A Mathematical Theory of Communication

                                        Claude Shannon’s paper is extremely accessible for something so foundational. This is the paper that I would argue started machine learning. All the ideas that we use to this day are in there. The way we think about the problem hasn’t changed all that much. As a bonus, Shannon’s paper The Bandwagon is still relevant to navigating AI hype.