<h2>Computational Complexity:</h2>

<p>If you are looking for recent complexity textbooks. The following two are must have.</p>

<ul>
<li><p><a href="http://rads.stackoverflow.com/amzn/click/0521424267">Computational Complexity: A Modern Approach</a> by Sanjeev Arora and Boaz Barak (<a href="http://www.cs.princeton.edu/theory/complexity/">Textbook homepage</a>)</p></li>
<li><p><a href="http://rads.stackoverflow.com/amzn/click/052188473X">Computational Complexity: A Conceptual Perspective</a> by Oded Goldreich (<a href="http://www.wisdom.weizmann.ac.il/~oded/cc-book.html">Textbook homepage</a>)</p></li>
</ul>

<p>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.</p>

<p>Another option, an older but timeless textbook in complexity is:</p>

<ul>
<li><a href="http://rads.stackoverflow.com/amzn/click/0201530821">Computational Complexity</a> by Christos Papadimitriou</li>
</ul>

<p>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.</p>

<p>Another (comparatively) old, but quite notable classic is:</p>

<ul>
<li><a href="http://rads.stackoverflow.com/amzn/click/0534950973">Introduction to the Theory of Computation</a> by Michael Sipser</li>
</ul>

<p>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 <em>any</em> 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 <em>great</em>.</p>

<ul>
<li><a href="http://rads.stackoverflow.com/amzn/click/0199233217">The Nature of Computation</a> by Cristopher Moore and Stephan Mertens</li>
</ul>

<p>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.</p>

CC BY-SA 2.5
2010-11-22T16:24:11.933Z
@turkistany, looks like you posted as I was writing. ;) I'll add some of my thoughts to your post!
Daniel Apon
CC BY-SA 2.5
2010-11-22T16:38:46.710Z
As an aside for those interested in how these books compare to one another, I can also offer this [book review](http://www.cs.umd.edu/~gasarch/BLOGPAPERS/compbooks.pdf) of Arora/Barak and Goldreich that I recently wrote for the SIGACT book review column.
Daniel Apon
CC BY-SA 2.5
2010-11-29T23:34:36.050Z
see also Lance Fortnow's list of his favorite Computational Complexity books on Amazon: http://amzn.com/l/22R1UX0Y9YRT2
Alessandro Cosentino
CC BY-SA 2.5
2010-11-30T13:48:38.197Z
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
CC BY-SA 2.5
2010-11-30T16:03:23.287Z
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
CC BY-SA 3.0
2011-12-05T00:59:46.273Z
I've found Sipser far more useful than Papadimitriou for actually teaching complexity theory, ymmv.
Jeff Burdges
CC BY-SA 3.0
2010-11-22T16:17:29.943Z
2015-08-18T20:28:05.493Z
2015-08-18T20:28:05.493Z
Mohammad Al-Turkistany
<h2>NP-Completeness:</h2>
<p>Well, I guess Garey and Johnson's <a href="https://rads.stackoverflow.com/amzn/click/com/0716710455" rel="noreferrer" rel="nofollow noreferrer">Computers and Intractability: A Guide to the Theory of NP-Completeness</a> will be found among the top books in this list.</p>

CC BY-SA 2.5
2010-11-23T22:22:55.610Z
Still the best introduction to complexity theory after 30 years.
Emil
CC BY-SA 3.0
2012-01-20T04:25:48.177Z
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
CC BY-SA 3.0
2012-01-20T04:29:56.517Z
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
CC BY-SA 2.5
2010-11-22T15:41:37.197Z
2010-11-22T18:10:55.640Z
2020-06-17T09:38:08.363Z
Anthony Labarre
<h2>Design &amp; Analysis of Algorithms:</h2>

<p>Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. <a href="http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&amp;tid=8570" rel="noreferrer">Introduction to Algorithms.</a></p>

<p>R. Motwani, P. Raghavan. <a href="http://books.google.com/books?id=QKVY4mDivBEC&amp;lpg=PP1&amp;dq=motwani%20raghavan%20randomized%20algorithms&amp;hl=ru&amp;pg=PP1#v=onepage&amp;q&amp;f=false" rel="noreferrer">Randomized algorithms.</a></p>

<p>I found this book <a href="https://mathoverflow.net/questions/7772/9314#9314">suggested by Ryan Williams</a> on MathOverflow: <a href="http://rads.stackoverflow.com/amzn/click/0321295358" rel="noreferrer">Algorithm Design</a> by <em>Kleinberg &amp; Tardos</em>.</p>

<p>Another excellent book is <a href="http://rads.stackoverflow.com/amzn/click/0201120372" rel="noreferrer">Introduction to Algorithms: A Creative Approach</a> by <em>Udi Manber</em>. 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)</p>

CC BY-SA 3.0
2015-01-11T21:08:43.080Z
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
CC BY-SA 2.5
2010-12-05T08:34:59.243Z
"An Introduction to the Analysis of Algorithms" by Sedgewick and Flajolet is great.
Jay
CC BY-SA 2.5
2010-11-22T18:00:18.943Z
2010-12-01T00:04:04.623Z
2017-04-13T12:57:54.777Z
Nikita Zhiltsov
<h2>General Math for Computer Science:</h2>

<ul>
<li><p><a href="http://rads.stackoverflow.com/amzn/click/0201558025">Concrete Mathematics: A Foundation for Computer Science</a> by Graham, Knuth, and Patashnik.</p></li>
<li><p><a href="http://rads.stackoverflow.com/amzn/click/0691118809">The Princeton Companion to Mathematics</a> by Gowers <em>et al.</em></p></li>
<li><p><a href="http://rads.stackoverflow.com/amzn/click/3540636986">Proofs from THE BOOK</a> by Aigner and Ziegler.</p></li>
</ul>

CC BY-SA 2.5
2010-11-22T20:10:00.560Z
2010-11-23T04:32:04.473Z
2010-11-23T04:32:04.473Z
Sadeq Dousti
<h2>Type Systems and Programming Language Semantics:</h2>

<p>Benjamin Pierce's <a href="http://rads.stackoverflow.com/amzn/click/0262162091">Types and Programming Languages</a> and the follow up volume <a href="http://rads.stackoverflow.com/amzn/click/0262162288">Advanced Topics in Types and Programming Languages</a>. 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.</p>

CC BY-SA 3.0
2011-10-24T02:52:07.930Z
Upvote for TAPL. FYI Benjamin Pierce is one of the authors of a new book "Software Foundation" that uses Coq.
kunjan kshetri
CC BY-SA 4.0
2020-01-04T13:05:45.087Z
Harper's "Practical Foundations for Programming Languages" is an excellent follow up to TaPL
brj
CC BY-SA 4.0
2023-12-26T20:46:37.140Z
Voted useful for TaPL. Software Foundations is also a recommended set of textbooks for programming languages and verification (and it is FREE available online).
Kagura Hitoha
CC BY-SA 2.5
2010-11-25T19:21:59.857Z
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
CC BY-SA 2.5
2010-12-14T19:08:24.973Z
I would suggest John Mitchell's Foundations for Programming Languages on this topic. As in previous comment, it's more mathematically matured.
Artem Pelenitsyn
CC BY-SA 2.5
2010-11-22T15:49:43.197Z
2010-11-22T18:32:32.620Z
2010-11-22T18:32:32.620Z
Dave Clarke
<h2>Inequalities:</h2>
<p>Another valuable book for anyone in computer science who ever wants to bound any quantity (so, everyone!) is:
<a href="https://rads.stackoverflow.com/amzn/click/com/052154677X" rel="noreferrer" rel="nofollow noreferrer">The Cauchy-Schwarz Master Class: An Introduction to the Art of Mathematical Inequalities</a> by Michael Steele.</p>
<p>An encyclopedic book on the topic is <a href="https://rads.stackoverflow.com/amzn/click/com/0582327482" rel="noreferrer" rel="nofollow noreferrer">A Dictionary of Inequalities</a>. While this is not a book for reading cover-to-cover, it is good to have it at your disposal.
See also <a href="http://ajmaa.org/RGMIA/monographs/bullen/Dict-Ineq-Supp-Comb.pdf" rel="noreferrer">the supplement</a> of the book.</p>
<p>Moreover, Wikipedia has an excellent <a href="http://en.wikipedia.org/wiki/List_of_inequalities" rel="noreferrer">list of inequalities</a>.</p>
<p>For specific topics, you may consult:</p>
<ul>
<li><a href="https://rads.stackoverflow.com/amzn/click/com/981428078X" rel="noreferrer" rel="nofollow noreferrer">Probabilistic Inequalities</a></li>
<li><a href="https://rads.stackoverflow.com/amzn/click/com/3540437983" rel="noreferrer" rel="nofollow noreferrer">Matrix Inequalities</a></li>
<li><a href="https://rads.stackoverflow.com/amzn/click/com/0883856042" rel="noreferrer" rel="nofollow noreferrer">Geometric Inequalities</a></li>
<li><a href="http://www.math.upenn.edu/%7Ewilf/AeqB.html" rel="noreferrer">The book &quot;A=B&quot; by Petkovsek, Wilf and Zeilberger</a></li>
</ul>

CC BY-SA 3.0
2013-12-09T16:31:02.533Z
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:
http://www.lkozma.net/inequalities_cheat_sheet/
László Kozma
CC BY-SA 3.0
2015-07-15T14:19:11.090Z
Hardy, Littlewood, Polya, "Inequalities", a gem from the 1930s(?)
kodlu
CC BY-SA 2.5
2010-11-22T17:03:09.920Z
2010-11-23T09:46:54.623Z
2020-06-17T09:38:08.363Z
Aaron Roth
<p>Interesting. 
No one mentioned volumes of <a href="http://www-cs-faculty.stanford.edu/~knuth/taocp.html">The Art of Computer Programming</a> by <a href="http://www-cs-faculty.stanford.edu/~knuth/index.html">Donald E. Knuth</a>. A very detailed treatment of topics with very good exercises. </p>

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

CC BY-SA 2.5
2011-04-03T14:10:53.407Z
TAOCP is still relevant and Vol. 4A has just been released.
dbasnett
CC BY-SA 3.0
2011-01-28T14:41:59.960Z
2013-01-03T18:45:01.813Z
2013-01-03T18:45:01.813Z
Fakrudeen
<h2>Randomized Algorithms:</h2>

<p><a href="http://rads.stackoverflow.com/amzn/click/0521835402">Probability and Computing: Randomized Algorithms and Probabilistic Analysis</a> by Michael Mitzenmacher and Eli Upfal.</p>

<p>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.</p>

<p>(answered by Marcos Villagra)</p>

<p><strong>Analysis of Randomized Algorithms:</strong></p>

<p>Anyone working in algorithms should have <a href="http://rads.stackoverflow.com/amzn/click/0521884276">Concentration of Measure for the Analysis of Randomized Algorithms</a>, which is also available for download in PDF format <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.2561&amp;rep=rep1&amp;type=pdf">here</a>.</p>

