From the comments on my last post:
scott would you be so kind, if you have some spare time, to post a list of textbooks that you’ve read in math and cs?
Now this is the kind of blog topic I like: zero expenditure of emotional energy required; lends itself to snarky one-liners. So here’s a list of math and CS books that I’ve read and you should too. Pitifully incomplete, but enough to get you started.
- Computational Complexity, by Christos Papadimitriou
The Iliad of complexity. An epic poem to read and reread until you can quote it by section number, until the pages fall out of the spine. Christos is not a textbook writer but a bard — and the only problem with his tale is that it ends around the late 1980’s. Christos, if you’re reading this: we want an Odyssey!
- Gems of Theoretical Computer Science, by Uwe Schöning and Randall Pruim
The proofs are terse, but I love the division into short, digestible “gems.” Keep this one on your night table or by the toilet. (But not until you’ve mastered Papadimitriou and are ready to wield BP operators like a Fortnow.)
- Computational Complexity: A Modern Approach, by Sanjeev Arora
The newest entrant in the arena. Best of all is that the current draft is free and online. I love Sanjeev’s use of “lowerbound” as one word.
- Lecture notes by Luca Trevisan, Umesh Vazirani, John Preskill, …
I don’t know if these count as textbooks, but read them anyway.
- Quantum Computation and Quantum Information, by “Mike & Ike” (Michael Nielsen and Isaac Chuang)
The best quantum computing book. I open it to the section on fidelity and trace distance pretty much every time I write a paper. (I’ve heard the other sections are excellent too.)
- Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan
Chernoff bounds, random walks, second eigenvalues, PCP’s … a 1-1/e fraction of what you need to know about randomness.
- Computers and Intractability: A Guide to the Theory of NP-Completeness, by Michael Garey and David Johnson
Changed my life when I read it at fifteen. Since then it’s sat on my shelf, but I’d take it down if I actually had to prove something NP-complete.
- An Introduction to Computational Learning Theory, by Michael Kearns and Umesh Vazirani
Since this book was co-authored by my advisor, I’ll refrain from saying anything about it except that it’s excellent. (And short.)
- Artificial Intelligence: A Modern Introduction, by Stuart Russell and Peter Norvig
Almost (but not quite) made me go into AI. My favorite chapter is the last one, which carefully demolishes the arguments of John Searle and the other confuseniks.
- Complexity and Real Computation, by Lenore Blum, Felix Cucker, Michael Shub, and Steve Smale
Decidability of the Mandelbrot set? P versus NP over the complex numbers? I may be a Boolean chauvinist, but I knows an elegant theory when I sees one.
- The Art of Computer Programming, by Donald Knuth
Three-volume set looks mighty impressive on a shelf, but beware of MMIX and constant factors.
- Set Theory and the Continuum Hypothesis, by Paul Cohen
The book that gave me the illusion of understanding logic. Short and hard. Prerequisites: None.
- Topology: A First Course, by James Munkres
What every math book should be.
- The Book of Numbers, by John Conway and Richard Guy
Since this is a popular book, obviously I couldn’t have learned anything new from it, but it was nice to “refresh my memory” about octonions, Heegner numbers, and why eπ sqrt(163) is within 0.00000000000075 of an integer.
- The Road to Reality: A Complete Guide to the Laws of the Universe, by Roger Penrose
Preface: “Even if you hated fractions in elementary school, have no fear! I’ve tried to make this book accessible to you as well.”
Chapter 2: “Consider a Lie algebra of sheaves over the holomorphic fibre bundle PZL(Zn,5)…” (Not really, but close.)
I struggled through Penrose’s masterpiece, but by the end, I felt like I’d come as close as I ever had (and possibly ever will) to understanding “post-1920’s” particle physics and the math underlying it. If you’re willing to invest the effort, you’ll find The Road to Reality so excellent that it “cancels out” Shadows of the Mind, like an electron annihilating its positronic companion.