Recommended textbooks and courses

Preliminary remarks:

  • This reading/course list is intended for very early career researchers who want to work in my rough area and who are wondering what skills they need. For example, the list might help you decide which courses to take in your undergraduate degree if you want to do a PhD on a cluster of topics similar to the topics I work on.
  • Currently the list focuses on relatively general and technical skills, which one might be able to take as courses in a CS undergraduate degree. (For example, I don’t currently list philosophy or advanced, niche topics like open-source game theory.)
  • Mathematics is not only a pile of specific results, techniques and ideas. It is also a general language and a general way of thinking. So, I think taking random math courses rarely hurts if you have not yet taken many math courses. One of the math courses that I have the fondest memories of was on Petri nets, which have no relevance whatsoever to what I am working on now.
  • In order to get ready for doing theoretical research it is essential to practice writing mathematical proofs. Specifically, I think it is important to have someone give you feedback on your proofs. Unfortunately, most Coursera courses that I’ve looked at don’t put much emphasis on this. In some countries (e.g., in the US), you can even take university math courses without getting much feedback on mathematical proofs you write. I think this is also a significant obstacle to learning university-level math autodidactically from scratch.
  • I often don’t have great recommendations for books, because I learned much of what I know from taking courses at universities and because I learned about some areas (e.g., probability theory) in the context of other courses or projects.
  • The list is not intended to be a list of “necessary conditions”. The relevance of different topics depends a lot on what exactly you want to work on. For any given project that I work on, I only need a small subset of the areas listed here.
  • The different areas listed here have plenty of overlap. Some sets of topics on this list may encompass all the most relevant aspects of other areas on this list. For example, if you take undergraduate courses in all of the below topics, except probability theory, you may already know all the most important probability-theoretic concepts.

Here are the recommendations:

  • Set theory
    • Set-theoretic notation is used everywhere, so it’s a good way to get started if you don’t have prior exposure to university-level math.
    • Some object-level set theory ideas are also important to understand (for example, cardinality, bijections).
    • Recommended material
  • Graph theory
    • Non-trivial graph-theoretic ideas generally aren’t very important for my kind of research. However, like set theory, graph theory is used as notation in many other contexts (e.g., Bayes nets, extensive-form games, neural nets, search, etc.), so it’s good to be familiar with basic graph-theoretic notation and ideas.
  • Analysis
    • You can start with “calculus” (which I understand is a less formal, less rigorous version of analysis) if you don’t yet know the basics of differentiation and integration.
  • Linear algebra
    • The basics of linear algebra (topics one might learn even in high-school, such as linear independence) are important in many places. More advanced concepts are especially important for ML/NNs, but they also show up occasionally in other places. I generally view linear algebra as one of the biggest gaps in my undergraduate-level CS/math education. I took a linear algebra course a long time ago, but haven’t used the more advanced concepts much.
  • Decision theory
  • Probability theory
  • Artificial Intelligence and Machine Learning
    • Some important concepts and topics: reinforcement learning (Q learning, SARSA), optimization (gradient descent), neural nets and backpropagation
    • Recommended material
    • Generally there are lots of great resources on the practical aspects of machine learning, i.e., how to actually train a neural net that learns to classify the MNIST data set or the like. I’m not the best person to make a recommendation for materials. I would assume that practical ML is much easier to learn autodidactically than most of the other topics on this list.
  • Computability theory and logic
    • Some important concepts and topics: Turing completeness, Church–Turing thesis, undecidability of the halting problem, axiomatizations of mathematics (Peano arithmetic, Zermelo-Fraenkl set theory)
      • Generally it’s not that important to learn about finite automata or context-free grammars.
    • Recommended material
      • Douglas Hofstadter: Gödel, Escher, Bach.
        • This famous book is a popular-science-type introduction to issues of self-reference in logic and computation. Obviously, it’s quite informal and it shouldn’t be the only thing you read. You should only read it if you enjoy it!
  • Algorithms and computational complexity
    • Some important concepts and topics: P versus NP; NP-hardness; big O notation, linear programming.
    • Recommended material
      • Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Virkumar Vazirani: Algorithms
  • Game theory
    • Some important concepts and topics: Nash equilibria, Stackelberg equilibria, elimination by (iterated) (strict) dominance, minimax theorem, extensive-form games, subgame-perfect equilibrium, folk theorems for repeated games.
    • Recommended material
      • Martin J. Osborne: An Introduction to Game Theory
        • This book is a very easy read, I would say.
  • Algorithms and computational complexity x game theory.
  • Programming
    • For ML, it’s most important to learn Python. I also think Python is one of the easiest languages to learn nowadays.

Other reading lists: