271
$\begingroup$

[Timeline]

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

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

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

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

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

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

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

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

Related topics:

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Pithikos
    Sep 12, 2014 at 13:31
  • $\begingroup$ 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? question on reddit/compsci. There is some overlap, but luckily the differences are sufficiently significant. $\endgroup$
    – Thomas Klimpel
    Jun 8, 2017 at 9:59

39 Answers 39

Reset to default
1
2
9
$\begingroup$

Writing Mathematics

Improve this answer
$\endgroup$
8
$\begingroup$

Fundamental Algorithms in Algorithmic Algebra by Chee Yap (available online here).

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.

Improve this answer
$\endgroup$
8
$\begingroup$

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

Out of Their Minds 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.

Improve this answer
$\endgroup$
6
$\begingroup$

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

Improve this answer
$\endgroup$
5
$\begingroup$

Coloring Problems

The best book on the subject is The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators by Soifer et al.

There is also another book Graph Coloring Problems, by Tommy R. Jensen and Bjarne Toft.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The book Graph Colorings published by AMS looks at coloring and many variants of it used for practical applications (see bookstore.ams.org/conm-352). Notably, it includes list coloring. $\endgroup$
    – Cyriac Antony
    Jan 28, 2020 at 3:35
5
$\begingroup$

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

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ 2nd edition of the book by Downey and Fellows is out. It covers the later developments in the field (so I am told). $\endgroup$
    – Cyriac Antony
    Jan 27, 2020 at 16:42
  • $\begingroup$ There is also a recent book from F.V.Fomin and others specialized in kernelization techniques (it alsoc includes meta theorems and lower-bounds). $\endgroup$
    – Narek Bojikian
    Jan 27, 2020 at 20:02
  • $\begingroup$ You could give details of this book (at least name and year) and a link to it preferably in publisher's website. $\endgroup$
    – Cyriac Antony
    Jan 28, 2020 at 3:45
  • 1
    $\begingroup$ 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 cambridge.org/core/books/kernelization/… $\endgroup$
    – Hermann Gruber
    Apr 5, 2020 at 22:53
  • 1
    $\begingroup$ @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. $\endgroup$
    – Narek Bojikian
    Apr 5, 2020 at 23:38
3
$\begingroup$

Algebraic Geometry

Algebraic Geometry 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 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.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ Hartshorne a book "everyone" should read? That's a surprising recommendation in a computer-science context. $\endgroup$
    – Martin Berger
    Jul 18, 2015 at 15:54
  • $\begingroup$ 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. $\endgroup$
    – Fleeep
    Jul 23, 2015 at 13:15
  • 2
    $\begingroup$ 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)... $\endgroup$
    – Joshua Grochow
    Feb 5, 2016 at 18:39
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
2

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