Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

[Timeline]


This question has the same spirit of what papers should everyone read and what videos should everybody watch. It asks for remarkable books in different areas of theoretical computer science.

The books can be math-oriented, yet you may find it great for a computer scientist. Examples:

  • Probability
  • Inequalities
  • Logic
  • Graph Theory
  • Combinatorics
  • Design & Analysis of Algorithm
  • Theory of Computation / Computational Complexity Theory

Please devote each answer to books of the same subject (e.g. books on combinatorics).

Note: The title might be misleading. Here's a clarification: Let X and Y be two fields in computer science. There are books that everyone

  • in field X should read.
  • in field Y should read.
  • in both fields should read.

This question seeks all 3 cases. In other words, it is NOT specific to the latter case.

Edit: As suggested by Dai Le, please highlight the reason(s) you like the book as well.


Related topics:

share|improve this question
add comment

34 Answers

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:

Papadimitriou's book is notable for chapters covering first-order logic as well as the classes SNP, MaxSNP$_0$, 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:

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.

share|improve this answer
2  
As an aside for those interested in how these books compare to one another, I can also offer this book review of Arora/Barak and Goldreich that I recently wrote for the SIGACT book review column. –  Daniel Apon Nov 22 '10 at 16:38
1  
see also Lance Fortnow's list of his favorite Computational Complexity books on Amazon: amzn.com/l/22R1UX0Y9YRT2 –  Alessandro Cosentino Nov 29 '10 at 23:34
4  
The only comment on Sipser's book is that he sometimes uses nonstandard names when covering computability theory. For example, he uses "recognizable" instead of "semi-decidable". But I guess since the textbook is so widely used, it might just become as standard by now. –  Dai Le Nov 30 '10 at 13:48
3  
Actually, that's an excellent comment in general, @Dai Le. I can think of similar differences between Goldreich and Arora/Barak. For instance, Goldreich uses the name $PC$ and Arora/Barak uses the name $FNP$, even though they're both talking about the same concept. –  Daniel Apon Nov 30 '10 at 16:03
show 4 more comments

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)

share|improve this answer
7  
"An Introduction to the Analysis of Algorithms" by Sedgewick and Flajolet is great. –  Jay Dec 5 '10 at 8:34
add comment

NP-Completeness:

Well, I guess Garey and Johnson's Computers and Intractability: A Guide to the Theory of NP-Completeness will be found among the top books in this list.

share|improve this answer
3  
Still the best introduction to complexity theory after 30 years. –  Emil Nov 23 '10 at 22:22
1  
after decades this book is still the most complete list of NP complete problems in one place, apparently, almost an encyclopedia, and many cs researchers seem to share this point of view –  vzn Jan 20 '12 at 4:25
1  
recommend this be added to FAQ for a general question, "is my problem X NP complete?" with answer, "1st check this book 1st and then get back to us" –  vzn Jan 20 '12 at 4:29
add comment

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:

share|improve this answer
show 1 more comment

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.

share|improve this answer
6  
For a more mathematical perspective on type theory, "Lectures on the Curry-Howard Isomorphism" by Sorensen and Urzyczyn is a great start, providing a good overview of typed lambda-calculi all the way up to the Calculus of Constructions, and beyond. –  Dominic Mulligan Nov 25 '10 at 19:21
2  
I would suggest John Mitchell's Foundations for Programming Languages on this topic. As in previous comment, it's more mathematically matured. –  Artem Pelenitsyn Dec 14 '10 at 19:08
1  
Upvote for TAPL. FYI Benjamin Pierce is one of the authors of a new book "Software Foundation" that uses Coq. –  kunjan kshetri Oct 24 '11 at 2:52
add comment

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.

share|improve this answer
2  
This book was suggested in another topic (I think by Suresh). I found it excellent. Thanks to Aaron for mentioning it here. –  Sadeq Dousti Nov 22 '10 at 17:01
add comment

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.