CC BY-SA 2.5
2010-11-22T17:01:41.217Z
This book was suggested in another topic (I think by Suresh). I found it excellent. Thanks to Aaron for mentioning it here.
Sadeq Dousti
CC BY-SA 2.5
2010-11-22T16:52:53.897Z
2011-01-27T09:17:58.087Z
2011-01-27T09:17:58.087Z
Aaron Roth
<p>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. </p>

<h2>Finite Model Theory</h2>

<p>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 <em>not</em> applicable to finite models. This leads us to the study of <em><a href="http://en.wikipedia.org/wiki/Finite_model_theory">Finite Model Theory</a></em>. For this area, I recommend the following excellent books:</p>

<blockquote>
  <ul>
  <li>Leonid Libkin, <a href="http://rads.stackoverflow.com/amzn/click/3540212027">Elements of Finite Model Theory</a>. (textbook)</li>
  <li>Grädel et al., <a href="http://rads.stackoverflow.com/amzn/click/3540004289">Finite Model Theory and Its Applications</a>. (survey
  articles and applications)</li>
  </ul>
</blockquote>

<p>A sub-area of finite model theory is <a href="http://en.wikipedia.org/wiki/Descriptive_complexity_theory">descriptive complexity</a>, where we want to characterizes complexity classes by the type of logic needed to define the languages. The definitive reference for descriptive complexity is:</p>

<blockquote>
  <ul>
  <li>Neil Immerman, <a href="http://rads.stackoverflow.com/amzn/click/0387986006">Descriptive Complexity</a>.</li>
  </ul>
</blockquote>

<h2>Proof Complexity</h2>

<p>Another important area of logic in computer science is <a href="http://en.wikipedia.org/wiki/Proof_complexity">Proof Complexity</a>, 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 <em>bounded arithmetic</em>. </p>

<p>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?"</p>

<p>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 <em>provably total</em> 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. </p>

<p>Aspects (i) and (ii) are closely related by the notion of <em>propositional translation</em> proposed in <a href="http://portal.acm.org/citation.cfm?id=803756">Cook's 1975 paper</a>, 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. </p>

<p>For excellent surveys on proof complexity, I recommend the following two books:</p>

<blockquote>
  <ul>
  <li>Stephen Cook and Phuong Nguyen, <a href="http://rads.stackoverflow.com/amzn/click/052151729X">Logical Foundations of Proof Complexity</a>.
  (draft made available <a href="http://www.cs.toronto.edu/~sacook/homepage/book/">here</a>)</li>
  <li>Jan Krajíček, <a href="http://rads.stackoverflow.com/amzn/click/0521452058">Bounded Arithmetic, Propositional Logic and Complexity
  Theory</a>.</li>
  </ul>
</blockquote>

