15-859T: A Theorist's Toolkit 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.
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 --…
saved by
related reading
- 15-855: Graduate Computational Complexity Theory, Fall 2017cs.cmu.edu
- Theory at Berkeleytheory.cs.berkeley.edu
- 15-859BB: Quantum Computation and Quantum Information 2018cs.cmu.edu
- Algorithmic Game Theory (CS364A), Fall 2013timroughgarden.org
- Study Guide — LessWronglesswrong.com
- CSE 599 Recent Developments in Approximation Algorithmshomes.cs.washington.edu
- Tim Roughgarden's Lecture Notestimroughgarden.org
- Fall 2026boazbk.github.io
- COMP 598 Fall 2020 - Proof Complexitycs.mcgill.ca
- CSE 599 Counting and Samplinghomes.cs.washington.edu
- 275A, Notes 0: Foundations of probability theory | What's newterrytao.wordpress.com
- Logic in Computer Sciencecourses.grainger.illinois.edu