# Toolkit for Theoretical Computer Science

## Lecture notes

Lecture notes/references will be posted here.

• 2018-12-19. Student presentations.

• 2018-12-04–2018-12-06. Treewidth and associated notions. (PH)

• Ref: Lecture notes by U. Feige and R. Krauthgamer for an Advanced Algorithms Course at the Weizmann Institute.
• 2018-11-29. Sketch of Marton’s proof of Talagrand’s convex distance inequality. (PS)

• 2018-11-27. Marton’s transportation cost method. Pinsker’s inequality and the Hoeffding lemma. Talagrand’s proof of the Gaussian concentration inequality via Marton’s method. (PS)

• 2018-11-22. Functional inequalities (contd.). Brief sketch of the proofs of Log-sobolev inequalities (without the base case). Connections with transportation-cost inequalities. (PS)

• 2018-11-20. Functional inequalities and concentration. The Herbst argument. Sub-additivity and convexity of the variance and entropy functionals. (PS)

• Ref: For references on the impromptu discussion we had on the connections between Log-Sobolev inequalities, hypercontractivity and the mixing properties of associated Markov chains, see the monograph Lectures on finite Markov chains by Laurent Saloff-Coste.
• 2018-11-15. Introduction to Gaussian concentration. Robust versions of the Johnson-Lindenstrauss Lemma. (PS)

• 2018-11-13. Review of basic concentration inequalities. Sub-Gaussian and sub-Gamma tails. The Johnson-Lindenstrauss embedding for a finite metric space. (PS)

• 2018-11-08. Polynomial and linear algebraic methods. (PH)

• Capset Problem. Ref: Lecture Notes from Tibor Szabó and Anurag Bishnoi, Extremal Combinatorics and its Methods, F. U Berlin, (Winter 2017-2018).

• Berlekamp-Welch Algorithm. Ref: Lecture Notes from Madhu Sudan, Essential Coding Theory, Harvard (Spring 2017).

• 2018-11-05. Linear algebraic methods. (PH)

• 2018-11-01. Introduction to the polynomial method: the Schwartz-Zippel Lemma and Combinatorial Nullstellensatz). (PH)

• 2018-10-25—2018-10-30. Spectral algorithms based on zeros of polynomials. Rank-one updates to matrices. The Batson-Spielman-Srivastava sparsifier. (PS)

• 2018-10-23—2018-10-25. Introduction to the singular value decomposition. k-variance clustering. (PS)

• 2018-10-04—2018-10-18. Introduction to Spectral graph theory. (PH)

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

• 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)

• 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 bash 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

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 3. Due November 15, 2018. Last updated version hash: 27c59b0, October 31.

• 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

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.