<p>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!</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-30T05:31:59.333Z
2011-01-28T10:35:05.180Z
2011-01-28T10:35:05.180Z
Dai Le
<h2>Cryptography:</h2>
<p>The two-volume book <strong>Foundations of Cryptography</strong> by Oded Goldreich (<a href="https://rads.stackoverflow.com/amzn/click/com/0521791723" rel="nofollow noreferrer" rel="nofollow noreferrer">Volume 1: Basic Tools</a> and <a href="https://rads.stackoverflow.com/amzn/click/com/0521830842" rel="nofollow noreferrer" rel="nofollow noreferrer">Volume 2: Basic Applications</a>) is an excellent book on the subject. (Early drafts available from <a href="http://www.wisdom.weizmann.ac.il/%7Eoded/foc-book.html" rel="nofollow noreferrer">author's homepage</a>.) A <a href="https://rads.stackoverflow.com/amzn/click/com/1933019026" rel="nofollow noreferrer" rel="nofollow noreferrer">shortened version</a> of this book is also available.</p>
<p>Another excellent book is <a href="https://rads.stackoverflow.com/amzn/click/com/1466570261" rel="nofollow noreferrer" rel="nofollow noreferrer">Introduction to Modern Cryptography: Principles and Protocols</a> by Katz &amp; Lindell.</p>
<p><a href="https://toc.cryptobook.us/" rel="nofollow noreferrer">A Graduate Course in Applied Cryptography</a> is a work-in-progress book by Boneh and Shoup.</p>
<p>For those interested in mathematical backgrounds of cryptography, <a href="https://rads.stackoverflow.com/amzn/click/com/0387779930" rel="nofollow noreferrer" rel="nofollow noreferrer">An Introduction to Mathematical Cryptography</a> by Hoffstein <em>et al.</em> is the natural choice.</p>
<p>Other excellent books are:</p>
<ul>
<li><a href="https://rads.stackoverflow.com/amzn/click/com/0849385237" rel="nofollow noreferrer" rel="nofollow noreferrer">Handbook of Applied Cryptography</a> by Menezes <em>et al.</em> (Chapter are <a href="http://www.cacr.math.uwaterloo.ca/hac/" rel="nofollow noreferrer">available online</a>).</li>
<li><a href="https://rads.stackoverflow.com/amzn/click/com/1584885084" rel="nofollow noreferrer" rel="nofollow noreferrer">Cryptography: Theory and Practice</a> by Stinson.</li>
</ul>
<hr />
<p><strong>Specific Topics:</strong></p>
<ul>
<li>Books pertaining to advanced composition of security protocols:</li>
<li><a href="https://rads.stackoverflow.com/amzn/click/com/354020105X" rel="nofollow noreferrer" rel="nofollow noreferrer">Composition of Secure Multi-Party Protocols: A Comprehensive Study</a> by Lindell.</li>
<li><a href="https://rads.stackoverflow.com/amzn/click/com/3642069495" rel="nofollow noreferrer" rel="nofollow noreferrer">Concurrent Zero-Knowledge</a> by Rosen.</li>
<li>Formal proofs in security protocols</li>
<li><a href="https://rads.stackoverflow.com/amzn/click/com/3540681345" rel="nofollow noreferrer" rel="nofollow noreferrer">Formal Correctness of Security Protocols</a> by Bella.</li>
<li><a href="https://rads.stackoverflow.com/amzn/click/com/1107013925" rel="nofollow noreferrer" rel="nofollow noreferrer">Mathematics of Public Key Cryptography</a> by Galbraith</li>
</ul>

CC BY-SA 2.5
2010-11-22T20:24:10.763Z
Since their introduction in 1993, [random oracles](http://en.wikipedia.org/wiki/Random_oracle) 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
CC BY-SA 2.5
2010-11-23T19:22:00.943Z
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
CC BY-SA 2.5
2010-11-24T08:30:00.350Z
@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
CC BY-SA 2.5
2010-11-30T15:46:56.470Z
@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
CC BY-SA 2.5
2010-11-30T15:53:35.603Z
Actually, @Sadeq, your and Alon's answers to [this question](http://cstheory.stackexchange.com/questions/2975/straight-line-simulatability) are kind of the complement of the type of information I'd be interested in knowing more about anyway. I'll check out the papers the two of you linked there and maybe ask a question if I end up with something unanswered. :)
Daniel Apon
CC BY-SA 2.5
2010-11-30T21:20:57.553Z
@Daniel: I'll be glad to help. Don't ever hesitate to ask ;)
Sadeq Dousti
CC BY-SA 2.5
2010-12-22T07:56:10.920Z
@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
CC BY-SA 4.0
2010-11-22T19:07:53.040Z
2020-08-14T19:16:07.337Z
2020-08-14T19:16:07.337Z
Sadeq Dousti
<h2>Combinatorics</h2>

<p>I want to cite <a href="http://algo.inria.fr/flajolet/Publications/book.pdf" rel="noreferrer">Analytic Combinatorics</a>, 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. </p>

CC BY-SA 3.0
2011-03-24T14:49:16.647Z
2017-06-18T20:22:11.870Z
2017-06-18T20:22:11.870Z
Lamine
<h2>Quantum Computing</h2>

<ul>
<li><p><a href="http://rads.stackoverflow.com/amzn/click/0521635039" rel="noreferrer">Quantum Computation and Quantum Information</a> by <em>Nielsen and Chuang</em>, is a great <strong>reference</strong> 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:</p>

<ul>
<li><p><a href="http://rads.stackoverflow.com/amzn/click/9812387900" rel="noreferrer">Problems &amp; Solutions in Quantum Computing &amp; Quantum Information</a> by <em>Steeb &amp; Hardy</em>. This book includes a lot of examples, but it is not still for the absolute beginner. For starters, the following book is suggested:</p>

<ul>
<li><a href="http://rads.stackoverflow.com/amzn/click/013145224X" rel="noreferrer">Approaching Quantum Computing</a> by <em>Marinescu &amp; Marinescu</em>. While elementary and easy to learn, some people find it "filled with errors". In this regard, the <a href="http://www.cs.ucf.edu/~dcm/Errata.pdf" rel="noreferrer">book's errata</a> comes handy.</li>
</ul></li>
</ul></li>
<li><p><a href="http://rads.stackoverflow.com/amzn/click/0521199565" rel="noreferrer">Quantum Computing Since Democritus</a> by <em>Scott Aaronson</em>. A tour-de-force of much more than quantum computing, with relationships to physics, philosophy, etc.</p></li>
</ul>

<p>Two other excellent introductory books on the subject are:</p>

<ul>
<li><a href="http://rads.stackoverflow.com/amzn/click/0521879965" rel="noreferrer">Quantum Computing for Computer Scientists</a> by <em>Yanofsky &amp; Mannucci</em>.</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/019857049X" rel="noreferrer">An Introduction to Quantum Computing</a> by <em>Kaye, Laflamme, and Mosca</em>.</li>
</ul>

CC BY-SA 4.0
2022-04-15T11:07:37.103Z
Another book I think is great is Kitaev's Classical and Quantum Computation.
narip
CC BY-SA 3.0
2010-11-30T22:18:56.513Z
2015-08-18T20:12:23.277Z
2015-08-18T20:12:23.277Z
Sadeq Dousti
<h2>Distributed algorithms</h2>

<p><a href="http://rads.stackoverflow.com/amzn/click/1558603484">Distributed Algorithms</a> by Nancy Lynch
This is a classic text written by a pioneer of distributed computing; </p>

<p><a href="http://rads.stackoverflow.com/amzn/click/0521794838">Introduction to Distributed Algorithms</a> by Gerard Tel
Very good introduction, also suitable for undergraduate level courses; focused on the message-passing model</p>

<p><a href="http://rads.stackoverflow.com/amzn/click/0471453242">Distributed Computing: Fundamentals, Simulations, and Advanced Topics</a> by Hagit Attiya and Jennifer Welch
This contains advanced materials, suitable for PhD level courses; both message-passing and shared-memory models are discussed</p>

<p><a href="http://rads.stackoverflow.com/amzn/click/0471719978">Design and Analysis of Distributed Algorithms</a> 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</p>

CC BY-SA 3.0
2011-04-30T17:55:08.880Z
2012-10-24T19:03:23.530Z
2012-10-24T19:03:23.530Z
Massimo Cafaro
<h2><strong>Program Verification</strong></h2>

<ul>
<li><a href="http://rads.stackoverflow.com/amzn/click/0486432386" rel="noreferrer">Mathematical Theory of
Computation</a> by Zohar Manna</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/026202649X" rel="noreferrer">Principles of Model Checking</a> by
Christel Baier and Joost-Pieter
Katoen </li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0262032708" rel="noreferrer">Model Checking</a> by Edmund
M. Clarke Jr., Orna Grumberg and
Doron A. Peled</li>
<li><a href="http://www.amazon.co.uk/Verification-Sequential-Concurrent-Programs-Computer/dp/184882744X/ref=wl_it_dp_o?ie=UTF8&amp;coliid=I3H4XLBLP0HCNH&amp;colid=360PU4HGT5V1E" rel="noreferrer">Verification of Sequential and Concurrent Programs</a> by Krzysztof R. Apt, Frank S. de Boer  and, Ernst-Rüdiger Olderog</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/052154310X" rel="noreferrer">Logic in Computer Science: Modelling and Reasoning about Systems</a> by M. Huth and M. Ryan</li>
</ul>

CC BY-SA 3.0
2015-07-18T15:53:40.117Z
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
CC BY-SA 3.0
2017-10-10T16:20:13.083Z
@MartinBerger Any hints as to where this major progress might be learned about, if it is not in any recent textbooks?
Mitch
CC BY-SA 3.0
2017-10-11T23:29:39.003Z
@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
CC BY-SA 3.0
2018-03-06T17:34:27.533Z
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
CC BY-SA 3.0
2010-12-13T19:08:13.823Z
2015-07-15T18:13:26.717Z
2015-07-15T18:13:26.717Z
Chan Li
<h2>Information Theory</h2>

<p><a href="http://www.inference.phy.cam.ac.uk/mackay/itila/book.html">Information Theory, Inference, and Learning Algorithms</a> by David MacKay</p>

<p>Other famous textbooks on information theory can be found on <a href="http://en.wikipedia.org/wiki/Information_theory#Textbooks_on_information_theory">Wikipedia</a>.</p>

CC BY-SA 2.5
2010-11-29T14:32:13.740Z
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
CC BY-SA 2.5
2010-11-29T15:20:24.587Z
@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
CC BY-SA 2.5
2010-11-30T12:24:50.113Z
@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
CC BY-SA 2.5
2010-11-30T13:23:44.857Z
@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?
Sadeq Dousti
CC BY-SA 2.5
2010-11-30T14:05:46.693Z
@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
CC BY-SA 2.5
2010-11-30T15:06:25.980Z
@Dai: As you wish! I left a link to Wikipedia, just in case people want to know what other choices are available. I think this is the best compromise. Your idea of asking people to explain why they like the book is brilliant. I'm changing the question to reflect that.
Sadeq Dousti
CC BY-SA 2.5
2010-11-29T10:48:00.523Z
2010-11-30T15:03:38.150Z
2010-11-30T15:03:38.150Z
NPE
<h2>Communication Complexity:</h2>

<p><hr>
<a href="http://rads.stackoverflow.com/amzn/click/052102983X">Communication Complexity</a> by Eyal Kushilevitz and Noam Nisan.</p>

<p>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.</p>

<p>The part of randomized communication complexity should be complemented with parts of the first book.</p>

<hr>

<p><a href="http://books.google.com/books?id=jQbUo-clEGkC&amp;pg=PA131&amp;dq=introduction%20to%20communication%20complexity&amp;hl=es&amp;ei=ExG9TaTLJ4q6vQPns8W1BQ&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CDAQ6AEwAA#v=onepage&amp;q&amp;f=false">Communication Complexity and Parallel Computing</a> by Juraj Hromkovič.</p>

<p>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.</p>

CC BY-SA 3.0
2010-11-29T23:23:38.697Z
2011-05-01T07:59:53.577Z
2011-05-01T07:59:53.577Z
Marcos Villagra
<h2>Optimization</h2>

<p>I liked Paul Nahin's <a href="http://rads.stackoverflow.com/amzn/click/0691070784">When Least is Best.</a></p>

<p>Essentially a cute history of optimization through problems and personalities. There is a nice review on pages 32-36 in one of <a href="http://www.cs.umd.edu/~gasarch/bookrev/41-3.pdf">Bill Gasarch's columns.</a> </p>

<p>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.</p>

CC BY-SA 2.5
2010-11-23T04:14:11.903Z
2010-11-23T08:00:37.563Z
2010-11-23T08:00:37.563Z
Mugizi Rwebangira
<h2>Computational Algebra</h2>

<p>As Shiva said <a href="https://cstheory.stackexchange.com/questions/2270/formal-representation-of-rings-in-computations/2272#2272">in this answer</a>, 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 <a href="https://cstheory.stackexchange.com/q/2270/1800">this question</a>, </p>

<ul>
<li><a href="http://rads.stackoverflow.com/amzn/click/0521826462" rel="noreferrer">Modern Computer Algebra</a> by Joachim von zur Gathen and Jürgen Gerhard.</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/3540605827" rel="noreferrer">Algebraic Complexity Theory</a> by Peter Bürgisser, Michael Clausen, Mohammad A. Shokrollahi and T. Lickteig.</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0387940901" rel="noreferrer">Algorithmic Algebra</a> by Bhubaneswar Mishra.</li>
<li><a href="http://shoup.net/ntb/" rel="noreferrer">A Computational Introduction to Number Theory and Algebra</a> by Victor Shoup.</li>
</ul>

<h2>Computational Analysis</h2>

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

<ul>
<li><a href="http://www.amazon.co.uk/Computable-Analysis-Oliver-Aberth/dp/0070000794" rel="noreferrer">Computable Analysis</a> by Oliver Aberth.</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/3540668179" rel="noreferrer">Computable Analysis: An Introduction</a> by Klaus Weihrauch.</li>
</ul>

CC BY-SA 2.5
2011-02-18T04:35:44.527Z
2011-02-18T04:42:23.913Z
2017-04-13T12:32:28.743Z
Hsien-Chih Chang 張顯之
<h2>Combinatorics</h2>

<p><a href="http://www.math.upenn.edu/~wilf/DownldGF.html" rel="noreferrer">generatingfunctionology</a>, 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.</p>

<p><a href="http://www-math.mit.edu/~rstan/ec/ec1/" rel="noreferrer">Enumerative Combinatorics</a> by Richard Stanley is a great reference (advanced).</p>

<p><a href="http://www.maths.qmul.ac.uk/~pjc/comb/" rel="noreferrer">Combinatorics: topics, techniques, algorithms</a> by Peter Cameron and <a href="http://rads.stackoverflow.com/amzn/click/0198570422" rel="noreferrer">Invitation to Discrete Mathematics</a> by Matousek and Nesetril are fine introductions to combinatorics.</p>

<p><a href="https://www.crcpress.com/Applied-Combinatorics-Second-Edition/Roberts-Tesman/9781420099829" rel="noreferrer">Applied Combinatorics</a> by Roberts and Tesman is an encyclopaediac reference on applied combinatorics.</p>

CC BY-SA 3.0
2011-03-24T13:17:10.087Z
2016-02-07T11:06:47.660Z
2016-02-07T11:06:47.660Z
Anthony Labarre
<ul>
<li><p>The books by <a href="https://rads.stackoverflow.com/amzn/click/com/3642039413" rel="noreferrer" rel="nofollow noreferrer">Matousek</a> &amp; <a href="http://www.cs.princeton.edu/%7Echazelle/book.html" rel="noreferrer">Chazelle</a> on Discrepancy are excellent.</p>
<p>Almost <a href="http://www.amazon.com/s/ref=ntt_athr_dp_sr_1?_encoding=UTF8&amp;sort=relevancerank&amp;search-alias=books&amp;field-author=Jiri%20Matousek" rel="noreferrer">all the books by Matousek</a>, in fact, are worth reading to some extent.</p>
</li>
<li><p>Douglas West books on Graph Theory (<a href="https://rads.stackoverflow.com/amzn/click/com/0130144002" rel="noreferrer" rel="nofollow noreferrer">[1]</a> and <a href="https://rads.stackoverflow.com/amzn/click/com/B004E1RYGO" rel="noreferrer" rel="nofollow noreferrer">[2]</a>) are good.</p>
</li>
<li><p><a href="https://rads.stackoverflow.com/amzn/click/com/0470170204" rel="noreferrer" rel="nofollow noreferrer">Alon &amp; Spencer</a> is also excellent.</p>
</li>
<li><p><a href="https://rads.stackoverflow.com/amzn/click/com/0471588903" rel="noreferrer" rel="nofollow noreferrer">Pach &amp; Agarwal</a> is good for discrete geometry, as is the <a href="https://rads.stackoverflow.com/amzn/click/com/0521135117" rel="noreferrer" rel="nofollow noreferrer">Sharir &amp; Agarwal</a> if you are into DS sequences.</p>
</li>
<li><p><a href="https://rads.stackoverflow.com/amzn/click/com/0387238158" rel="noreferrer" rel="nofollow noreferrer">Brass, Moser, and Pach</a> book on open problems in discrete geometry is also very good.</p>
</li>
<li><p>The <a href="https://rads.stackoverflow.com/amzn/click/com/0387743871" rel="noreferrer" rel="nofollow noreferrer">Vanderbei</a> book on LP is very good.</p>
</li>
<li><p>Schrijver's books (<a href="https://rads.stackoverflow.com/amzn/click/com/0471982326" rel="noreferrer" rel="nofollow noreferrer">[1]</a> and <a href="https://rads.stackoverflow.com/amzn/click/com/3540443894" rel="noreferrer" rel="nofollow noreferrer">[2]</a>) are amazing.</p>
</li>
</ul>

CC BY-SA 3.0
2014-12-26T13:07:47.237Z
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](http://analysisofbooleanfunctions.org/), by Ryan O'Donnell (2014). It is available online freely [here](http://get.analysisofbooleanfunctions.org/) as well.
Clement C.
CC BY-SA 2.5
2010-12-01T04:03:06.267Z
2011-01-27T11:44:31.630Z
2020-06-17T09:38:08.363Z
Sariel Har-Peled
<h2>Functional Programming</h2>

<ul>
<li><a href="http://rads.stackoverflow.com/amzn/click/0521663504" rel="noreferrer">Purely Functional Data Structures</a> by <strong>Chris Okasaki</strong>. 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 &amp; algorithms in a functional language.</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0201137445" rel="noreferrer">Functional Programming: Practice and Theory</a> by <strong>Bruce J. Maclennan</strong>. 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.</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0521513383" rel="noreferrer">Pearls of Functional Algorithm Design</a> by <strong>Richard Bird</strong>. 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.</li>
<li><a href="http://adam.chlipala.net/cpdt/" rel="noreferrer">Certified Programming with Dependent Types</a> by <strong>Adam Chlipala</strong>. 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.</li>
</ul>

CC BY-SA 3.0
2011-01-03T13:25:51.547Z
2015-08-18T20:39:14.993Z
2015-08-18T20:39:14.993Z
Sadeq Dousti
<h2>Approximation Algorithms</h2>

<p>The book <a href="http://rads.stackoverflow.com/amzn/click/3642084699">Approximation Algorithms</a> by Vazirani is the best book on the subject. Another book is <a href="http://rads.stackoverflow.com/amzn/click/0534949681">Approximation Algorithms for NP-Hard Problems</a> by Hochbaum.</p>

<p>Here are comparisons by two reviewers:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>and</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>A recent book is <a href="http://www.designofapproxalgs.com/">The design of approximation algorithms</a> by Williamson and Shmoys.</p>

CC BY-SA 2.5
2010-12-02T14:17:01.917Z
2010-12-03T01:50:22.533Z
2010-12-03T01:50:22.533Z
Sadeq Dousti
<h2>Combinatorics</h2>

<p><strong>Introductory books.</strong> Any of the following books can serve as an excellent introduction to the subject:</p>

<ul>
<li><a href="http://rads.stackoverflow.com/amzn/click/158488780X">Handbook of Discrete and Combinatorial Mathematics</a> by Rosen.</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0201726343">Discrete and Combinatorial Mathematics: An Applied Introduction</a> by Grimaldi. See also the <a href="http://rads.stackoverflow.com/amzn/click/0321200330">solution manual</a>.</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/9810249012">A Walk Through Combinatorics and Introduction To Enumerative Combinatorics</a> and <a href="http://rads.stackoverflow.com/amzn/click/007312561X">Introduction To Enumerative Combinatorics</a> by Bona. The first book is more comprehensive as well as classical. The second book has considerable overlap with the first, but the emphasis is a lot more on modern counting methods.</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0521006015">A Course in Combinatorics</a> by van Lint &amp; Wilson.</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0521451337">Combinatorics: Topics, Techniques, Algorithms</a> by Cameron. (This book has a lot of nice exercises.)</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/044481504X">Combinatorial Problems and Exercises by László Lovász</a> (answered by @Sazzad)</li>
</ul>

<p><strong>More advanced texts.</strong></p>

<ul>
<li>Enumerative Combinatorics, <a href="http://rads.stackoverflow.com/amzn/click/0521663512">Volume 1</a> &amp; <a href="http://rads.stackoverflow.com/amzn/click/0521789877">Volume 2</a> by Stanley. It's simply a masterpiece on enumerative combinatorics; very challenging, very deep.</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/084933988X">Combinatorial Algorithms: Generation, Enumeration, and Search</a> by Kreher &amp; Stinson. More suited to computer science applications of combinatorics.</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0521136563">Additive Combinatorics</a> by Terence Tao and Van H. Vu. A very useful reference when facing a combinatorial problem related to number theory. </li>
</ul>

CC BY-SA 3.0
2010-12-02T14:05:29.413Z
2013-01-04T16:34:48.863Z
2013-01-04T16:34:48.863Z
Sadeq Dousti
<h2>Number Theory</h2>

<p>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:</p>

<ul>
<li><a href="http://rads.stackoverflow.com/amzn/click/0199219869">An Introduction to the Theory of Numbers</a> by Hardy <em>et al.</em> Hardy is a renown British mathematician. He was the mentor of the Indian mathematician <a href="http://en.wikipedia.org/wiki/Srinivasa_Ramanujan">Ramanujan</a>. His contribution to the field of number theory is <a href="http://www.numbertheory.org/obituaries/LMS/hardy/">quite amazing</a>.</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0471625469">An Introduction to the Theory of Numbers</a> by Niven, Zuckerman, Montgomery. Another classical introduction to the field.</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/082182824X">Solved and Unsolved Problems in Number Theory</a> by Shanks. This is <strong>the</strong> book for those who seek yet-to-be-proven conjectures in the field.</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0486417409">Riemann's Zeta Function</a> 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.</li>
</ul>

CC BY-SA 2.5
2011-03-05T20:44:26.423Z
What do you think of Rosen's book, or the Dover reprints?
Mark C
CC BY-SA 2.5
2011-03-06T03:05:49.560Z
@Mark: They're good too. Why not edit the post, and add those books as well?
Sadeq Dousti
CC BY-SA 2.5
2010-12-11T11:01:42.240Z
2010-12-11T18:06:41.010Z
2010-12-11T18:06:41.010Z
Sadeq Dousti
<h2>Hypergraphs</h2>

<p>There are not many books devoted exclusively to hypergraphs. One such book is</p>

<p>Berge C. <a href="http://rads.stackoverflow.com/amzn/click/0444874895">Hypergraphs: combinatorics of finite sets</a>.</p>

CC BY-SA 2.5
2010-12-11T21:43:37.053Z
2011-01-27T09:21:34.103Z
2011-01-27T09:21:34.103Z
Oleksandr Bondarenko
<p><strong>Graph Theory</strong></p>

<p>For introduction to graph theory:
<a href="http://www.math.uiuc.edu/~west/igt/" rel="noreferrer">Introduction to Graph Theory by West</a></p>

<p>More about graph theory:
<a href="http://www.math.jussieu.fr/~jabondy/" rel="noreferrer">Graph Theory by Bondy and Murty</a></p>

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

<p><a href="http://diestel-graph-theory.com/" rel="noreferrer">Graph theory : Reinhard Diestel</a>.</p>

<p>For graphs on surfaces with combinatorial approach:</p>

<p><a href="http://rads.stackoverflow.com/amzn/click/0801866898" rel="noreferrer">Graphs On Surfaces</a></p>

<p>And for digraphs:</p>

<p><a href="http://www.cs.rhul.ac.uk/books/dbook/" rel="noreferrer">Digraphs: Theory, Algorithms and Applications</a> </p>

CC BY-SA 3.0
2011-05-02T09:30:53.030Z
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
CC BY-SA 3.0
2011-04-30T17:21:07.147Z
2015-07-15T10:28:54.443Z
2015-07-15T10:28:54.443Z
dpufrj
<h2>Proof Theory</h2>
<p>Troelstra and Schwichtenberg's book <a href="http://books.google.com/books?id=x9x6F_4mUPgC" rel="nofollow noreferrer">Basic Proof Theory</a> is the de facto text on the topic now.</p>
<p>Girard, Taylor &amp; LaFont's <a href="http://books.google.com/books?id=6JOEQgAACAAJ" rel="nofollow noreferrer">Proofs and Types</a> is a shorter
book on the subject, and a version of it is available for download at <a href="http://www.paultaylor.eu/stable/Proofs%2BTypes.html" rel="nofollow noreferrer">http://www.paultaylor.eu/stable/Proofs%2BTypes.html</a></p>

CC BY-SA 3.0
2011-05-01T08:44:15.913Z
2013-09-26T22:12:28.180Z
2020-06-17T09:38:08.363Z
Rob
<h2>Logic:</h2>
<p>This is a verbatim of my answer to <a href="https://cstheory.stackexchange.com/questions/2571/what-kind-of-mathematical-background-is-needed-for-complexity-theory">this question</a>.</p>
<p>Knowledge of basic mathematical logic is, in my opinion, a plus. You can have a look at the two books by Cori and Lascar.</p>
<p><a href="http://books.google.com/books?id=Cle6_dOLt2IC&amp;dq=editions:Cle6_dOLt2IC&amp;hl=en&amp;ei=-EHNTM7SBorMswbOuPCWCA&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CCUQ6AEwAA" rel="noreferrer">Mathematical Logic: A Course with Exercises Part I</a></p>
<p><a href="http://books.google.com/books?id=zDrqGvJhSPIC&amp;printsec=frontcover&amp;dq=cori+lascar&amp;hl=en&amp;ei=0EHNTMa_BYqVswbXyfWWCA&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CCgQ6AEwAA#v=onepage&amp;q&amp;f=false" rel="noreferrer">Mathematical Logic: A Course with Exercises Part II</a></p>

CC BY-SA 3.0
2018-03-06T17:37:38.313Z
How about A Mathematical Introduction to Logic by Herbert Enderton?
RexYuan
CC BY-SA 2.5
2010-11-22T15:39:17.917Z
2010-11-22T18:10:25.173Z
2020-06-17T09:38:08.363Z
Sylvain Peyronnet
<h3>Writing Mathematics</h3>

<ul>
<li>Donald E. Knuth, Tracy Larrabee, and Paul M. Roberts, "<a href="https://books.google.ca/books?id=dDOehHMbUMcC" rel="noreferrer">Mathematical Writing</a>", 1989 (<a href="http://jmlr.csail.mit.edu/reviewing-papers/knuth_mathematical_writing.pdf" rel="noreferrer">pdf</a>)</li>
</ul>

CC BY-SA 3.0
2016-02-05T07:12:31.977Z
2016-02-05T07:12:31.977Z
Kaveh
<h2>VLSI Design</h2>

<p>I'm not into hardware. However, since the <a href="https://cstheory.stackexchange.com/faq">FAQ</a> includes VLSI as one of the sub-fields of TCS, I asked an expert about famous books in the VLSI design. Here they are:</p>

<ul>
<li><a href="http://rads.stackoverflow.com/amzn/click/0130909963" rel="nofollow noreferrer">Digital Integrated Circuits</a></li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0321547748" rel="nofollow noreferrer">CMOS VLSI Design: A Circuits and Systems Perspective</a></li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0137145004" rel="nofollow noreferrer">Modern VLSI Design: IP-Based Design</a></li>
</ul>

CC BY-SA 2.5
2010-12-13T18:56:29.000Z
In this area, I would recommend this extremely readable book: 
Synthesis and Optimization of Digital Circuits 
by Giovanni De Micheli
Chan Li
CC BY-SA 2.5
2010-11-29T09:41:16.420Z
2010-11-30T21:36:18.953Z
2017-04-13T12:32:28.167Z
Sadeq Dousti
<p>I've got to answer this question, even though it already has 30+ answers.</p>

<p><a href="http://cs.nyu.edu/shasha/outofmind.html" rel="noreferrer">Out of Their Minds</a> really is a must read for all computer scientists or people with a general interest in computer science. It introduces the reader to the life and work of 15 very important computer scientists, 8 of whom have won a Turing Award. I had read this book after it was recommended in my first university computer science course (almost two years ago now) and have since then skimmed through it again for 2 times. It is just brilliant.</p>

CC BY-SA 3.0
2011-06-15T00:30:12.860Z
2011-06-15T00:30:12.860Z
codd
<p><a href="http://rads.stackoverflow.com/amzn/click/0195125169" rel="noreferrer">Fundamental Algorithms in Algorithmic Algebra</a> by Chee Yap (available online <a href="http://www.cs.nyu.edu/yap/book/berlin/" rel="noreferrer">here</a>).</p>

<p>This text covers (fast) integer multiplication, polynomial root finding, integer polynomial factorization, lattice reduction techniques (specifically LLL), elimination theory, Grobner bases and continued fractions, all from an algorithmic perspective.  I found this text indispensable when learning about lattice reduction.</p>

CC BY-SA 3.0
2011-05-01T00:14:07.957Z
2011-05-01T00:14:07.957Z
user834
<p>A new addition to the list is a book "Foundations of Data Science" by Blum, Hopcroft and Kannan: <a href="https://www.cs.cornell.edu/jeh/book.pdf" rel="noreferrer">https://www.cs.cornell.edu/jeh/book.pdf</a></p>

CC BY-SA 4.0
2018-12-27T06:35:01.177Z
2018-12-27T06:35:01.177Z
Grigory Yaroslavtsev
<h2>Coloring Problems</h2>

<p>The best book on the subject is <a href="http://rads.stackoverflow.com/amzn/click/0387746404" rel="nofollow">The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators</a> by Soifer <em>et al.</em></p>

<p>There is also another book <a href="http://rads.stackoverflow.com/amzn/click/0471028657" rel="nofollow">Graph Coloring Problems</a>, by Tommy R. Jensen and Bjarne Toft.</p>

CC BY-SA 4.0
2020-01-28T03:35:17.820Z
The book **Graph Colorings** published by AMS looks at coloring and many variants of it used for practical applications (see https://bookstore.ams.org/conm-352). Notably, it includes list coloring.
Cyriac Antony
CC BY-SA 2.5
2010-12-02T14:09:30.267Z
2011-01-31T20:47:14.630Z
2011-01-31T20:47:14.630Z
Sadeq Dousti
<h1>Theory of Computation, Logic ( and also Music and Art )</h1>

<ul>
<li><a href="http://rads.stackoverflow.com/amzn/click/0465026567" rel="noreferrer">Gödel, Escher, Bach: An Eternal Golden Braid</a>.</li>
</ul>

<p>When I was a young student I found this book really exciting. Maybe it is not so  usefull in technical sense, but it's a good and funny way to understand hard concepts from Logic and Theory in general.</p>

CC BY-SA 3.0
2011-10-13T08:31:37.390Z
2011-10-13T08:31:37.390Z
AntonioFa
<h2>Parameterized complexity</h2>

<p>It might worth adding an answer since no one mentioned this area.</p>

<p>A comprehensible, well written quite recent book is</p>

<blockquote>
  <p>Parameterized Algorithms, M. Cygan et al., 2015</p>
</blockquote>

<p>Another book is</p>

<blockquote>
  <p>Parameterized complexity, R. Downey and M. Fellows, 1999</p>
</blockquote>

<p>Meanwhile the former presents a comprehensible text about most of the used methods and covers both algorithms and lower-bounds, the later presents more complexity-theory driven text.</p>

<p>Two other books are </p>

<blockquote>
  <p>Invitation to Fixed-Parameter Algorithms, R. Niedermeier, 2006</p>
</blockquote>

<p>and </p>

<blockquote>
  <p>Parameterized Complexity theory, J.Flum and M.Grohe, 2006</p>
</blockquote>

CC BY-SA 4.0
2020-01-27T16:42:59.013Z
2nd edition of the book by Downey and Fellows is out. It covers the later developments in the field (so I am told).
Cyriac Antony
CC BY-SA 4.0
2020-01-27T20:02:39.573Z
There is also a recent book from F.V.Fomin and others specialized in kernelization techniques (it alsoc includes meta theorems and lower-bounds).
Narek Bojikian
CC BY-SA 4.0
2020-01-28T03:45:56.990Z
You could give details of this book (at least name and year) and a link to it preferably in publisher's website.
Cyriac Antony
CC BY-SA 4.0
2020-04-05T22:53:53.107Z
I haven't read it, so I hesitated to add this to the answer (recall that the question is: "what books should everyone read") - but here is the reference: Fedor V. Fomin et al.: "Kernelization: Theory of Parameterized Preprocessing", Cambridge University Press 2019 https://www.cambridge.org/core/books/kernelization/36F327A8BB97CB6BBEA564368BF1AD4A
Hermann Gruber
CC BY-SA 4.0
2020-04-05T23:38:11.530Z
@HermannGruber I haven't read this exact book either. Cygan's book is the only one I read cover to cover among the ones in the answer. However, I wrote the answer in the spirit of the other answers as a reference for people who are interested in this exact field. Cygan's book is nonetheless very well written, enjoyable and a good read. It has a quite amusing introduction that I was able  to present to friends from outside computer science field.
Narek Bojikian
CC BY-SA 4.0
2020-01-03T17:16:19.230Z
2020-01-25T18:14:16.100Z
2020-01-25T18:14:16.100Z
Narek Bojikian
<p><strong>Algorithmic Game Theory</strong></p>

<p>Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani. <em>Algorithmic Game Theory</em>. Cambridge University Press, 24 de set. de 2007</p>

<p><strong>History of Computer Science</strong></p>

<p>COOPER, S. Barry; VAN LEEUWEN, Jan (Ed.). <em>Alan Turing: His work and impact.</em> Elsevier, 2013.</p>

<p><strong>Learning theory</strong></p>

<p>Kearns, Michael J., Umesh Virkumar Vazirani, and Umesh Vazirani. <em>An introduction to computational learning theory</em>. MIT press, 1994.</p>

<p>Sutton, Richard S., and Andrew G. Barto. <em>Reinforcement learning: An introduction</em>.(2011).</p>

<p>Arney, Chris. "<em>Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World.</em>" Mathematics and Computer Education 48.1 (2014): 126.</p>

CC BY-SA 4.0
2020-04-04T22:10:35.093Z
2020-04-04T22:10:35.093Z
Raphael Augusto
<p><strong>Algebraic Geometry</strong></p>

<p><a href="http://www.springer.com/us/book/9780387902449" rel="nofollow">Algebraic Geometry</a> by Robin Hartshorne.</p>

<p>The book is, for me, challenging but covers a broad area of the field of algebraic geometry. I found this a good addition to the next book when learning about ellipc curve cryptography.</p>

<p><strong>Elliptic curves</strong></p>

<p><a href="http://www.springer.com/us/book/9780387094939" rel="nofollow">The Arithmetic of Elliptic Curves</a> by Joseph H. Silverman. </p>

<p>The book is a good introduction into mathematics of elliptic as well as a suitable source for an extended insight of elliptic curve cryptography. Also it reads very well.</p>

CC BY-SA 3.0
2015-07-18T15:54:27.097Z
Hartshorne a book "everyone" should read? That's a surprising recommendation in a computer-science context.
Martin Berger
CC BY-SA 3.0
2015-07-23T13:15:54.560Z
According to the quesetion: ''The books can be math-oriented. [...] There are books that everyone in field X should read.''
So not all of the book might be interesting for people in the field ''elliptic curves'', but at least some of it.
Fleeep
CC BY-SA 3.0
2016-02-05T18:39:51.183Z
I think Martin's point was not that the *content* of Hartshorne might not be suitable here, but that Hartshorne is notorious as an introductory book, which one might imagine is especially so for people outside of algebraic geometry (which includes most computer scientists)...
Joshua Grochow
CC BY-SA 3.0
2015-07-14T14:21:53.577Z
2015-07-14T14:21:53.577Z
Fleeep
<p>[<a href="https://cstheory.stackexchange.com/posts/3253/timeline">Timeline</a>]</p>

<hr>

<p>This question has the same spirit of <a href="https://cstheory.stackexchange.com/q/1168/873">what papers should everyone read</a> and <a href="https://cstheory.stackexchange.com/q/1198/873">what videos should everybody watch</a>. It asks for remarkable books in different areas of theoretical computer science.</p>

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

<ul>
<li>Probability</li>
<li>Inequalities</li>
<li>Logic</li>
<li>Graph Theory</li>
<li>Combinatorics</li>
<li>Design &amp; Analysis of Algorithm</li>
<li>Theory of Computation / Computational Complexity Theory</li>
</ul>

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

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

<ul>
<li>in field X should read.</li>
<li>in field Y should read.</li>
<li>in both fields should read.</li>
</ul>

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

<p><strong>Edit: As suggested by <a href="https://cstheory.stackexchange.com/users/1080/dai-le">Dai Le</a>, please highlight the reason(s) you like the book as well.</strong></p>

<hr>

<p><strong>Related topics:</strong></p>

<ul>
<li><a href="https://cstheory.stackexchange.com/q/238/873">References for TCS proof techniques</a></li>
<li><a href="https://cstheory.stackexchange.com/q/1955/873">Books on automata theory for self-study</a></li>
<li><a href="https://mathoverflow.net/questions/20355">Books for probability</a></li>
<li><a href="https://mathoverflow.net/questions/8609">Favorite popular math book</a></li>
<li><a href="https://cstheory.stackexchange.com/q/1094/873">Beginner's guide to derandomization</a></li>
<li><a href="https://cstheory.stackexchange.com/q/1759/873">References on circuit lower bounds</a></li>
<li><a href="https://cstheory.stackexchange.com/q/3373/873">Survey article on the theory of recursive functions</a></li>
<li><a href="https://cstheory.stackexchange.com/questions/3533/books-on-programming-language-semantics">Books on Programming Language Semantics</a></li>
<li><a href="https://cstheory.stackexchange.com/q/3540/873">What are the recent TCS books whose drafts are available online</a></li>
<li><a href="https://cstheory.stackexchange.com/q/5801/873">Books on probability</a></li>
</ul>

CC BY-SA 3.0
2014-09-12T13:31:10.657Z
Since I can't answer to the question I'll do it here. **Discrete Mathematics** - TTC: Discrete Mathematics by Arthur T. Benjamin. It's a lectures bundle on various topics from Set Theory to Graphs and Probability.
Pithikos
CC BY-SA 3.0
2017-06-08T09:59:29.643Z
It may be interesting to compare this list of remarkable books with the list of introductory book from the [Is there a list of the canonical introductory textbooks covering the major branches of computer science?](https://www.reddit.com/r/compsci/comments/gprp0/is_there_a_list_of_the_canonical_introductory/) question on reddit/compsci. There is some overlap, but luckily the differences are sufficiently significant.
Thomas Klimpel
<reference-request><soft-question><big-list><books>
What Books Should Everyone Read?
Sadeq Dousti
# What Books Should Everyone Read?

(Asked by: username_0 on 2010-11-22)

[[Timeline](https://cstheory.stackexchange.com/posts/3253/timeline)]

---

This question has the same spirit of [what papers should everyone read](https://cstheory.stackexchange.com/q/1168/873) and [what videos should everybody watch](https://cstheory.stackexchange.com/q/1198/873). 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](https://cstheory.stackexchange.com/users/1080/dai-le), please highlight the reason(s) you like the book as well.**

---

**Related topics:**

* [References for TCS proof techniques](https://cstheory.stackexchange.com/q/238/873)
* [Books on automata theory for self-study](https://cstheory.stackexchange.com/q/1955/873)
* [Books for probability](https://mathoverflow.net/questions/20355)
* [Favorite popular math book](https://mathoverflow.net/questions/8609)
* [Beginner's guide to derandomization](https://cstheory.stackexchange.com/q/1094/873)
* [References on circuit lower bounds](https://cstheory.stackexchange.com/q/1759/873)
* [Survey article on the theory of recursive functions](https://cstheory.stackexchange.com/q/3373/873)
* [Books on Programming Language Semantics](https://cstheory.stackexchange.com/questions/3533/books-on-programming-language-semantics)
* [What are the recent TCS books whose drafts are available online](https://cstheory.stackexchange.com/q/3540/873)
* [Books on probability](https://cstheory.stackexchange.com/q/5801/873)

**Tags:** reference-request, soft-question, big-list, books
> **Comments:**
> **username_1**: Since I can't answer to the question I'll do it here. **Discrete Mathematics** - TTC: Discrete Mathematics by Arthur T. Benjamin. It's a lectures bundle on various topics from Set Theory to Graphs and Probability.  
> **username_2**: It may be interesting to compare this list of remarkable books with the list of introductory book from the [Is there a list of the canonical introductory textbooks covering the major branches of computer science?](https://www.reddit.com/r/compsci/comments/gprp0/is_there_a_list_of_the_canonical_introductory/) question on reddit/compsci. There is some overlap, but luckily the differences are sufficiently significant.  

---

## 38 answers

### Answer by username_3 on 2010-11-22. Score: 103

## Computational Complexity:

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

* [Computational Complexity: A Modern Approach](http://rads.stackoverflow.com/amzn/click/0521424267) by Sanjeev Arora and Boaz Barak ([Textbook homepage](http://www.cs.princeton.edu/theory/complexity/))
* [Computational Complexity: A Conceptual Perspective](http://rads.stackoverflow.com/amzn/click/052188473X) by Oded Goldreich ([Textbook homepage](http://www.wisdom.weizmann.ac.il/~oded/cc-book.html))

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](http://rads.stackoverflow.com/amzn/click/0201530821) by Christos Papadimitriou

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:

* [Introduction to the Theory of Computation](http://rads.stackoverflow.com/amzn/click/0534950973) 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](http://rads.stackoverflow.com/amzn/click/0199233217) 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.

> **Comments:**
> **username_4**: @turkistany, looks like you posted as I was writing. ;) I'll add some of my thoughts to your post!  
> **username_4**: As an aside for those interested in how these books compare to one another, I can also offer this [book review](http://www.cs.umd.edu/~gasarch/BLOGPAPERS/compbooks.pdf) of Arora/Barak and Goldreich that I recently wrote for the SIGACT book review column.  
> **username_5**: see also Lance Fortnow's list of his favorite Computational Complexity books on Amazon: http://amzn.com/l/22R1UX0Y9YRT2  
> **username_6**: 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.  
> **username_4**: 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.  
> **username_7**: I've found Sipser far more useful than Papadimitriou for actually teaching complexity theory, ymmv.  

---

### Answer by username_8 on 2010-11-22. Score: 51

## NP-Completeness:

Well, I guess Garey and Johnson's [Computers and Intractability: A Guide to the Theory of NP-Completeness](https://rads.stackoverflow.com/amzn/click/com/0716710455) will be found among the top books in this list.

> **Comments:**
> **username_9**: Still the best introduction to complexity theory after 30 years.  
> **username_10**: 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  
> **username_10**: 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"  

---

### Answer by username_11 on 2010-11-22. Score: 50

## Design & Analysis of Algorithms:

Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. [Introduction to Algorithms.](http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=8570)

R. Motwani, P. Raghavan. [Randomized algorithms.](http://books.google.com/books?id=QKVY4mDivBEC&lpg=PP1&dq=motwani%20raghavan%20randomized%20algorithms&hl=ru&pg=PP1#v=onepage&q&f=false)

I found this book [suggested by Ryan Williams](https://mathoverflow.net/questions/7772/9314#9314) on MathOverflow: [Algorithm Design](http://rads.stackoverflow.com/amzn/click/0321295358) by *Kleinberg & Tardos*.

Another excellent book is [Introduction to Algorithms: A Creative Approach](http://rads.stackoverflow.com/amzn/click/0201120372) 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)

> **Comments:**
> **username_13**: "An Introduction to the Analysis of Algorithms" by Sedgewick and Flajolet is great.  
> **username_12**: 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.  

---

### Answer by username_0 on 2010-11-22. Score: 46

## General Math for Computer Science:

* [Concrete Mathematics: A Foundation for Computer Science](http://rads.stackoverflow.com/amzn/click/0201558025) by Graham, Knuth, and Patashnik.
* [The Princeton Companion to Mathematics](http://rads.stackoverflow.com/amzn/click/0691118809) by Gowers *et al.*
* [Proofs from THE BOOK](http://rads.stackoverflow.com/amzn/click/3540636986) by Aigner and Ziegler.


---

### Answer by username_14 on 2010-11-22. Score: 43

## Type Systems and Programming Language Semantics:

Benjamin Pierce's [Types and Programming Languages](http://rads.stackoverflow.com/amzn/click/0262162091) and the follow up volume [Advanced Topics in Types and Programming Languages](http://rads.stackoverflow.com/amzn/click/0262162288). 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.

> **Comments:**
> **username_18**: 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.  
> **username_19**: I would suggest John Mitchell's Foundations for Programming Languages on this topic. As in previous comment, it's more mathematically matured.  
> **username_15**: Upvote for TAPL. FYI Benjamin Pierce is one of the authors of a new book "Software Foundation" that uses Coq.  
> **username_16**: Harper's "Practical Foundations for Programming Languages" is an excellent follow up to TaPL  
> **username_17**: Voted useful for TaPL. Software Foundations is also a recommended set of textbooks for programming languages and verification (and it is FREE available online).  

---

### Answer by username_20 on 2010-11-22. Score: 41

## 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](https://rads.stackoverflow.com/amzn/click/com/052154677X) by Michael Steele.

An encyclopedic book on the topic is [A Dictionary of Inequalities](https://rads.stackoverflow.com/amzn/click/com/0582327482). While this is not a book for reading cover-to-cover, it is good to have it at your disposal.
See also [the supplement](http://ajmaa.org/RGMIA/monographs/bullen/Dict-Ineq-Supp-Comb.pdf) of the book.

Moreover, Wikipedia has an excellent [list of inequalities](http://en.wikipedia.org/wiki/List_of_inequalities).

For specific topics, you may consult:

* [Probabilistic Inequalities](https://rads.stackoverflow.com/amzn/click/com/981428078X)
* [Matrix Inequalities](https://rads.stackoverflow.com/amzn/click/com/3540437983)
* [Geometric Inequalities](https://rads.stackoverflow.com/amzn/click/com/0883856042)
* [The book "A=B" by Petkovsek, Wilf and Zeilberger](http://www.math.upenn.edu/%7Ewilf/AeqB.html)

> **Comments:**
> **username_21**: 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: http://www.lkozma.net/inequalities_cheat_sheet/  
> **username_22**: Hardy, Littlewood, Polya, "Inequalities", a gem from the 1930s(?)  

---

### Answer by username_23 on 2011-01-28. Score: 40

Interesting.
No one mentioned volumes of [The Art of Computer Programming](http://www-cs-faculty.stanford.edu/~knuth/taocp.html) by [Donald E. Knuth](http://www-cs-faculty.stanford.edu/~knuth/index.html). A very detailed treatment of topics with very good exercises.

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

> **Comments:**
> **username_24**: TAOCP is still relevant and Vol. 4A has just been released.  

---

### Answer by username_20 on 2010-11-22. Score: 37

## Randomized Algorithms:

[Probability and Computing: Randomized Algorithms and Probabilistic Analysis](http://rads.stackoverflow.com/amzn/click/0521835402) 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](http://rads.stackoverflow.com/amzn/click/0521884276), which is also available for download in PDF format [here](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.2561&rep=rep1&type=pdf).

> **Comments:**
> **username_0**: This book was suggested in another topic (I think by Suresh). I found it excellent. Thanks to Aaron for mentioning it here.  

---

### Answer by username_6 on 2010-11-30. Score: 35

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](http://en.wikipedia.org/wiki/Finite_model_theory)*. For this area, I recommend the following excellent books:

> * Leonid Libkin, [Elements of Finite Model Theory](http://rads.stackoverflow.com/amzn/click/3540212027). (textbook)
> * Grädel et al., [Finite Model Theory and Its Applications](http://rads.stackoverflow.com/amzn/click/3540004289). (survey
>   articles and applications)

A sub-area of finite model theory is [descriptive complexity](http://en.wikipedia.org/wiki/Descriptive_complexity_theory), 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](http://rads.stackoverflow.com/amzn/click/0387986006).

## Proof Complexity

Another important area of logic in computer science is [Proof Complexity](http://en.wikipedia.org/wiki/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](http://portal.acm.org/citation.cfm?id=803756), 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:

> * Stephen Cook and Phuong Nguyen, [Logical Foundations of Proof Complexity](http://rads.stackoverflow.com/amzn/click/052151729X).
>   (draft made available [here](http://www.cs.toronto.edu/~sacook/homepage/book/))
> * Jan Krajíček, [Bounded Arithmetic, Propositional Logic and Complexity
>   Theory](http://rads.stackoverflow.com/amzn/click/0521452058).

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.


---

### Answer by username_0 on 2010-11-22. Score: 30

## Cryptography:

The two-volume book **Foundations of Cryptography** by Oded Goldreich ([Volume 1: Basic Tools](https://rads.stackoverflow.com/amzn/click/com/0521791723) and [Volume 2: Basic Applications](https://rads.stackoverflow.com/amzn/click/com/0521830842)) is an excellent book on the subject. (Early drafts available from [author's homepage](http://www.wisdom.weizmann.ac.il/%7Eoded/foc-book.html).) A [shortened version](https://rads.stackoverflow.com/amzn/click/com/1933019026) of this book is also available.

Another excellent book is [Introduction to Modern Cryptography: Principles and Protocols](https://rads.stackoverflow.com/amzn/click/com/1466570261) by Katz & Lindell.

[A Graduate Course in Applied Cryptography](https://toc.cryptobook.us/) is a work-in-progress book by Boneh and Shoup.

For those interested in mathematical backgrounds of cryptography, [An Introduction to Mathematical Cryptography](https://rads.stackoverflow.com/amzn/click/com/0387779930) by Hoffstein *et al.* is the natural choice.

Other excellent books are:

* [Handbook of Applied Cryptography](https://rads.stackoverflow.com/amzn/click/com/0849385237) by Menezes *et al.* (Chapter are [available online](http://www.cacr.math.uwaterloo.ca/hac/)).
* [Cryptography: Theory and Practice](https://rads.stackoverflow.com/amzn/click/com/1584885084) by Stinson.

---

**Specific Topics:**

* Books pertaining to advanced composition of security protocols:
* [Composition of Secure Multi-Party Protocols: A Comprehensive Study](https://rads.stackoverflow.com/amzn/click/com/354020105X) by Lindell.
* [Concurrent Zero-Knowledge](https://rads.stackoverflow.com/amzn/click/com/3642069495) by Rosen.
* Formal proofs in security protocols
* [Formal Correctness of Security Protocols](https://rads.stackoverflow.com/amzn/click/com/3540681345) by Bella.
* [Mathematics of Public Key Cryptography](https://rads.stackoverflow.com/amzn/click/com/1107013925) by Galbraith

> **Comments:**
> **username_0**: Since their introduction in 1993, [random oracles](http://en.wikipedia.org/wiki/Random_oracle) have been extensively used in literature; specially in signature schemes. I don't know a book that covers this area appropriately. Suggestions are welcome.  
> **username_4**: 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?  
> **username_0**: @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.  
> **username_4**: @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...  
> **username_4**: Actually, @Sadeq, your and Alon's answers to [this question](http://cstheory.stackexchange.com/questions/2975/straight-line-simulatability) are kind of the complement of the type of information I'd be interested in knowing more about anyway. I'll check out the papers the two of you linked there and maybe ask a question if I end up with something unanswered. :)  
> **username_0**: @Daniel: I'll be glad to help. Don't ever hesitate to ask ;)  
> **username_25**: @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).  

---

### Answer by username_0 on 2011-01-03. Score: 27

## Functional Programming

* [Purely Functional Data Structures](http://rads.stackoverflow.com/amzn/click/0521663504) 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](http://rads.stackoverflow.com/amzn/click/0201137445) 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](http://rads.stackoverflow.com/amzn/click/0521513383) 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](http://adam.chlipala.net/cpdt/) 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.


---

### Answer by username_0 on 2010-12-02. Score: 25

## Approximation Algorithms

The book [Approximation Algorithms](http://rads.stackoverflow.com/amzn/click/3642084699) by Vazirani is the best book on the subject. Another book is [Approximation Algorithms for NP-Hard Problems](http://rads.stackoverflow.com/amzn/click/0534949681) 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](http://www.designofapproxalgs.com/) by Williamson and Shmoys.


---

### Answer by username_0 on 2010-12-02. Score: 25

## Combinatorics

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

* [Handbook of Discrete and Combinatorial Mathematics](http://rads.stackoverflow.com/amzn/click/158488780X) by Rosen.
* [Discrete and Combinatorial Mathematics: An Applied Introduction](http://rads.stackoverflow.com/amzn/click/0201726343) by Grimaldi. See also the [solution manual](http://rads.stackoverflow.com/amzn/click/0321200330).
* [A Walk Through Combinatorics and Introduction To Enumerative Combinatorics](http://rads.stackoverflow.com/amzn/click/9810249012) and [Introduction To Enumerative Combinatorics](http://rads.stackoverflow.com/amzn/click/007312561X) by Bona. The first book is more comprehensive as well as classical. The second book has considerable overlap with the first, but the emphasis is a lot more on modern counting methods.
* [A Course in Combinatorics](http://rads.stackoverflow.com/amzn/click/0521006015) by van Lint & Wilson.
* [Combinatorics: Topics, Techniques, Algorithms](http://rads.stackoverflow.com/amzn/click/0521451337) by Cameron. (This book has a lot of nice exercises.)
* [Combinatorial Problems and Exercises by László Lovász](http://rads.stackoverflow.com/amzn/click/044481504X) (answered by @Sazzad)

**More advanced texts.**

* Enumerative Combinatorics, [Volume 1](http://rads.stackoverflow.com/amzn/click/0521663512) & [Volume 2](http://rads.stackoverflow.com/amzn/click/0521789877) by Stanley. It's simply a masterpiece on enumerative combinatorics; very challenging, very deep.
* [Combinatorial Algorithms: Generation, Enumeration, and Search](http://rads.stackoverflow.com/amzn/click/084933988X) by Kreher & Stinson. More suited to computer science applications of combinatorics.
* [Additive Combinatorics](http://rads.stackoverflow.com/amzn/click/0521136563) by Terence Tao and Van H. Vu. A very useful reference when facing a combinatorial problem related to number theory.


---

### Answer by username_26 on 2011-03-24. Score: 23

## Combinatorics

I want to cite [Analytic Combinatorics](http://algo.inria.fr/flajolet/Publications/book.pdf), 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.


---

### Answer by username_0 on 2010-11-30. Score: 23

## Quantum Computing

* [Quantum Computation and Quantum Information](http://rads.stackoverflow.com/amzn/click/0521635039) 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](http://rads.stackoverflow.com/amzn/click/9812387900) 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](http://rads.stackoverflow.com/amzn/click/013145224X) by *Marinescu & Marinescu*. While elementary and easy to learn, some people find it "filled with errors". In this regard, the [book's errata](http://www.cs.ucf.edu/~dcm/Errata.pdf) comes handy.
* [Quantum Computing Since Democritus](http://rads.stackoverflow.com/amzn/click/0521199565) 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:

* [Quantum Computing for Computer Scientists](http://rads.stackoverflow.com/amzn/click/0521879965) by *Yanofsky & Mannucci*.
* [An Introduction to Quantum Computing](http://rads.stackoverflow.com/amzn/click/019857049X) by *Kaye, Laflamme, and Mosca*.

> **Comments:**
> **username_27**: Another book I think is great is Kitaev's Classical and Quantum Computation.  

---

### Answer by username_28 on 2011-04-30. Score: 22

## Distributed algorithms

[Distributed Algorithms](http://rads.stackoverflow.com/amzn/click/1558603484) by Nancy Lynch
This is a classic text written by a pioneer of distributed computing;

[Introduction to Distributed Algorithms](http://rads.stackoverflow.com/amzn/click/0521794838) 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](http://rads.stackoverflow.com/amzn/click/0471453242) 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](http://rads.stackoverflow.com/amzn/click/0471719978) 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


---

### Answer by username_29 on 2010-12-13. Score: 20

## **Program Verification**

* [Mathematical Theory of
  Computation](http://rads.stackoverflow.com/amzn/click/0486432386) by Zohar Manna
* [Principles of Model Checking](http://rads.stackoverflow.com/amzn/click/026202649X) by
  Christel Baier and Joost-Pieter
  Katoen
* [Model Checking](http://rads.stackoverflow.com/amzn/click/0262032708) by Edmund
  M. Clarke Jr., Orna Grumberg and
  Doron A. Peled
* [Verification of Sequential and Concurrent Programs](http://www.amazon.co.uk/Verification-Sequential-Concurrent-Programs-Computer/dp/184882744X/ref=wl_it_dp_o?ie=UTF8&coliid=I3H4XLBLP0HCNH&colid=360PU4HGT5V1E) by Krzysztof R. Apt, Frank S. de Boer and, Ernst-Rüdiger Olderog
* [Logic in Computer Science: Modelling and Reasoning about Systems](http://rads.stackoverflow.com/amzn/click/052154310X) by M. Huth and M. Ryan

> **Comments:**
> **username_30**: 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.  
> **username_31**: @MartinBerger Any hints as to where this major progress might be learned about, if it is not in any recent textbooks?  
> **username_30**: @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.  
> **username_32**: 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.  

---

### Answer by username_33 on 2010-11-29. Score: 19

## Information Theory

[Information Theory, Inference, and Learning Algorithms](http://www.inference.phy.cam.ac.uk/mackay/itila/book.html) by David MacKay

Other famous textbooks on information theory can be found on [Wikipedia](http://en.wikipedia.org/wiki/Information_theory#Textbooks_on_information_theory).

> **Comments:**
> **username_6**: 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!  
> **username_0**: @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.  
> **username_6**: @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.  
> **username_0**: @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?  
> **username_6**: @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?  
> **username_0**: @Dai: As you wish! I left a link to Wikipedia, just in case people want to know what other choices are available. I think this is the best compromise. Your idea of asking people to explain why they like the book is brilliant. I'm changing the question to reflect that.  

---

### Answer by username_34 on 2010-11-29. Score: 18

## Communication Complexity:

---

[Communication Complexity](http://rads.stackoverflow.com/amzn/click/052102983X) 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](http://books.google.com/books?id=jQbUo-clEGkC&pg=PA131&dq=introduction%20to%20communication%20complexity&hl=es&ei=ExG9TaTLJ4q6vQPns8W1BQ&sa=X&oi=book_result&ct=result&resnum=1&ved=0CDAQ6AEwAA#v=onepage&q&f=false) 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.


---

### Answer by username_35 on 2010-11-23. Score: 17

## Optimization

I liked Paul Nahin's [When Least is Best.](http://rads.stackoverflow.com/amzn/click/0691070784)

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.](http://www.cs.umd.edu/~gasarch/bookrev/41-3.pdf)

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.


---

### Answer by username_36 on 2011-02-18. Score: 17

## Computational Algebra

As Shiva said [in this answer](https://cstheory.stackexchange.com/questions/2270/formal-representation-of-rings-in-computations/2272#2272), 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](https://cstheory.stackexchange.com/q/2270/1800),

* [Modern Computer Algebra](http://rads.stackoverflow.com/amzn/click/0521826462) by Joachim von zur Gathen and Jürgen Gerhard.
* [Algebraic Complexity Theory](http://rads.stackoverflow.com/amzn/click/3540605827) by Peter Bürgisser, Michael Clausen, Mohammad A. Shokrollahi and T. Lickteig.
* [Algorithmic Algebra](http://rads.stackoverflow.com/amzn/click/0387940901) by Bhubaneswar Mishra.
* [A Computational Introduction to Number Theory and Algebra](http://shoup.net/ntb/) by Victor Shoup.

## Computational Analysis

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

* [Computable Analysis](http://www.amazon.co.uk/Computable-Analysis-Oliver-Aberth/dp/0070000794) by Oliver Aberth.
* [Computable Analysis: An Introduction](http://rads.stackoverflow.com/amzn/click/3540668179) by Klaus Weihrauch.


---

### Answer by username_8 on 2011-03-24. Score: 17

## Combinatorics

[generatingfunctionology](http://www.math.upenn.edu/~wilf/DownldGF.html), 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](http://www-math.mit.edu/~rstan/ec/ec1/) by Richard Stanley is a great reference (advanced).

[Combinatorics: topics, techniques, algorithms](http://www.maths.qmul.ac.uk/~pjc/comb/) by Peter Cameron and [Invitation to Discrete Mathematics](http://rads.stackoverflow.com/amzn/click/0198570422) by Matousek and Nesetril are fine introductions to combinatorics.

[Applied Combinatorics](https://www.crcpress.com/Applied-Combinatorics-Second-Edition/Roberts-Tesman/9781420099829) by Roberts and Tesman is an encyclopaediac reference on applied combinatorics.


---

### Answer by username_37 on 2010-12-01. Score: 16

* The books by [Matousek](https://rads.stackoverflow.com/amzn/click/com/3642039413) & [Chazelle](http://www.cs.princeton.edu/%7Echazelle/book.html) on Discrepancy are excellent.

  Almost [all the books by Matousek](http://www.amazon.com/s/ref=ntt_athr_dp_sr_1?_encoding=UTF8&sort=relevancerank&search-alias=books&field-author=Jiri%20Matousek), in fact, are worth reading to some extent.
* Douglas West books on Graph Theory ([[1]](https://rads.stackoverflow.com/amzn/click/com/0130144002) and [[2]](https://rads.stackoverflow.com/amzn/click/com/B004E1RYGO)) are good.
* [Alon & Spencer](https://rads.stackoverflow.com/amzn/click/com/0470170204) is also excellent.
* [Pach & Agarwal](https://rads.stackoverflow.com/amzn/click/com/0471588903) is good for discrete geometry, as is the [Sharir & Agarwal](https://rads.stackoverflow.com/amzn/click/com/0521135117) if you are into DS sequences.
* [Brass, Moser, and Pach](https://rads.stackoverflow.com/amzn/click/com/0387238158) book on open problems in discrete geometry is also very good.
* The [Vanderbei](https://rads.stackoverflow.com/amzn/click/com/0387743871) book on LP is very good.
* Schrijver's books ([[1]](https://rads.stackoverflow.com/amzn/click/com/0471982326) and [[2]](https://rads.stackoverflow.com/amzn/click/com/3540443894)) are amazing.

> **Comments:**
> **username_38**: 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](http://analysisofbooleanfunctions.org/), by Ryan O'Donnell (2014). It is available online freely [here](http://get.analysisofbooleanfunctions.org/) as well.  

---

### Answer by username_43 on 2010-11-22. Score: 15

## Logic:

This is a verbatim of my answer to [this question](https://cstheory.stackexchange.com/questions/2571/what-kind-of-mathematical-background-is-needed-for-complexity-theory).

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](http://books.google.com/books?id=Cle6_dOLt2IC&dq=editions:Cle6_dOLt2IC&hl=en&ei=-EHNTM7SBorMswbOuPCWCA&sa=X&oi=book_result&ct=result&resnum=1&ved=0CCUQ6AEwAA)

[Mathematical Logic: A Course with Exercises Part II](http://books.google.com/books?id=zDrqGvJhSPIC&printsec=frontcover&dq=cori+lascar&hl=en&ei=0EHNTMa_BYqVswbXyfWWCA&sa=X&oi=book_result&ct=result&resnum=1&ved=0CCgQ6AEwAA#v=onepage&q&f=false)

> **Comments:**
> **username_32**: How about A Mathematical Introduction to Logic by Herbert Enderton?  

---

### Answer by username_0 on 2010-12-11. Score: 13

## 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](http://rads.stackoverflow.com/amzn/click/0199219869) by Hardy *et al.* Hardy is a renown British mathematician. He was the mentor of the Indian mathematician [Ramanujan](http://en.wikipedia.org/wiki/Srinivasa_Ramanujan). His contribution to the field of number theory is [quite amazing](http://www.numbertheory.org/obituaries/LMS/hardy/).
* [An Introduction to the Theory of Numbers](http://rads.stackoverflow.com/amzn/click/0471625469) by Niven, Zuckerman, Montgomery. Another classical introduction to the field.
* [Solved and Unsolved Problems in Number Theory](http://rads.stackoverflow.com/amzn/click/082182824X) by Shanks. This is **the** book for those who seek yet-to-be-proven conjectures in the field.
* [Riemann's Zeta Function](http://rads.stackoverflow.com/amzn/click/0486417409) 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.

> **Comments:**
> **username_39**: What do you think of Rosen's book, or the Dover reprints?  
> **username_0**: @Mark: They're good too. Why not edit the post, and add those books as well?  

---

### Answer by username_40 on 2010-12-11. Score: 13

## Hypergraphs

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

Berge C. [Hypergraphs: combinatorics of finite sets](http://rads.stackoverflow.com/amzn/click/0444874895).


---

### Answer by username_41 on 2011-04-30. Score: 13

**Graph Theory**

For introduction to graph theory:
[Introduction to Graph Theory by West](http://www.math.uiuc.edu/~west/igt/)

More about graph theory:
[Graph Theory by Bondy and Murty](http://www.math.jussieu.fr/~jabondy/)

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

[Graph theory : Reinhard Diestel](http://diestel-graph-theory.com/).

For graphs on surfaces with combinatorial approach:

[Graphs On Surfaces](http://rads.stackoverflow.com/amzn/click/0801866898)

And for digraphs:

[Digraphs: Theory, Algorithms and Applications](http://www.cs.rhul.ac.uk/books/dbook/)

> **Comments:**
> **username_26**: 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.  

---

### Answer by username_42 on 2011-05-01. Score: 11

## Proof Theory

Troelstra and Schwichtenberg's book [Basic Proof Theory](http://books.google.com/books?id=x9x6F_4mUPgC) is the de facto text on the topic now.

Girard, Taylor & LaFont's [Proofs and Types](http://books.google.com/books?id=6JOEQgAACAAJ) 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>


---

### Answer by username_44 on 2016-02-05. Score: 9

### Writing Mathematics

* Donald E. Knuth, Tracy Larrabee, and Paul M. Roberts, "[Mathematical Writing](https://books.google.ca/books?id=dDOehHMbUMcC)", 1989 ([pdf](http://jmlr.csail.mit.edu/reviewing-papers/knuth_mathematical_writing.pdf))


---

### Answer by username_0 on 2010-11-29. Score: 9

## VLSI Design

I'm not into hardware. However, since the [FAQ](https://cstheory.stackexchange.com/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:

* [Digital Integrated Circuits](http://rads.stackoverflow.com/amzn/click/0130909963)
* [CMOS VLSI Design: A Circuits and Systems Perspective](http://rads.stackoverflow.com/amzn/click/0321547748)
* [Modern VLSI Design: IP-Based Design](http://rads.stackoverflow.com/amzn/click/0137145004)

> **Comments:**
> **username_29**: In this area, I would recommend this extremely readable book:  Synthesis and Optimization of Digital Circuits  by Giovanni De Micheli  

---

### Answer by username_45 on 2011-06-15. Score: 8

I've got to answer this question, even though it already has 30+ answers.

[Out of Their Minds](http://cs.nyu.edu/shasha/outofmind.html) really is a must read for all computer scientists or people with a general interest in computer science. It introduces the reader to the life and work of 15 very important computer scientists, 8 of whom have won a Turing Award. I had read this book after it was recommended in my first university computer science course (almost two years ago now) and have since then skimmed through it again for 2 times. It is just brilliant.


---

### Answer by username_46 on 2011-05-01. Score: 8

[Fundamental Algorithms in Algorithmic Algebra](http://rads.stackoverflow.com/amzn/click/0195125169) by Chee Yap (available online [here](http://www.cs.nyu.edu/yap/book/berlin/)).

This text covers (fast) integer multiplication, polynomial root finding, integer polynomial factorization, lattice reduction techniques (specifically LLL), elimination theory, Grobner bases and continued fractions, all from an algorithmic perspective. I found this text indispensable when learning about lattice reduction.


---

### Answer by username_47 on 2018-12-27. Score: 6

A new addition to the list is a book "Foundations of Data Science" by Blum, Hopcroft and Kannan: <https://www.cs.cornell.edu/jeh/book.pdf>


---

### Answer by username_0 on 2010-12-02. Score: 5

## Coloring Problems

The best book on the subject is [The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators](http://rads.stackoverflow.com/amzn/click/0387746404) by Soifer *et al.*

There is also another book [Graph Coloring Problems](http://rads.stackoverflow.com/amzn/click/0471028657), by Tommy R. Jensen and Bjarne Toft.

> **Comments:**
> **username_48**: The book **Graph Colorings** published by AMS looks at coloring and many variants of it used for practical applications (see https://bookstore.ams.org/conm-352). Notably, it includes list coloring.  

---

### Answer by username_49 on 2011-10-13. Score: 5

# Theory of Computation, Logic ( and also Music and Art )

* [Gödel, Escher, Bach: An Eternal Golden Braid](http://rads.stackoverflow.com/amzn/click/0465026567).

When I was a young student I found this book really exciting. Maybe it is not so usefull in technical sense, but it's a good and funny way to understand hard concepts from Logic and Theory in general.


---

### Answer by username_50 on 2020-01-03. Score: 4

## Parameterized complexity

It might worth adding an answer since no one mentioned this area.

A comprehensible, well written quite recent book is

> Parameterized Algorithms, M. Cygan et al., 2015

Another book is

> Parameterized complexity, R. Downey and M. Fellows, 1999

Meanwhile the former presents a comprehensible text about most of the used methods and covers both algorithms and lower-bounds, the later presents more complexity-theory driven text.

Two other books are

> Invitation to Fixed-Parameter Algorithms, R. Niedermeier, 2006

and

> Parameterized Complexity theory, J.Flum and M.Grohe, 2006

> **Comments:**
> **username_48**: 2nd edition of the book by Downey and Fellows is out. It covers the later developments in the field (so I am told).  
> **username_50**: There is also a recent book from F.V.Fomin and others specialized in kernelization techniques (it alsoc includes meta theorems and lower-bounds).  
> **username_48**: You could give details of this book (at least name and year) and a link to it preferably in publisher's website.  
> **username_51**: I haven't read it, so I hesitated to add this to the answer (recall that the question is: "what books should everyone read") - but here is the reference: Fedor V. Fomin et al.: "Kernelization: Theory of Parameterized Preprocessing", Cambridge University Press 2019 https://www.cambridge.org/core/books/kernelization/36F327A8BB97CB6BBEA564368BF1AD4A  
> **username_50**: @HermannGruber I haven't read this exact book either. Cygan's book is the only one I read cover to cover among the ones in the answer. However, I wrote the answer in the spirit of the other answers as a reference for people who are interested in this exact field. Cygan's book is nonetheless very well written, enjoyable and a good read. It has a quite amusing introduction that I was able  to present to friends from outside computer science field.  

---

### Answer by username_52 on 2020-04-04. Score: 3

**Algorithmic Game Theory**

Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani. *Algorithmic Game Theory*. Cambridge University Press, 24 de set. de 2007

**History of Computer Science**

COOPER, S. Barry; VAN LEEUWEN, Jan (Ed.). *Alan Turing: His work and impact.* Elsevier, 2013.

**Learning theory**

Kearns, Michael J., Umesh Virkumar Vazirani, and Umesh Vazirani. *An introduction to computational learning theory*. MIT press, 1994.

Sutton, Richard S., and Andrew G. Barto. *Reinforcement learning: An introduction*.(2011).

Arney, Chris. "*Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World.*" Mathematics and Computer Education 48.1 (2014): 126.


---

### Answer by username_53 on 2015-07-14. Score: 3

**Algebraic Geometry**

[Algebraic Geometry](http://www.springer.com/us/book/9780387902449) by Robin Hartshorne.

The book is, for me, challenging but covers a broad area of the field of algebraic geometry. I found this a good addition to the next book when learning about ellipc curve cryptography.

**Elliptic curves**

[The Arithmetic of Elliptic Curves](http://www.springer.com/us/book/9780387094939) by Joseph H. Silverman.

The book is a good introduction into mathematics of elliptic as well as a suitable source for an extended insight of elliptic curve cryptography. Also it reads very well.

> **Comments:**
> **username_30**: Hartshorne a book "everyone" should read? That's a surprising recommendation in a computer-science context.  
> **username_53**: According to the quesetion: ''The books can be math-oriented. [...] There are books that everyone in field X should read.'' So not all of the book might be interesting for people in the field ''elliptic curves'', but at least some of it.  
> **username_54**: I think Martin's point was not that the *content* of Hartshorne might not be suitable here, but that Hartshorne is notorious as an introductory book, which one might imagine is especially so for people outside of algebraic geometry (which includes most computer scientists)...  

---

