Toolkit for Theoretical Computer Science

Outline Notes References Assignments

Lecture notes

Lecture notes/references will be posted here.

General information

Instructors: Prahladh Harsha & Piyush Srivastava

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

The following is a tentative schedule for the class.

Additional topics that might (not) be covered


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.


  1. Approximation Algorithms. V. V. Vazirani.

  2. The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. S. Arora, E. Hazan, S. Kale.

  3. Concentration Inequalities. Stéphane Boucheron, Gábor ugosi, Pascal Massart.