15-751: A Theorist's Toolkit 2016
Meetings time and place: Monday and Wednesday, 3pm-4:20pm, GHC 4303.
First meeting: Wednesday, September 7.
Instructors: Ryan O'Donnell, Venkat Guruswami
TAs: Vijay Bhattiprolu, Yu Zhao
Office Hours: Vijay: Fridays 1-2:30, GHC 9003. Yu: Wednesdays, 4:30-6, GHC 7509. Ryan: Wednesdays, 1:15-2:30, GHC 7213. Venkat: Thursdays, 4:45-6, GHC 7211.
Course bulletin board: Piazza
Lecture 1 slides: .ppsx, .pdf
Homework
Homework 1 (due Monday Sept. 19)
Homework 2 (due Monday Sept. 26)
Homework 3 (due Monday Oct. 3)
Homework 4 (due Wednesday Oct. 12)
Homework 5 (due Monday Oct. 24)
Homework 6 (due Monday Nov. 7)
Homework 7 (due Friday Nov. 18)
Homework 8 (due Monday Dec. 5)
Take Home Final (due Sunday Dec. 11)
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.
Grading scheme
- 80% homework (likely to be 8 homeworks worth 10% each).
- 15% take-home final exam.
- 5% participation.
Resources