Where to learn more about what Theoretical Computer Science is? 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!
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


Resources for mathematicians hoping to learn more computer science
Are there any topics in theoretical CS that are more about pure math?
Applications of TCS to classical mathematics?
Solid applications of category theory in TCS?