CSS.205.1: Toolkit for Theoretical Computer Science - Winter/Summer Semester (2022-23)

Time: Tue-Thurs 09:30-11:00
Location: A201
Instructors: and
Homepage: https://www.tifr.res.in/~prahladh/teaching/2022-23/toolkit

Course Announcement

Problem Sets Lectures Projects References

Problem Sets and Exams

  1. PS1 [ (out: 31 Jan, due: 14 Feb) ]
  2. PS2 (corrected) [ (out: 21 Feb, due: 9 Mar) ]
  3. PS3 [ (out: 30 Mar, due: 13 Apr) ]
  4. PS4 (corrected) [ (out: 27 Apr, due: 11 May) ]
  5. Final Exam (16 May, 9:30-12:00)
  6. Project Presentations (18-19 May, 14:00-17:00)

Lectures

  1. 2023-01-17 Out of Memory ()
    [Notes (from 2021)]
  2. 2023-01-19 Concentration inequalities for sums of "well-behaved" independent random variables ()
    [Notes (from 2021)]
  3. 2023-01-24 No class at the usual time due to a talk at the same time by Justin Gilmer. Please try to attend the talk! We will have a make up class 2PM-4PM on Friday, January 27 4PM-530PM on Tuesday, January 24.
    Hoeffding ineqality and the median trick. Reducing storage using \(k\)-wise independence. Construction of \(n\) pairwise independent bits using \(O(\log n)\) storage. Quick introduction to finite fields. ()
    [Notes (from 2021)]

    2023-01-26 No class (Republic Day ).

  4. 2023-01-31 No class at the usual time due to a talk at the same time by Nikhil Kumar. Please try to attend the talk! We will have a make up class 4PM-5:30PM.
    Construction of \(4\)-wise independent bits using finite field arithmetic in \(\mathbf{F}_{2^d}\). Prototype implementation of AMS. Two-player zero-sum games. ()
    [Notes (from 2021)]
    [Code for AMS]
  5. 2023-02-02 Two-player zero sum games with mixed strategies. Separating hyper plane theorem. Strong duality for linear programs. Proof of von Neumann minmax theorem for two-player zero sum games as an example. ()
    [Notes 1 (from 2021), Notes 2 (from 2021), Notes 3 (from 2021)]
  6. 2023-02-07 An application in complexity theory: the Impagliazzo hard core set lemma. Convex programs in more generality. A special case: semi-definite programs. ()
    [Notes (from 2021)]; Ref: [ Imp (Lemma 2) ] See also [ Tre (Comments) ]
  7. 2023-02-09 Duality theory in more generality. Semi definite programs and their duals. The Lagrangian dual. A simple example: the max-entropy program and its dual. ()
    [Transcript (includes material form next lecture)]
  8. 2023-02-14 The max-entropy program (contd.). Proof of strong duality for the Lagrangian dual under Slater's constraint qualification. ()
    [Transcript (includes material form previous lecture)]
    See also [ BV (Chapter 5) ] for more examples.
  9. 2023-02-16 Multiplicative Weight Update Method I ()
    Introduction, weighted majority algorithm, MWUM algorithm
    [Notes(from 2021)]; Ref: [ AHK (Sec 1-2), GO (Lec 16), VR (Lec 4) ]
  10. 2023-02-21 Multiplicative Weight Update Method II ()
    Analysis of MWUM algorithm, Formulation in terms of relative entropy via Bregman projections
    [Notes (from 2021)]; Ref: [ AHK (Sec 2) ]
  11. 2023-02-23 Multiplicative Weight Update Method III ()
    Approximately solving zero-sum games and Linear-programs
    [Notes (from 2021); demo]; Ref: [ AHK (Sec 3.2-3.3), GO (Lec 17) ]
  12. 2023-02-28 Multiplicative Weight Update Method IV ()
    Approximately solving zero-sum Linear-programs and Introduction to Boosting
    [Notes1, Notes2 (from 2021)]; Ref: [ AHK (Sec 3.3 and 3.6), GO (Lec 17) ]
  13. 2023-03-02 Multiplicative Weight Update Method V ()
    Boosting, Constructive proof of Impagliazzo's Hardcore set lemma; Yao's XOR Lemma
    [Notes1, Notes2 (from 2021)]; Ref: [ AHK (Sec 3.3 and 3.6), AB (Sec 19.1.1) ]

    14. 2023-03-07 No class (Holi/Dhuḷwaḍ).

  14. 2023-03-09 Basic matrix analysis: the singular value decomposition and low-rank approximation. ()
    [Notes (from 2021)]
  15. 2023-03-14 Basic matrix analysis: low-rank approximation in the Frobenius norm. Basic properties of PSD matrices. Functions on PSD matrices. ()
    [Notes (from 2021)]
    [Some notes on inequalities for PSD matrices]
  16. 2023-03-16 Trace inequalities. Lieb's concavity theorem. The Laplace transform method applied to matrices. ()
    [Notes (from 2021)] (See also the notes for the previous class.)
  17. 2023-03-21 Proof of the Matrix Bernstein inequality. Application to covariance estimation. ()
    [Notes (from 2021)] (See also the notes for the previous class.)
  18. 2023-03-23 Matrices with random entries. \(\epsilon\)-net based analyses for the condition number of random matrices. Random subspaces. ()
    [Notes (from 2021)]
  19. 2023-03-28 Spectral Methods I ()
    Spectral Theorem, Eigenspectrum of Adjacency Matrix, Wilf's bound
    [Notes1, Notes2 (from 2021)]; Ref: [ Spi ]
  20. 2023-03-30 Spectral Methods II ()
    Hoffman Bound, Eigenspectrum of Laplacian Matrix
    [Notes1, Notes2 (from 2021)]; Ref: [ Spi ]

    2023-04-04 No class (Mahaveer Jayanti).

  21. 2023-04-06 Spectral Methods III ()
    Hall's spectral drawing of graphs, Eigenspectrum of simple graphs, Cayley Graphs and their eigenspectrum
    [Notes1, Notes2 (from 2021)]; Ref: [ Jupyter notebook (html, ipnyb), Spi ]
  22. 2023-04-11 Spectral Methods IV ()
    Random walk matrix, reversibility, eigenspectrum, convergence
    [Notes1, Notes2 (from 2021)]; Ref: [Spi]
  23. 2023-04-13 Spectral Methods V ()
    Random walk matrix, expander mixing lemma, Cheeger inequalities (proof of easy direction)
    [Notes1, Notes2 (from 2021)]; Ref: [Spi]
  24. 2023-04-18 Spectral Methods VI ()
    Cheeger inequalities (proof of hard direction), Fieldler's algorithm
    [Notes (from 2021)]; Ref: [Spi]
  25. 2023-04-20 Introduction to black box methods in optimization: Gradient Descent ()
    [Transcript], based almost entirely on Chapters 1 and 2 of Nesterov [Nes].
    See also the monograph by Bubeck [Bub].
  26. 2023-04-25 Introduction to black box methods in optimization: Nesterov's Accelerated Gradient Descent ()
    [Transcript], based almost entirely on Chapters 1 and 2 of Nesterov [Nes].
    See also the monograph by Bubeck [Bub].
  27. 2023-04-27 Expander Graphs I ()
    Different notions of expansion (spectral, combinatorial), Spectral gap implies vertex expansion, Explicit family of expander graphs, Ramanujan graphs
    [Notes1, Notes2 (from 2021)].
  28. 2023-05-02 Expander Graphs II ()
    Hitting Set Lemma for expanders; Introduction to polynomial method: degree method, Reed-Solomon codes, Singleton Bound
    [Notes1, Notes2 (from 2021)].
  29. 2023-05-04 Polynomial and Linear Algebraic Method I
    Unique Decoding of Reed-Solomon codes (Welch-Berlekamp algorithm), Schwartz-Zippel Lemma and application to bipartite matching, Combinatorial Nullstellensatz and application to Cauchy-Davenport Theorem
    [Notes1, Notes2 (from 2021)]
  30. 2023-05-09 Polynomial and Linear Algebraic Method II
    Proof of Combinatorial Nullstellsatz, VC-dimension: Introduction and examples, Sauer-Shelah Lemma
    [Notes1, Notes2, Notes3 (from 2021)]

