15-859T: A Theorist's Toolkit 2013
Meetings time and place: Monday and Wednesday, 3pm-4:20pm, GHC 5222.
Instructor: Ryan O'Donnell
TA: Ameya Velingker
Office Hours: Ryan, GHC 7213, by appointment; Ameya, Thursdays 4--5pm in GHC 6211
Course bulletin board: Piazza
Scribe notes
(Scribes will be de-anonymized at the end of the semester.)
- Lecture 01 -- Asymptotics (Misha Lavrov scribe notes, lecture draft)
- Lecture 02 -- Central Limit Theorem (Yu Zhao scribe notes, lecture draft)
- Lecture 03 -- Chernoff bounds (Elara Willett scribe notes, lecture draft)
- Lecture 04 -- How to do math (slides .pdf, slides .pps)
- Lecture 05 -- Computational models (Guru Guruganesh scribe notes, lecture draft)
- Lecture 06 -- Spectral graph theory I (Jennifer Iglesias scribe notes, lecture draft)
- Lecture 07 -- Spectral graph theory II (Christian Tjandraatmadja scribe notes, lecture draft)
- Lecture 08 -- Spectral graph theory III (Jeremy Karp scribe notes, lecture draft)
- Lecture 09 -- Fields and polynomials (Kevin Su scribe notes, lecture draft)
- Lecture 10 -- Error correcting codes (Xiaowen Ding scribe notes, lecture draft)
- Lecture 11 -- Derandomization (Linus Hamilton scribe notes, lecture draft)
- Lecture 12 -- Expanders (Aleksandr Kazachkov scribe notes, lecture draft)
- Lecture 13 -- Linear programming I (Yuting Ge scribe notes, lecture draft)
- Lecture 14 -- Linear programming II (Stylianos Despotakis scribe notes, lecture draft)
- Lecture 15 -- Semidefinite programming (Michael Nugent scribe notes, lecture draft)
- Lecture 16 -- Constraint satisfaction problems (Neal Barcelo scribe notes, lecture draft)
- Lecture 17 -- Treewidth (Thomas Swayze scribe notes, lecture draft)
- Lecture 18 -- Analysis of Boolean functions (Sarah Allen scribe notes, lecture draft)
- Lecture 19 -- Communication complexity (Livia Ilie scribe notes, lecture draft)
- Lecture 20 -- Information theory (Kevin Su scribe notes, lecture draft)
- Lecture 21 -- LP hierarchies and proof complexity (lecture draft)
- Lecture 22 -- Quantum computation (Elara Willett scribe notes). Lecture by John Wright. Thanks John!
- Lecture 23 -- Cryptography (Linus Hamilton scribe notes, lecture draft)
- Lecture 24 -- Hardness assumptions (Jeremy Karp scribe notes, lecture draft)
- Lecture 25 -- Sketch of the PCP Theorem (Ben Cousins scribe notes, lecture draft)
Course description
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).
Prerequisites
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). Mathematical maturity is a must.
Suggested text
The Nature of Computation by Cris Moore and Stephan Mertens.