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

Time: Mon-Thurs 14:00-15:30
Location: A201
Instructors: and

Online Videos of Lectures: CSS.205.1 Toolkit for TCS 2025: YouTube Playlist

Problem Sets and Exams

1. Problem Set 1 (out: 13 Feb, due: 27 Feb)
2. Problem Set 2(out: 7 Mar, due: 21 Mar)
3. Problem Set 3 (out: 28 Mar, due: 11 Apr)
4. Problem Set 4 (out: 18 Apr, due: 2 May)
5. Final Exam (9 May)

Lectures

1. [22 Jan] Spectral Methods I (): Introduction, Administrivia, Graphs, Adjaceny and Laplacian Matrix, Spectral Theorem
   [Notes, YouTube Video, Jupyter notebook (ipnyb)]; Ref: [Spi (Chap 1-3)]
2. [29 Jan] Spectral Methods II (): Eigenspectrum of the Adjacency Matrix and Laplacian, Graph Colouring and Wilf's theorem, Hall's drawing of graphs
   [Notes, YouTube Video]; Ref: [Spi (Chap 3-4)]
3. [31 Jan] Spectral Methods III (): Cayley graphs, Random walk matrix
   [Notes, YouTube Video]
4. [3 Feb] Spectral Methods IV (): Random Walk Matrix (irreducibility, reversibility, eigenspectrum, convergence), Expander Mixing Lemma
   [Notes, YouTube Video]
5. [6 Feb] Spectral Methods V (): Cheeger's Inequalities
   [Notes, YouTube Video]
6. [10 Feb] Spectral Methods VI (): Cheeger's Inequalities (Contd), Expander Graphs: vertex and spectral expansion, examples of expander constructions
   [Notes, YouTube Video]; Ref: [Vad (Chap 7)]
7. [13 Feb] Spectral Methods VII (): Spectral expansion implies vertex expansion; Expander application: error reduction, hitting-set lemma
   [Notes, YouTube Video]; Ref: [Vad (Chap 7)]
8. [17 Feb] Spectral Methods VIII (): Zig-Zag expanders
   [Notes, YouTube Video]; Ref: [Vad (Chap 7)]
9. [20 Feb] Multiplicative-weight Update Method I (): Zig-Zag expanders (contd); weighted majority algorithm
   [Notes, YouTube Video]; Ref: [Vad (Chap 7), AHK (Sec 1)]
10. [25 Feb] Multiplicative-weight Update Method II (): weighted majority algorithm, MWUM algorithm and analysis
    [Notes, YouTube Video]; Ref: [AHK (Sec 1-2)]
11. [27 Feb] Multiplicative-weight Update Method III (): MWUM analysis in terms of relative entropy using Bregman's projection
    [Notes, YouTube Video]; Ref: [AHK (Sec 2.2)]
12. [3 Mar] Multiplicative-weight Update Method IV (): Applications of MWUM: approximating zero-sum games, boosting
    [Notes, YouTube Video]; Ref: [AHK (Sec 3.2 and 3.6)]
13. [6 Mar] Multiplicative-weight Update Method V (): Yao's XOR lemma and Impagliazzo's hardcore set lemma
    [Notes (from 2021), YouTube Video]; Ref: [AHK (Sec 3.7)]
14. [10 Mar] Linear-algebraic method I (): Frankl-wilson theorem, definition and statement of the Sauer-Shelah lemma
    [Notes 1, Notes 2 (from 2021), YouTube Video].
