What Books Should Everyone Read?

Computational Complexity:

If you are looking for recent complexity textbooks. The following two are must have.

The majority of the content between these two books is comparable. However, some key differences exist: Goldreich devotes more space to exploring the conceptual and philosophical basis of complexity theory, whereas Arora/Barak covers a wider selection of topics, including concrete models of complexity, quantum computation, and circuit lower bounds that are mostly absent from the former.

Another option, an older but timeless textbook in complexity is:

• Computational Complexity by Christos Papadimitriou

Papadimitriou's book is notable for chapters covering first-order logic as well as the classes SNP, MaxSNP0, and APX (the theoretical foundations of hardness of approximation), which are missing from the more modern texts.

Another (comparatively) old, but quite notable classic is:

• Introduction to the Theory of Computation by Michael Sipser

This is one of the few/first textbooks that explicitly includes "Proof Idea:" between "Theorem:" and "Proof:", and is one of the best-written mathematical textbooks on any topic. On the other hand, it is only an intro to complexity, devoting only one 50-page chapter to "advanced topics" (including approximation, probabilistic algorithms, IP=PSPACE, and crypto). As a first book on complexity, or as an example of truly excellent writing, this book is great.

• The Nature of Computation by Cristopher Moore and Stephan Mertens

Scott Aaronson writes that this book has "the fun of a popular book with the intellectual heft of a textbook." It tells stories and gives lots of entertaining examples and references (Game of Life, and lots of other examples for Turing-complete machines). It doesn't go too deep into complexity theory but has great breadth. Especially of note are its connections to statistical physics.

Design & Analysis of Algorithms:

Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms.

R. Motwani, P. Raghavan. Randomized algorithms.

I found this book suggested by Ryan Williams on MathOverflow: Algorithm Design by Kleinberg & Tardos.

Another excellent book is Introduction to Algorithms: A Creative Approach by Udi Manber. This book is not a catalog of algorithms; rather, it tries to provide the reader with intuition to "recognize mathematical structure in abstract problems." (quoted from a review)

Type Systems and Programming Language Semantics:

Benjamin Pierce's Types and Programming Languages and the follow up volume Advanced Topics in Types and Programming Languages. They provide a solid yet comprehensible overview of the role of type theory in programming language design, along with using operational semantics to express programming language semantics.

Inequalities:

Another valuable book for anyone in computer science who ever wants to bound any quantity (so, everyone!) is: The Cauchy-Schwarz Master Class: An Introduction to the Art of Mathematical Inequalities by Michael Steele.

An encyclopedic book on the topic is A Dictionary of Inequalities. While this is not a book for reading cover-to-cover, it is good to have it at your disposal. See also the supplement of the book.

Moreover, Wikipedia has an excellent list of inequalities.

For specific topics, you may consult:

Interesting. No one mentioned volumes of The Art of Computer Programming by Donald E. Knuth. A very detailed treatment of topics with very good exercises.

I found gems like 'resorvoir sampling' in this book just to mention one example.

Randomized Algorithms:

Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal.

Great book for explaining the basics of randomized algorithms. The examples and proofs are explained very clearly, and are easy to follow. Also, the exercises are very fun to do.

(answered by Marcos Villagra)

Analysis of Randomized Algorithms:

Anyone working in algorithms should have Concentration of Measure for the Analysis of Randomized Algorithms, which is also available for download in PDF format here.

As Sylvain Peyronnet already mentioned, logic is an important part of theoretical computer science. However, it is not enough to learn logic from textbooks tailored for pure mathematicians. In other words, it's also important to learn logic from a more "computer science" perspective.

Finite Model Theory

We want to learn techniques that deal with finite structures. It is well-known that many traditional tools from model theory, e.g., compactness and Löwenheim-Skolem theorem, are not applicable to finite models. This leads us to the study of Finite Model Theory. For this area, I recommend the following excellent books:

• Leonid Libkin, Elements of Finite Model Theory. (textbook)
• Grädel et al., Finite Model Theory and Its Applications. (survey articles and applications)

A sub-area of finite model theory is descriptive complexity, where we want to characterizes complexity classes by the type of logic needed to define the languages. The definitive reference for descriptive complexity is:

• Neil Immerman, Descriptive Complexity.

Proof Complexity

Another important area of logic in computer science is Proof Complexity, a study of three way relationship among complexity classes, weak logical systems, and propositional proof system. The following two related aspects are considered: (i) the complexity of of proofs of propositional formulas, and (ii) the study of weak theories of arithmetic, called bounded arithmetic.

Aspect (i) has to do with the following question: "Is there a propositional proof system in which every tautology has a proof of size polynomial in the size of the tautology?"

Aspect (ii) studies logical systems which use restricted reasoning based on concepts from computational complexity. In other words, we assign with each complexity class C a logical theory VC, where the provably total functions in VC are exactly the functions in the complexity class C. One recent development is a new research program called "bounded reverse mathematic" proposed by Stephen Cook and Phuong Nguyen, where the goal is to classify theorems (of interest in computer science) based on the (minimal) computational complexity of concepts needed to prove them.

