17
$\begingroup$

I am a graduate student in math, and theoretical computer science is a domain which I never understood what it is about because I couldn't find a good read about the topic. I want to know what this domain is actually about, what kind of topics it is concerned with, what prerequisites are needed to embark into it, etc. For now, I just want to know:

What is a good introductory book to theoretical computer science?

Given that there is such a thing. If not, where should a mathematician who has basic knowledge about computer science (i.e. they know the basics of one or two programming languages) start if they want to understand what theoretical computer science is about? What do you recommend?

thanks!

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Great question. I'm really at a loss. Theoretical CS is just so broad and diverse, I doubt anyone has attempted to survey it all in a single place. There are intro books, such as Sipser's "Theory of Computation" or "Algorithms" by Dasgupta, Papadimitriou, and Vazirani. But those are like undergraduate prerequisites and won't give an idea of what current TCS is "actually about"... $\endgroup$
    – usul
    Aug 18, 2016 at 15:53
  • 6
    $\begingroup$ The question is much too broad. One could then equally ask: "Where to learn more about what Mathematics is?". One should therefore look at the fields of TCS which are close to math, like complexity theory, cryptography, approximation. Say, circuit complexity is just a part of Extremal Combinatorics. Sipser's book is indeed great: it is a mathematicians view at TCS (a small part of it, needless to say); Sipser himself is actually a mathematician. $\endgroup$
    – Stasys
    Aug 18, 2016 at 16:34
  • 2
    $\begingroup$ Avi Wigderson's upcoming text is a great resource: math.ias.edu/avi/book $\endgroup$
    – András Salamon
    Oct 28, 2017 at 16:50

2 Answers 2

Reset to default
31
$\begingroup$

First, "theoretical computer science" means different things to different people. I think for most users on this site, a historical caricature (which reflects some modern sociological tendencies) is that there is "Theory A" and "Theory B" (with no implied order relation between them): Theory A consists of the theory of algorithms, complexity theory, cryptography, and similar. Theory B consists of things like the theory of programming languages, theory of automata, etc. Depending on your tastes in mathematics, you may prefer one over the other (or like both equally). I am more familiar with "Theory A," so let me give some references there:

  • Start with Sipser's book. This will give you a good introduction to automata, Turing machines, computability, Kolmogorov complexity, P vs NP, and a few other complexity classes. It is very well-written (in my opinion, it is one of the best-written technical books ever)

  • For algorithms, I have a slighty preference for Kleinberg-Tardos, but there are many good introductory books out there. You might be especially interested in computational geometry, which has its own set of great books.

  • Given that you are a mathematics graduate student, a major branch of TCS that is missing from these books is algebraic complexity theory, which often is closely related to algebra (both commutative and non-commutative), representation theory, group theory, and algebraic geometry. There is a canonical text here, which is Burgisser-Clausen-Shokrollahi. It is somewhat encyclopedic, so may not be the best introduction, but I'm not sure there is a really introductory book in this area. You might also check out the surveys by Chen-Kayal-Wigderson and Shiplka-Yehudayoff.

After that, I'd suggest browsing through more advanced books on particular topics, depending on your mathematical taste:

  • Arora-Barak is more modern complexity theory (continues on where Sipser's book ends, so to speak), giving you a flavor of the techniques involved (mix of combinatorics and algebra, mostly)

  • Jukna's book on Boolean function complexity does similar, but more in-depth for Boolean circuit complexity in particular (very combinatorial in flavor)

  • Geometric complexity theory. See here or Landsberg's introduction for geometers.

  • O'Donnell's book Analysis of Boolean Functions has a more Fourier-analytic bent.

  • Cryptography. The more advanced mathematical aspects here are typically number theory and algebraic geometry. While these pure mathematical aspects represent only a small portion of cryptography, they are an important one that you might find interesting. Not being my area, I'm not sure of what a good starting book is here.

  • Coding theory. Here, the mathematical theory ranges from sphere-packing (see the book by Conway and Sloane) to algebraic geometry (e.g., the book by Stichtenoth). Again, not my area, so I'm not sure if these are the best starting points, but flipping through them you will quickly get the flavor and decide if you want to delve deeper.

And then there are many other mathematical topics that only appear in the research literature, like connections with foams, graph theory, C*-algebras (let me just point you to the Kadison-Singer conjecture), invariant theory, representation theory, quadratures, and on and on. See also these related questions

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

The Nature of Computation by Cristopher Moore and Stephan Mertens.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I love this book - I didn't recommend it in my answer mostly for its length, though of course one can always pick and choose the chapters to read. $\endgroup$
    – Joshua Grochow
    Aug 24, 2016 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.