When I was in grad school a common advice for beginning grad students was to leaf through the (paper) STOC or FOCS proceedings to see papers that you are interested in. This is still a decent advice (and requires less physical strength these days 🙂 ) but papers are not always the best source for people starting out. More often than we’d like to, the author of the 10th paper on a topic writes it to the audience of people that read (in fact probably wrote) the previous 9 papers.
Talks often do a better job of giving an overview of the field, and one great resource is the videos from the Simons Institute. If you want to get more in-depth information about a particular topic, it’s hard to beat the extended surveys in Foundations and Trends in TCS, as well as the related areas such as Machine Learning and Information Theory.
But if you are not yet sure what topic you’re interested in, or perhaps not even sure if you want to go to grad school, but you just know that you are interested in theory, there is now a new great resource. As I learned from Twitter, Ryan O’Donnell has just finished his TCS Toolkit course. All 99(!) lectures are on YouTube.
The topics are the following (these links are to the handwritten notes, for the lecture videos see YouTube channel):
1. Course Overview, and How to TCS
3. Factorials and Binomial Coefficients
7. Fast Multiplication with the DFT
8. Analysis of Boolean Functions
15.1. Cheeger’s Inequality (Spectral Graph Theory bonus)
21. LP Hierarchies and Proof Systems
p.s. For giving a high level taste of theory to beginning undergraduates, a great resource is Aaronson’s Quantum Computing since Democritus or Wigderson’s Math and Computation if they’re more math inclined.
One thought on “Ryan O’Donnell’s “TCS Toolkit” and other resources”
looks like a great resource, thanks for pointing it out.