Tentative Schedule

Requirements

Students taking the course for credit will be expected to:

Projects

Potential topics for projects and paper presentation

References

[AB] Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. [ .html | doi ]
[AHK] Sanjeev Arora, Elad Hazan, and Satyen Kale. The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory Comput. 8(1): 121-164 (2012) [ doi ]
[BV] Stephen Boyd, Lieven Vandenberghe. Convex Optimization. Cambridge University Press. (2004). [ doi | pdf ]
[Bub] Sébastien Bubeck: Convex Optimization: Algorithms and Complexity. Now Publishers. [ doi | arXiv ]
[Cha] Sourav Chatterjee: Concentration inequalities with exchangeable pairs (Ph.D. thesis) [ arXiv ]
[GO] Anupam Gupta and Ryan O'Donnell. 15-859(E): Linear and Semidefinite Programming (Advanced Algorithms) Fall 2011 A course offered at CMU. [ .html ]
[GRS] Venkatesan Guruswami, Atri Rudra and Madhu Sudan, "Essential Coding Theory", (draft of book), 2022.
[Imp] Russell Impagliazzo: Hard-Core Distributions for Somewhat Hard Problems. FOCS 1995: 538-545 [ doi | ps ]
[Mat] Jiri Matousek, Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra, American Mathematical Society, 2010. [pdf]
[Nes] Yurii Nesterov: Lectures on Convex Optimization. Springer. [ doi ]
[RV] Satish Rao and Umesh Vazirani. CS270: Combinatorial Algorithms and Data Structures Spring 2012 A course offered at Univ California, Berkeley. [ .html ]
[Spi] Dan Spielman. Spectral and Algebraic Graph Theory (draft of book), 2019. [ .html ]
[Tre] Luca Trevisan. The Impagliazzo Hard-Core-Set Theorem, blogpost in Blog In Theory, Nov 2007. [ .html ]

Previous versions of this course: 2021 and 2018

This page has been accessed at least Counter times since 9 January 2023.

Prahladh Harsha