Ryan O’Donnell’s “TCS Toolkit” and other resources

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

2.   Basic Asymptotics

3.   Factorials and Binomial Coefficients

4.   Central Limit Theorem

5.   Chernoff Bounds

6.   Computational Models

7.   Fast Multiplication with the DFT

8.   Analysis of Boolean Functions

9.   Quantum Computation

10.   Fields and Polynomials

11.   Error-Correcting Codes

12.   Derandomization

13.   Spectral Graph Theory I

14.   Spectral Graph Theory II

15.   Spectral Graph Theory III

15.1.   Cheeger’s Inequality (Spectral Graph Theory bonus)

16.   Expander Graphs

17.   Linear Programming I

18.   Linear Programming II

19.   The Ellipsoid Algorithm

20.   CSPs and Approximation

21.   LP Hierarchies and Proof Systems

22.   Treewidth

23.   Communication Complexity

24.   Information Theory

25.   Cryptography

26.   Hardness Assumptions

27.   The PCP Theorem

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s