# Toolkit for Theoretical Computer Science

## General information

**Instructors:** Prahladh Harsha & Piyush Srivastava

**Schedule:** Tuesdays and Thursdays, 1130-1300, A-201.

The following is a tentative schedule for the class.

**2018-08-14—2018-08-21**.*Basic probability inequalities. Applications to sketching and streaming. The role of pseudorandomness. (3 lectures)***2018-08-23—2018-08-30**.*Linear and Semi-definite programming. Rounding. (3 lectures)***2018-09-04—2018-09-18**.*Duality. Algorithmic and analytic applications. (4 lectures)***2018-09-25—2018-10-09**.*The multiplicative weight update method and its applications. (4 lectures)***2018-10-11—2018-10-25**.*Spectral methods. (5 lectures)***2018-10-30—2018-11-01**.*Polynomial methods. (2 lectures)***2018-11-06—2018-11-20**.*Concentration of measure and applications. (4 lectures)***2018-11-22—2018-11-29**.*Lattice problems in algorithms and complexity. (3 lectures)***2018-12-04**.*Tree-width and related algorithmic ideas. (1 lecture)*

### Additional topics that might (not) be covered

- Fast linear system solvers
- Topics from convex geometry

## Lecture notes

Lecture notes/references will be posted here.

## Grading/Assignments

There will be four homework assignments, to be assigned (roughly) toward the end of the months from August to November. The first assignment will be a “warm-up” centered around some preliminaries.