# Toolkit for Theoretical Computer Science

## Lecture notes

Lecture notes/references will be posted here.

**2018-10-04—2018-10-18**.*Introduction to Spectral graph theory*. (PH)- See also Daniel Spielman’s course.
- HTML output of class demo. Code file for the demo, partly based on programs and tools developed by Daniel A. Spielman.

**2018-09-17—2018-10-04**.*The Multiplicative Weights Update Method*. (PH)- See AHK12.

**2018-09-10**.*Strong duality and constraint qualifications. Introduction to primal-dual methods.*(PS)**2018-08-28—2018-09-06**.*Convex sets and duality*. (PS)**2018-08-21—2018-08-28**.*Linear and semi-definite programs. Introduction to rounding procedures.*(PS)- See Approximation Algorithms, especially Chapters 12, 16 and 26.

**2018-08-14—2018-08-21**.*The Alon-Matias-Szegedy algorithm for computing moments of data streams. Basic concentration inequalities*. (PS)Please note that the notes are

*extremely*rough.Code implementing a version of the AMS algorithm. You need NTL and a modern C++ compiler (support for C++14 should be sufficient) to compile. Run

`make all`

in the directory in which the contents of the archive are extracted to compile. You can run the executables to get usage messages: both

`ams`

and`exact`

read their input from the standard input.

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

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

**Homework 2**. Due October 16, 2018. Last update version hash:`c072630`

, September 25.**Homework 1**. Due September 11, 2018. Last updated version hash:`b2763b3`

, August 29.

## References

*Approximation Algorithms*. V. V. Vazirani.*The Multiplicative Weights Update Method: a Meta-Algorithm and Applications*. S. Arora, E. Hazan, S. Kale.