Aspects (i) and (ii) are closely related by the notion of propositional translation proposed in Cook's 1975 paper, which introduced the equation theory PV for polytime functions and showed how theorems in PV can be translated into families of tautologies which have polynomial length proofs in the extended Frege proof system.

For excellent surveys on proof complexity, I recommend the following two books:

The book by Cook and Nguyen is essentially self-contained, and all the necessary logic background is given in Chapters 2 and 3. Chapter 9 is particularly interesting since the authors introduced an extremely easy method to define your own theory for any complexity classes within P. In this method, we only need to add one additional axiom to a base theory V0, where the axiom simply states the existence of a solution to a complete problem of the complexity class. Pretty amazing!

The book by Krajíček is a bit more challenging since he assumed the readers are already familiar with mathematical logic and model theory (or willing enough to learn the background needed along the way). But you will learn a lot from reading and understanding this book.

Cryptography:

The two-volume book Foundations of Cryptography by Oded Goldreich (Volume 1: Basic Tools and Volume 2: Basic Applications) is an excellent book on the subject. (Early drafts available from author's homepage.) A shortened version of this book is also available.

Another excellent book is Introduction to Modern Cryptography: Principles and Protocols by Katz & Lindell.

A Graduate Course in Applied Cryptography is a work-in-progress book by Boneh and Shoup.

For those interested in mathematical backgrounds of cryptography, An Introduction to Mathematical Cryptography by Hoffstein et al. is the natural choice.

Other excellent books are:

Specific Topics:

Functional Programming

• Purely Functional Data Structures by Chris Okasaki. Most books on data structures assume an imperative language such as C or C++. However, data structures for these languages do not always translate well to functional languages. This book is one of the best expositions on implementing data structures & algorithms in a functional language.
• Functional Programming: Practice and Theory by Bruce J. Maclennan. Despite its name, this book is more theory-oriented than practice-oriented. Those who read this book will have a much better view of the subject than those who learn it by ad-hoc programming.
• Pearls of Functional Algorithm Design by Richard Bird. A brand-new exposition on the subject, which takes the problem-solution approach, and shows the beauty of the field by exhibiting attractive ideas in the design of functional algorithms.
• Certified Programming with Dependent Types by Adam Chlipala. It's one of the best resources in learning Coq, and focuses in particular on how to automating program certification and theorem proving using logic/rule-based systems. Examples are extensive and easy-to-follow.

Approximation Algorithms

The book Approximation Algorithms by Vazirani is the best book on the subject. Another book is Approximation Algorithms for NP-Hard Problems by Hochbaum.

Here are comparisons by two reviewers:

I have been using Dorit Hochbaum's book on approximation algorithms for NP-Hard problems as a guideline for my work. Hochbaum's book is, without a doubt, terrific. However, the survey format compromised a smooth flow in favor of bringing together the best people in the field. Vazirani's book corrects this by being so smooth and elegant from start to finish. Excellent problem sets, excellent hints for most problems, and there is a section at the end of the book devoted to open problems, which is a really cool feature.

I have been looking for books related to solving NP-complete and NP-hard problems approximately. There is another book by Hochbaum and I have that too. Unfortunately, that book is more of a research oriented book as it is written by several researchers. It's like reading several research papers within two hard covers. This means that one needs to have a sort of intermediate level of experience with approximation algorithms.

A recent book is The design of approximation algorithms by Williamson and Shmoys.

Combinatorics

Introductory books. Any of the following books can serve as an excellent introduction to the subject:

More advanced texts.

• Enumerative Combinatorics, Volume 1 & Volume 2 by Stanley. It's simply a masterpiece on enumerative combinatorics; very challenging, very deep.
• Combinatorial Algorithms: Generation, Enumeration, and Search by Kreher & Stinson. More suited to computer science applications of combinatorics.
• Additive Combinatorics by Terence Tao and Van H. Vu. A very useful reference when facing a combinatorial problem related to number theory.

Distributed algorithms

Distributed Algorithms by Nancy Lynch This is a classic text written by a pioneer of distributed computing;

Introduction to Distributed Algorithms by Gerard Tel Very good introduction, also suitable for undergraduate level courses; focused on the message-passing model

Distributed Computing: Fundamentals, Simulations, and Advanced Topics by Hagit Attiya and Jennifer Welch This contains advanced materials, suitable for PhD level courses; both message-passing and shared-memory models are discussed

Design and Analysis of Distributed Algorithms By Nicola Santoro A relatively recent book, may be used both at the undergraduate and PhD level; materials are presented with an emphasis on protocol design

Combinatorics

I want to cite Analytic Combinatorics, by Philippe Flajolet and Robert Sedgewick. It provides a strong mathematical background for enumeration and analysis of algorithms. I want also to pay tribute to Philippe Flajolet, who died two days ago and was a great mathematician and computer scientist.

Quantum Computing

• Quantum Computation and Quantum Information by Nielsen and Chuang, is a great reference book, ideal for those who want to research in the field. However, for starters, it is hard to learn from, and it's definitely not for self learners. Since the book lacks worked examples, I suggest the following book:

  • Problems & Solutions in Quantum Computing & Quantum Information by Steeb & Hardy. This book includes a lot of examples, but it is not still for the absolute beginner. For starters, the following book is suggested:

    • Approaching Quantum Computing by Marinescu & Marinescu. While elementary and easy to learn, some people find it "filled with errors". In this regard, the book's errata comes handy.

• Quantum Computing Since Democritus by Scott Aaronson. A tour-de-force of much more than quantum computing, with relationships to physics, philosophy, etc.

Two other excellent introductory books on the subject are:

Communication Complexity:

This is a classic and a very well written book. Although a little old by now, still the best introductory book to the field. Also, the exercises are extremely fun, and are given exactly after explaining the concepts so you can fix what you just learned.

The part of randomized communication complexity should be complemented with parts of the first book.

Communication Complexity and Parallel Computing by Juraj Hromkovič.

Very complete, although sometimes a little bit hard to read. The intuitive explanations are very clear, and very nice exercises. In the second part it presents the connections to parallel computing.

Combinatorics

generatingfunctionology, by Herbert S. Wilf, is an excellent introduction to the theory of generating functions, written in a smooth way and packed with exercises. If he writes all his books like that, I can't wait to get started on another one.

Enumerative Combinatorics by Richard Stanley is a great reference (advanced).

Combinatorics: topics, techniques, algorithms by Peter Cameron and Invitation to Discrete Mathematics by Matousek and Nesetril are fine introductions to combinatorics.

Applied Combinatorics by Roberts and Tesman is an encyclopaediac reference on applied combinatorics.

Optimization

I liked Paul Nahin's When Least is Best.

Essentially a cute history of optimization through problems and personalities. There is a nice review on pages 32-36 in one of Bill Gasarch's columns.

Nahin has written a lot of other books in a similar vein (examining imaginary numbers, Euler's equation eiπ=−1, and other things), but this is perhaps the most computer science oriented.

• The books by Matousek & Chazelle on Discrepancy are excellent.

  Almost all the books by Matousek, in fact, are worth reading to some extent.

• Douglas West books on Graph Theory ([1] and [2]) are good.

• Alon & Spencer is also excellent.

• Pach & Agarwal is good for discrete geometry, as is the Sharir & Agarwal if you are into DS sequences.

• Brass, Moser, and Pach book on open problems in discrete geometry is also very good.

• The Vanderbei book on LP is very good.

• Schrijver's books ([1] and [2]) are amazing.

Computational Algebra

As Shiva said in this answer, literatures in this field are scattered all over the place, without common terminologies. One can find useful references by searching "symbolic computation", "algebraic complexity theory", "computer algebra" or "computational algebra". As suggested in the answers to this question,

• Modern Computer Algebra by Joachim von zur Gathen and Jürgen Gerhard.
• Algebraic Complexity Theory by Peter Bürgisser, Michael Clausen, Mohammad A. Shokrollahi and T. Lickteig.
• Algorithmic Algebra by Bhubaneswar Mishra.
• A Computational Introduction to Number Theory and Algebra by Victor Shoup.

Computational Analysis

An interesting field also, which deals with computations in real functions. Also known as "computable analysis" or "computable calculus".

Number Theory

I found several books frequently cited in many papers. They are excellent on the subject, but some of them are quite old. Here's a list of what I recall:

• An Introduction to the Theory of Numbers by Hardy et al. Hardy is a renown British mathematician. He was the mentor of the Indian mathematician Ramanujan. His contribution to the field of number theory is quite amazing.
• An Introduction to the Theory of Numbers by Niven, Zuckerman, Montgomery. Another classical introduction to the field.
• Solved and Unsolved Problems in Number Theory by Shanks. This is the book for those who seek yet-to-be-proven conjectures in the field.
• Riemann's Zeta Function by Edwards. An important part of the modern number theory, as well as several probabilistic algorithms for number-theoretic tasks are founded based on the (Extended) Riemann Hypothesis, as described in this book.

Graph Theory

For introduction to graph theory: Introduction to Graph Theory by West

More about graph theory: Graph Theory by Bondy and Murty

The comprehensive book which contains new developments as well as old classic results in graph theory :

Graph theory : Reinhard Diestel.

For graphs on surfaces with combinatorial approach:

Graphs On Surfaces

And for digraphs:

Digraphs: Theory, Algorithms and Applications

Proof Theory

Troelstra and Schwichtenberg's book Basic Proof Theory is the de facto text on the topic now.

Girard, Taylor & LaFont's Proofs and Types is a shorter book on the subject, and a version of it is available for download at http://www.paultaylor.eu/stable/Proofs%2BTypes.html