CS Theory Toolkit

Course ID 15751

Doctoral Breadth Course: Algorithms and Complexity - (*)
Classes marked with "*" (star) are appropriate for any CSD doctoral or 5th year master's student.

This course will take a random walk through various mathematical topics that come in handy for theoretical computer science. It is intended mainly for students earlier in their graduate studies (or very strong undergraduates) who want to do theory research. The idea for the course comes from other courses by Arora (2002, 2007), Håstad (2004/05), Kelner (2007, 2009), and Tulsiani (2013). Students should have a solid undergraduate background in math (e.g., elementary combinatorics, graph theory, discrete probability, basic algebra/calculus) and theoretical computer science (running time analysis, big-O/Omega/Theta, P and NP, basic fundamental algorithms).

Key Topics
The course will have 7 units of about 4 lectures each, on the following topics in CS Theory: Asymptotics and Probability; Fourier Transforms; Algebra and Applications; Spectral Graph Theory; CSPs and Hierarchies; Information and Communication; Hardness.

Learning Resources
http://www.cs.cmu.edu/~odonnell/papers/cs-theory-toolkit-lecture-notes.pdf
https://www.youtube.com/playlist?list=PLm3J0oaFux3ZYpFLwwrlv_EHH9wtH6pnX

Course Relevance
PhD students in CSD are the main audience. Also expected are PhD students from other SCS departments, CSD Master's students, and CS seniors.

Course Goals
The goal of this class is to provide students with the tools needed to be able to read and participate in contemporary research in theoretical computer science. The main focus will be on learning fundamental CS Theory concepts and mathematical tools. Students should learn to apply basic techniques in asymptotic and probabilistic analysis. They should gain familiarity and comfort with a wide variety of tools in theoretical computer science, including analysis of Boolean functions, error-correcting codes, pseudorandomness, graph expansion, information theory, and communication complexity. They will learn applications of linear programming and semidefinite programming in constraint satisfaction problems, with a view from proof complexity. They will also be exposed to different computational intractability assumptions, and learn how they are applied. A secondary focus of the course will be developing good practices in mathematical writing and good research habits. A goal for the students will be to improve their facility with LaTeX and their ability to write clear correct proofs.

Pre-required Knowledge
Mathematical maturity, proof-writing skills. Must have had an A in 15-451.

Assessment Structure
95% Homework
5% Participation

Course Link
https://www.cs.cmu.edu/~odonnell/toolkit20