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

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.

References

  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.