share|improve this answer
4  
TAOCP is still relevant and Vol. 4A has just been released. –  dbasnett Apr 3 '11 at 14:10
add comment

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:

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:

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 $\mathsf{PV}$ for polytime functions and showed how theorems in $\mathsf{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 $\mathsf{P}$. In this method, we only need to add one additional axiom to a base theory $V_0$, 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.

share|improve this answer
add comment

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.

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:

share|improve this answer
2  
Since their introduction in 1993, random oracles have been extensively used in literature; specially in signature schemes. I don't know a book that covers this area appropriately. Suggestions are welcome. –  Sadeq Dousti Nov 22 '10 at 20:24
1  
A book on random oracles would be a huge help. I don't do work in crypto, but I've read Katz/Lindell front-to-back. The transition from textbook to crypto literature was rough because of this specific reason. Also, @Sadeq, out of curiosity: Do any of the books you've read have good coverage of rewinding? –  Daniel Apon Nov 23 '10 at 19:22
1  
@Daniel: Martin Gagné's thesis "A Study of the Random Oracle Model" (UC Davis, 2008) is a relatively good reference on random oracles (though still far from being complete). Regarding the "rewinding" question: I don't know a book about it, yet I think I've completely grasped it. Could you please elaborate what part seems problematic to you? You can even ask it on a separate topic. –  Sadeq Dousti Nov 24 '10 at 8:30
3  
@Daniel: The introduction of my book con concurrent zero-knowledge explains rewinding and the difficulties induced by it in the context of protocol composition. Other sources are: (1) Oded Goldreich, Hugo Krawczyk: On the Composition of Zero-Knowledge Proof Systems. SIAM J. Comput. 25(1): 169-192 (1996) and (2) Cynthia Dwork, Moni Naor, Amit Sahai: Concurrent zero-knowledge. J. ACM 51(6): 851-898 (2004). –  Alon Rosen Dec 22 '10 at 7:56
show 4 more comments

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.

and

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.

share|improve this answer
show 1 more comment

Combinatorics

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

More advanced texts.

share|improve this answer
add comment

Information Theory

Information Theory, Inference, and Learning Algorithms by David MacKay

Other famous textbooks on information theory can be found on Wikipedia.

share|improve this answer
1  
@Dai Le: You are right. I think the list should be narrowed down. (I'm personally responsible for bloating the list!) However, this is a community wiki post. I added a long list suggesting what candidates are. Please trim the list to include only the most appropriate books. –  Sadeq Dousti Nov 29 '10 at 15:20
1  
@Sadeq: I'm afraid it's rarely the case that one person will trim down another person's list. As long as the post is still in the current form, it's completely worthless with respect to the purpose of post. –  Dai Le Nov 30 '10 at 12:24
show 4 more comments

Quantum Computing

Two other excellent introductory books on the subject are:

share|improve this answer
add comment

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.
share|improve this answer
add comment

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

share|improve this answer
add comment

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 $e^{i\pi} = -1$, and other things), but this is perhaps the most computer science oriented.

share|improve this answer
add comment

Communication Complexity:


Communication Complexity by Eyal Kushilevitz and Noam Nisan.

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.

share|improve this answer
add comment

Logic:

This is a verbatim of my answer to this question.

Knowledge of basic mathematical logic is, in my opinion, a plus. You can have a look at the two books by Cori and Lascar.

Mathematical Logic: A Course with Exercises Part I

Mathematical Logic: A Course with Exercises Part II

share|improve this answer
add comment

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, which died two days ago and was a great mathematician and computer scientist.

share|improve this answer
add comment
share|improve this answer
add comment

Program Verification

share|improve this answer
add comment

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.

share|improve this answer
add comment

Logic/Proof Writing:

  1. How to Prove It: A Structured Approach by Daniel J. Velleman
share|improve this answer
2  
How does this compare to "How to solve it" by G. Polya? I think I read the advice that Polya is the original and much better, but I'm not sure and cannot refind it on the interwebs ;) –  DaveBall aka user750378 Sep 12 '11 at 22:18
add comment

Hypergraphs

There are not many books devoted exclusively to hypergraphs. One such book is

Berge C. Hypergraphs: combinatorics of finite sets.

share|improve this answer
add comment

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,

Computational Analysis

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

share|improve this answer
add comment

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

share|improve this answer
add comment

VLSI Design

I'm not into hardware. However, since the FAQ includes VLSI as one of the sub-fields of TCS, I asked an expert about famous books in the VLSI design. Here they are:

share|improve this answer
show 1 more comment

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:

share|improve this answer
show 2 more comments

Graph Theory

Introduction to Graph Theory by West

Graph Theory by Bondy and Murty

I think these are the best basic books in Graph Theory and everyone should read them.

Graph theory : Reinhard Diestel is a book which presents graph theory in a greater detail.

share|improve this answer
1  
There is also The Theory of Graphs by Claude Berge, one of the founders of graph theory. And Graphs and Algorithms by Michel Minoux and Michel Gondran. –  Lamine May 2 '11 at 9:30
add comment

protected by Kaveh May 10 '13 at 6:52

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.