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

- Ref: Lecture notes by U. Feige and R. Krauthgamer for an Advanced Algorithms Course at the Weizmann Institute.
**2018-11-29**.*Sketch of the proof 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.

- 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
**2018-11-15**.*Introduction to Gaussian concentration. Robust versions of the Johnson-Lindenstrauss Lemma.*(PS)- Ref:
*Concentration Inequalities*, and M. Ledoux,*The concentration of measure phenomenon*.

- Ref:
**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)*Babai’s proof of the Ray-Chaudhuri-Wilson inequality*. Ref: L. Babai, A short proof of the nonuniform Ray-Chaudhuri-Wilson inequality,*Combinatorica*,**8**, pp. 133–135 (1988).*The Shattering Lemma*. Ref: J. Matoušek (1999),*VC-Dimension and Discrepancy*. In: Geometric Discrepancy. Algorithms and Combinatorics, vol 18. Springer.

**2018-11-01**.*Introduction to the polynomial method: the Schwartz-Zippel Lemma and Combinatorial Nullstellensatz)*. (PH)- See S. Jukna,
*Polynomial Method*.

- See S. Jukna,
**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)- See also the book
*Spectral Algorithms*by Kannan and Vempala.

- See also the book
**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 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

*Approximation Algorithms*. V. V. Vazirani.*The Multiplicative Weights Update Method: a Meta-Algorithm and Applications*. S. Arora, E. Hazan, S. Kale.*Concentration Inequalities*. Stéphane Boucheron, Gábor ugosi, Pascal Massart.