## 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**