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:

36 Answers 36

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.

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.

  • @turkistany, looks like you posted as I was writing. ;) I'll add some of my thoughts to your post! – Daniel Apon Nov 22 '10 at 16:24
  • 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


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.

  • 6
    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

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)

  • 7
    "An Introduction to the Analysis of Algorithms" by Sedgewick and Flajolet is great. – Jay Dec 5 '10 at 8:34
  • Daniel Spielman uses the book by Kleinberg and Tardos in his "Design and Analysis of Algorithms" course. I took it, and really loved the book. I found it much more approachable than CLRS. – Alex Reinking Jan 11 '15 at 21:08

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.

  • 7
    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
  • 4
    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
  • 2
    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


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:

  • 1
    If I may add a link to something I myself collected (from many different sources including some of the above), here is a cheat sheet of common inequalities: lkozma.net/inequalities_cheat_sheet – László Kozma Dec 9 '13 at 16:31
  • 1
    Hardy, Littlewood, Polya, "Inequalities", a gem from the 1930s(?) – kodlu Jul 15 '15 at 14:19

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.

  • 4
    TAOCP is still relevant and Vol. 4A has just been released. – dbasnett Apr 3 '11 at 14:10

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.

  • 3
    This book was suggested in another topic (I think by Suresh). I found it excellent. Thanks to Aaron for mentioning it here. – M.S. Dousti Nov 22 '10 at 17:01

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.


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:

  • 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. – M.S. 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. – M.S. Dousti Nov 24 '10 at 8:30
  • @Sadeq, I'm inclined to not start an independent question about it, because it would amount to little more than "Help, what is rewinding?" :) The problematic part is that rewinding wasn't in the textbook used in the crypto course that I took (i.e. Katz/Lindell), so I've never seen an introduction to the concept. I'm aware it shows up regularly in crypto literature, but as someone not actively involved in crypto research, I doubt I'll be reading enough papers to gain a solid understanding of rewinding just by encountering it enough. Maybe I could ask a question about rewinding's origins... – Daniel Apon Nov 30 '10 at 15:46
  • 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

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.


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

More advanced texts.

Program Verification

  • 1
    Some of the books (Manna and Apt et al.) are fairly dated (Manna is from 1977 and Apt et al from 1991), the field of logic based program verification has seen major progress in the last decade. Alas, there is no up-to-date text available. – Martin Berger Jul 18 '15 at 15:53
  • @MartinBerger Any hints as to where this major progress might be learned about, if it is not in any recent textbooks? – Mitch Oct 10 '17 at 16:20
  • @Mitch I'm afraid that has not been written up in textbooks as yet. Maybe look at some of the literature about interactive tools like Isabelle/HOL and Coq. Also look at recent automatic verification tools like Facebook's "infer" and the theory behind it. – Martin Berger Oct 11 '17 at 23:29
  • Huth&Ryan is very beginner-friendly. For someone who isn't very familiar with all the rigorous math in CS it's a good start. It is the first book I read about the formal side of CS and got me hooked ever since! It's also the first textbook that I actually finished all the readings. – RexYuan Mar 6 at 17:34

Quantum Computing

Two other excellent introductory books on the subject are:


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.

Information Theory

Information Theory, Inference, and Learning Algorithms by David MacKay

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

  • The title is "What Books Should Everyone Read?", so the recommendation should be selective. Anyone can find a big list of books on "information theory" from Amazon/library, but if you only have 2-3 choices, what will they be? You should only recommend books or articles that you have read quite carefully and narrow down to your absolute favorites! – Dai Le Nov 29 '10 at 14:32
  • 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. – M.S. 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
  • @Dai: You are right. But, since I'm not an expert in "info theory," I cannot trim the list myself. I can: 1) delete the list I added altogether (leaving the original list), or 2) Add a notice in the text to draw an expert's attention. What do you suggest? – M.S. Dousti Nov 30 '10 at 13:23
  • @Sadeq: I don't work on information theory either, otherwise I would help to trim the list. I know that the book "Thomas M. Cover, Joy A. Thomas. Elements of information theory" is recommended by many including Lance Fortnow. But I'm not sure whether everyone should read it or not. I think we should respect the original poster since the book might be his most favorite. So deleting the whole list is a good option. I really apologize for being too straightforward. Also could you ask people to explain why they suggest their books? – Dai Le Nov 30 '10 at 14:05

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


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.

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".

  • Another one, great for Boolean Fourier analysis (as the title suggests) and covering both the basics, more advanced topics and (many) applications, is Analysis of Boolean Functions, by Ryan O'Donnell (2014). It is available online freely here as well. – Clement C. Dec 26 '14 at 13:07

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.


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.


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

  • How about A Mathematical Introduction to Logic by Herbert Enderton? – RexYuan Mar 6 at 17:37

Logic/Proof Writing:

  1. How to Prove It: A Structured Approach by Daniel J. Velleman
  • 3
    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
  • 2
    Polya's "How to Solve It" (HTSI) addresses a different subject than Velleman's book. Polya is a sort of rumination on how to find solutions to hard problems, whereas Velleman is a textbook on how to formalize solutions using the conventions and language of mathematics. HTSI does have information about proofs, but it's presented in a sort of "glossary" form with no structure, whereas Velleman presents you with a systematic curriculum with exercises. Both are worth reading, but one does not replace the other. – Nate C-K Apr 5 '16 at 15:59

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:

  • What do you think of Rosen's book, or the Dover reprints? – Mark C Mar 5 '11 at 20:44
  • @Mark: They're good too. Why not edit the post, and add those books as well? – M.S. Dousti Mar 6 '11 at 3:05


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

Berge C. Hypergraphs: combinatorics of finite sets.

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

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

  • 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

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:

  • In this area, I would recommend this extremely readable book: Synthesis and Optimization of Digital Circuits by Giovanni De Micheli – Chan Li Dec 13 '10 at 18:56

protected by Kaveh May 10 '13 at 6:52

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

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.