15. [13 Mar] Linear-algebraic method II (): Proof of Sauer-Shelah lemma, epsilon-nets and the epsilon-nets theorem.
    [Notes (from 2021).
16. [20 Mar (Morning lecture: makeup for March 17)] Concentration inequalities (I) (): The Alon-Matias-Szegedy (AMS) algorithm for streaming estimation of second moment. Deviation inequalities. The second moment, and the moment generating function.
    [Notes (including material covered in the next lecture)].
17. [20 Mar (Afternoon lecture)] Concentration inequalities (II) (): Sub-Gaussian random variables and the Hoeffding lemma. The Hoeffding inequality. Analysis of the AMS algorithm ignoring storage of randomness.
    [Notes (including material covered in the previous lecture)].
18. [24 Mar] \(k\)-wise independence (): Reducing randomness storage in the AMS algorithm using \(k\)-wise independence. Constructions of \(k\)-wise independence random variables.
    [Notes 1 (from 2021)] [Notes 2 (from 2021)].
19. [27 Mar] Linear programming (1) (): Two-player zero-sum games. Statement of the von-Neumann min-max theorem. Linear programming. Weak duality for linear programs. [Notes (from 2021)].
20. [3 Apr] Linear programming (2) (): The separating hyperplane theorem. Duality for closed convex cones. Farkas lemma. Proof of strong duality for linear programs. [Notes]
21. [7 Apr] Linear programming (3) (): Proof of the von-Neumann min-max theorem using LP duality. The "procedure" for writing duals. The Lagrangian dual. [Notes].
22. [17 Apr] Linear programming (4) (): Nisan's proof of the Impagliazzo hard-core distribution lemma using LP-duality. [Notes].
23. [21 Apr] Convex relaxations (): Semi-definite programming. SDP relaxation for MAX-CUT. [Notes].
24. [23 Apr] (Makeup class) Singular value decomposition (). [Notes].
25. [24 Apr] Positive semi-definite matrices (1) (). Basic properties. Operator monotonicity of matrix square root. Failure of operator monotonicity of matrix square. [Notes (pp. 1-6)].
26. [28 Apr] Positive semi-definite matrices (2) (). Introduction to trace inequalities. Statement of Lieb's theorem. Exponential moment method for matrix random variables. [Notes (pp. 6-15)].
27. [29 Apr] (Makeup class 1: 1030-1130) Positive semi-definite matrices (3) (). A (watered-down version of) the matrix Bernstein inequality. Sample complexity upper bounds for covariance estimation. [Notes (pp. 15-18)].
28. [29 Apr] (Makeup class 2: 1130-1300) Black-box optimization (1) (). Basic setup. Gradient descent for convex functions with Lipschitz gradients. [Notes], based almost entirely on Chapters 1 and 2 of Nesterov [Nes].
    See also the monograph by Bubeck [Bub].
29. [1 May] Black-box optimization (2) (). Accelerated gradient descent for convex functions with Lipschitz gradients. [Notes], based almost entirely on Chapters 1 and 2 of Nesterov [Nes].
    See also the monograph by Bubeck [Bub].

Tentative Schedule (for remaining lectures):

• [22 Jan-17 Feb] Spectral methods. (PH: 8 lectures)
• [20 Feb-6 Mar] The multiplicative weight update method and its applications.(PH: 5 lectures)
• [10-13 Mar] Linear-algebraic method in combinatorics and VC Dimension (MK: 2 lectures)
• [17-24 Mar] Basic probability inequalities. Applications to sketching and streaming. The role of pseudorandomness. (PS: 3 lectures)
• [27-21 Apr] Linear and Semi-denite programming. Rounding. Duality. Algorithmic and analytic applications. (PS: 5 lectures)
• [31 Mar] Eid ul-Fitr (Institute holiday)
• [10 Apr] Mahavir Jayanthi (Institute holiday)
• [14 Apr] Dr. B. R. Ambedkar Jayanti (Institute holiday)
• [23-29 Apr] Basic Matrix Analysis. (PS: 4 lectures)
• [29 Apr-1 May] Introduction to oracle models of optimization. (PS: 2 lectures)

Requirements

Students taking the course for credit will be expected to:

• Do problem sets (approx 1 pset every 3-4 weeks)
• Give the final exam
• Give one presentation and/or in-class quizzes
• Grading Policy:
  • Problems Sets - 60-75% (best 3 of 4 psets will contribute towards grade)
  • In-class Final Exam - 25%
  • Presentation / In-class quizzes - 0-15%

References

[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 ]

[Bub]

Sébastien Bubeck: Convex Optimization: Algorithms and Complexity. Now Publishers. [ doi | arXiv ]

[Nes]

Yurii Nesterov: Lectures on Convex Optimization. Springer. [ doi ]

[Spi]

Dan Spielman. Spectral and Algebraic Graph Theory (draft of book), 2025. [ .html ]

[Vad]

Salil Vadhan. Pseudorandomness, Found. Trends Theor. Comput. Sci., 7(1-3):1–336, 2012. [ .html | doi ]

Previous versions of this course: 2023, 2021 and 2018

This page has been accessed at least times since 7 January 2025.