Fabian's Recommened Reading List

reading-list.md

Papers I like Pt. 1 Papers I like Pt. 2

Let's start meta:

1. Lamport - State the Problem Before Describing the Solution (1978). … 1-page memo. Read it.
2. Herlihy - Wait-free synchronization (1991) … Truly seminal. Lucid + enough good ideas for 4 papers easily.
3. Cook - How complex systems fail (1998) … 4 pages that anyone working on/with complex systems should read.
4. Moffat, Turpin - On the Implementation of Minimum Redundancy Prefix Codes (1997) … Much has been written about Huffman coding, a lot of it wrong. Almost everything worth knowing is in this (short!) paper.
5. 1. Dybvig, Hieb, Butler - Destination-Driven Code Generation (1990) … A simple, beautiful way to improve code gen forfast one-pass compilers.
   2. Milliken - One-pass Code Generation in V8 (year?)
      … makes a great companion piece.
6. Valmari - Fast brief practical DFA minimization (2012) … Takes a classic algorithm by Hopcroft that textbooks struggled to explain (or mostly omitted entirely) for decades, and simplifies it down to a (not particularly technical) 5-page paper.
7. Sarnak, Tarjan - Planar Point Location Using Persistent Search Trees (1986) … an interesting problem in its own right, and this paper solves it by introducing persistent search trees made efficient using a beautiful idea (section 3!).
8. Porter, Duff - Compositing Digital Images (1984) … Obligatory mention. Every half-year or so, another blog post crosses my timeline where someone excitedly sings the praises of premultiplied alpha. We need to get better about teaching this.
9. Brandt - Hard Sync Without Aliasing (2001) … Introducing MinBLEPs for bandlimited synthesis. Such an awesome idea!
10. Veach - Robust Monte Carlo Methods for Light Transport Simulation (PhD thesis, 1997) … wherein he invents a big chunk of modern light transport sim. A tour de force.
11. Goto, van de Geijn-Anatomy of high-performance matrix multiplication (2008) … how a high-perf GEMM works.
12. Chazelle-Filtering search: a new approach to query-answering (1986) … balancing preprocessing and query time, as applied to several geometric search problems. Not exactly easy reading but worth your time!
13. McIllroy-A Killer Adversary for Quicksort (1999) … how to do adversarial testing right. Worth studying!
14. Knuth-Structured Programming with go to Statements (1974) … oft-quoted, rarely read. It may surprise you.
15. Bryant-Graph-Based Algorithms for Boolean Function Manipulation (1986) … - introducing ROBDDs and kickstarting a revolution in formal ASIC verification in the process.
16. Donoghue et al.-Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding (2016) … a great example of good theory making for an elegant, practical algorithm.
17. Braun et al.-Simple and Efficient Construction of Static Single Assignment Form (2013) … There are many SSA construction algorithms; this is the slickest one I know.
18. Lamport, Palais-On the Glitch Phenomenon (1976) … arbitration is hard. Read Lamport's notes on it too!
19. Curtsinger, Berger-Stabilizer: Statistically sound performance evaluation (2013) … on how the ubiquity of address-indexed caches distorts program performance measurements, and what to do about it.
20. Tomasulo-An efficient algorihm for exploiting multiple arithmetic units (1967) … to my knowledged, the first Out of Order execution implementation that actually shipped - and applied to a small enough problem that it's easy to understand.
21. Wilson, Johnstone, Neely, Boles - Dynamic storage allocation: A survey and critical review (1995) … Knuth got this one wrong.
22. Meyer, Tischer-GLICBAWLS (2001) … Two Aussies make a dirty joke for an IOCCC entry, accidentally develop a fairly competitive lossless image coder in the process. It happens.
23. Hutton et al.-Improving FPGA Performance and Area Using an Adaptive Logic Module (2004) … Mainly geekery for me; feel free to skip this one if you're not interested in FPGA arch, I just thought it was really cool when I first saw it! (2010 or so)
24. O'Neill-PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation (2014) … Introduces a new, pretty cool RNG and makes for a great introduction to the topic in general.
25. Cook, Podelski, Rybalchenko-Termination Proofs for Systems Code … The Halting Problem: SOLVED!* *for a limited but very practically relevant class of programs; e.g. device drivers.
26. O'Neill - The Genuine Sieve of Eratosthenes (2009) … The standard example implementation as a pure functional program is not, in fact, the same algorithm, and it's very instructive to see how it fails.
27. Qureshi, Jaleel et al. - Adaptive Insertion Policies for High Performance Caching (2007) … this is a HW paper, but the design principles here have been a great inspiration for me in designing adaptive algs in SW.
28. Thompson-Reflections on Trusting Trust (1984 Turing Award lecture) … a classic. If you haven't read it, do so!
29. Dijkstra, Lamport et. al-On-the-fly Garbage Collection: an Exercise in Cooperation (1978) … introducing tri-color marking. No matter where you stand on GC, this is well worth reading.
30. Lamport-Multiple Byte Processing with Full-Word Instructions (1975) … I thought I wouldn't need to do this anymore when we got byte-wise SIMD instrs on CPUs, and then CUDA came along and it was suddenly profitable on GPUs.
31. Bientinesi, van de Geijn-Formal Correctness and Stability of Dense Linear Algebra Algorithms (2005) … Basically an algorithm(!) for deriving dense LA algorithms. Yields direct+blocked variants, correctness proof, stability analysis.

Ethics and Computer Science

Rogaway-The Moral Character of Cryptographic Work (2015) Ceglowski-Haunted By Data (2015)