Home Research Teaching Contact

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)

  • Ref: Concentration Inequalities, and M. Ledoux, The concentration of measure phenomenon.

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

  • Ref: Concentration Inequalities.

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

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

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

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

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.

Acknowledgments Site generated by Hakyll