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

Time: Mon-Wed 09:30-11:00
Location: Zoom and Live Youtube Streaming
Instructors: and
Homepage: http://www.tifr.res.in/~prahladh/teaching/2020-21/toolkit

In view of the suspension of all in-class lectures due to the COVID-19 precautionary measure, all classess will be held in the distance model via Zoom.

The online lectures will be both transcribed and recorded. The online transcripts are available below as pdfs while the videos will be available on the STCS TIFR Youtube Channel .

Online Videos of Lectures

Problem Sets and Exams

1. PS1 [ (out: 22 Feb, due: 8 Mar) ]
2. PS2 [ (out: 16 Mar, due: 5 Apr) ]
3. PS3 [ (out: 7 May, due: 26 May) ]
4. PS4 [ (out: 3 Jun, due: 18 Jun) ]

Lectures

1. Out of Memory (15 Feb: )
   [ Notes ]
2. Concentration and Memory (part I) (17 Feb: )
   [ Notes ]
3. Concentration and Memory (part II) (22 Feb: )
   [ Notes ]
4. Sketching: pseudorandomness and concentration (24 Feb: )
   [ Notes ]
5. Games and Linear Programming (1 Mar: )
   [ Notes ]
6. Strong Duality (part I) (3 Mar: )
   [ Notes ]
7. Strong Duality (part II) (8 Mar: )
   [ Notes ]
8. LP Duality, von-Neumann minmax, Hardcore distributions (10 Mar: )
   [ Notes ]
9. Hardcore distributions, SDPs (15 Mar: )
   [ Notes ]
10. Some basic tools of Matrix Analysis (Part I) (17 Mar: )
    [ Notes, Notes on PSD matrices ]
11. Basic Matrix Analysis (Part II) (22 Mar: )
    [ Notes ]
12. Matrix Concentration Inequalities (24 Mar: )
    [ Notes ]
13. Matrix Bernstein Inequality and an Application (31 Mar: )
    [ Notes ]
14. More Matrix Concentration (5 Apr: )
    [ Notes ]
15. Multiplicative Weight Update Method (part I: Introduction, weighted majority) (7 Apr: )
    [ Notes ], Ref: [ AHK (Sec 1-2), GO (Lec 17), VR (Lec 4) ]
16. Multiplicative Weight Update Method (part II: Analysis of MWUM, Bregman projections) (12 Apr: )
    [ Notes, demo ], Ref: [ AHK (Sec 2) ]
17. Multiplicative Weight Update Method (part III: Approximately solving zero-sum games and LPs) (19 Apr: )
    [ Notes ], Ref: [ AHK (Sec 3.2-3.3), GO (Lec 17) ]
18. Multiplicative Weight Update Method (part IV: Approximately solving LPs and Boosting) (21 Apr: )
    [ Notes ], Ref: [ AHK (Sec 3.3 and 3.6), GO (Lec 17) ]
19. Multiplicative Weight Update Method (part V: Hardcore set lemma and Yao's XOR Lemma) (26 Apr: )
    [ Notes ], Ref: [ AHK (Sec 3.7), AB (Lec 19.1.1) ]
20. Spectral Methods (part I: Adjacency Matrix, Laplacian, eigenvalues and eigenvectors) (30 Apr: )
    [ Notes ], Ref: [ Spi, Jupyter Notebook (source code) ]
21. Spectral Methods (part II: Wilf's thm, Hoffman Bound, Hall's drawing of graphs) (5 May: )
    [ Notes ], Ref: [ Spi, Jupyter Notebook (source code) ]
22. Spectral Methods (part III: Cayley Graphs, Random Walk Matrix) (7 May: )
    [ Notes ]
23. Spectral Methods (part IV: Random Walk Matrix, convergence, expander mixing lemma) (10 May: )
    [ Notes ]
24. Spectral Methods (part V: Cheeger's Inequalities) (12 May: )
    [ Notes ]
25. Spectral Methods (part VI: Cheeger's Inequalities, Expander graphs) (17 May: )
    [ Notes ]
26. Spectral Methods (part VII: Expander graphs) (25 May: )
    [ Notes ]
27. Lovasz's Theta Function (part I) (26 May: )
    [ Notes ]
28. Lovasz's Theta Function (part II) (31 May: )
    [ Notes ]
29. Polynomial Method: Reed-Solomon Codes (2 Jun: )
    [ Notes ]
30. Polynomial Method: Polynomial Identity Lemma and Combinatorial Nullstellensatz (7 Jun: )
    [ Notes ]
31. Polynomial Method: Frankl Wilson Theorem and Intro to VC dimension (9 Jun: )
    [ Notes ], Ref: [ Bab, PA (Chap 15)]
32. VC Dimension: Sauer-Shelah Lemma and epsilon nets (14 Jun: )
    [ Notes ], Ref: [ PA (Chap 15)]

Tentative schedule

1. Basic probability inequalities. Applications to sketching and streaming. The role of pseudorandomness. (PS: 3 lectures, 15-22 Feb)
2. Linear and Semidefinite programming. Rounding. Duality. Algorithmic and analytic applications. (PS: 6 lectures 24 Feb-15 Mar)
3. Basic Matrix analysis: properties of semidefinite matrices, concentration for matrix valued random variables. (PS: 4 lectures, 17 Mar-31 Mar)
4. The multiplicative weight update method and its applications. (PH: 4 lectures, 5-14 Apr)
5. Spectral methods: Eigenvalue decomposition, Cheeger’s inequality, singular value decomposition (PH: 5 lectures, 19 Apr-3 May)
6. Polynomial linear algebraic methods with applications to combinatorics, coding theory (PH: 3 lectures, 5-12 May)
7. VC dimension (new) (PH: 2 lectures, 17-19 May)
8. Introduction to oracle models of optimization. (PS: 2 lectures, 24-31 May)
9. Treewidth (PH: 2 lectures, 2-7 Jun)

Requirements

Students taking the course for credit will be expected to:

• Do problem sets (approx 1 pset every 2-3 weeks)
• Give the final exam
• Give one presentation and/or in-class quizzes
• Grading Policy:
  • Problems Sets - 50% (best 4 of 5 psets will contribute towards grade)
  • Quizzes - 10%
  • Presentation / In-class quizzes - 10%
  • In-class Final Exam - 30%

References

Previous avatars of this course: 2018

This page has been accessed at least times since 17 March, 2021.