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.)
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).

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.