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
.
VIDEO
PS1 [ (out: 22 Feb, due: 8 Mar) ]
PS2 [ (out: 16 Mar, due: 5 Apr) ]
PS3 [ (out: 7 May, due: 26 May) ]
PS4 [ (out: 3 Jun, due: 18 Jun) ]
Out of Memory
(15 Feb: )
[ Notes ]
Concentration and Memory (part I) (17 Feb: )
[ Notes ]
Concentration and Memory (part II) (22 Feb: )
[ Notes ]
Sketching: pseudorandomness and concentration
(24 Feb: )
[ Notes ]
Games and Linear Programming
(1 Mar: )
[ Notes ]
Strong Duality (part I)
(3 Mar: )
[ Notes ]
Strong Duality (part II)
(8 Mar: )
[ Notes ]
LP Duality, von-Neumann minmax, Hardcore
distributions
(10 Mar: )
[ Notes ]
Hardcore distributions, SDPs
(15 Mar: )
[ Notes ]
Some basic tools of Matrix Analysis (Part I)
(17 Mar: )
[ Notes , Notes on PSD matrices ]
Basic Matrix Analysis (Part II)
(22 Mar: )
[ Notes ]
Matrix Concentration Inequalities
(24 Mar: )
[ Notes ]
Matrix Bernstein Inequality and an Application
(31 Mar: )
[ Notes ]
More Matrix Concentration
(5 Apr: )
[ Notes ]
Multiplicative Weight Update Method (part I: Introduction,
weighted majority)
(7 Apr: )
[ Notes ], Ref: [ AHK (Sec 1-2), GO (Lec 17), VR (Lec 4) ]
Multiplicative Weight Update Method (part II: Analysis of
MWUM, Bregman projections)
(12 Apr: )
[ Notes , demo ], Ref: [ AHK (Sec 2) ]
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) ]
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) ]
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) ]
Spectral Methods (part I: Adjacency Matrix, Laplacian,
eigenvalues and eigenvectors)
(30 Apr: )
[ Notes ], Ref: [ Spi , Jupyter Notebook
(source code ) ]
Spectral Methods (part II: Wilf's thm, Hoffman Bound, Hall's
drawing of graphs)
(5 May: )
[ Notes ], Ref: [ Spi , Jupyter Notebook
(source code ) ]
Spectral Methods (part III: Cayley Graphs, Random Walk Matrix)
(7 May: )
[ Notes ]
Spectral Methods (part IV: Random Walk Matrix, convergence,
expander mixing lemma)
(10 May: )
[ Notes ]
Spectral Methods (part V: Cheeger's Inequalities)
(12 May: )
[ Notes ]
Spectral Methods (part VI: Cheeger's Inequalities, Expander graphs)
(17 May: )
[ Notes ]
Spectral Methods (part VII: Expander graphs)
(25 May: )
[ Notes ]
Lovasz's Theta Function (part I)
(26 May: )
[ Notes ]
Lovasz's Theta Function (part II)
(31 May: )
[ Notes ]
Polynomial Method: Reed-Solomon Codes
(2 Jun: )
[ Notes ]
Polynomial Method: Polynomial Identity Lemma and
Combinatorial Nullstellensatz
(7 Jun: )
[ Notes ]
Polynomial Method: Frankl Wilson Theorem and Intro to VC dimension
(9 Jun: )
[ Notes ], Ref: [ Bab , PA (Chap 15) ]
VC Dimension: Sauer-Shelah Lemma and epsilon nets
(14 Jun: )
[ Notes ], Ref: [ PA (Chap 15) ]
Tentative schedule
Basic probability inequalities. Applications to sketching and
streaming. The role of pseudorandomness. (PS: 3 lectures, 15-22 Feb)
Linear and Semidefinite
programming. Rounding. Duality. Algorithmic and analytic
applications. (PS: 6 lectures 24 Feb-15 Mar)
Basic Matrix analysis: properties of semidefinite matrices,
concentration for matrix valued random variables. (PS: 4 lectures,
17 Mar-31 Mar)
The multiplicative weight update method and its
applications. (PH: 4 lectures, 5-14 Apr)
Spectral methods: Eigenvalue decomposition, Cheeger’s
inequality, singular value decomposition (PH: 5 lectures, 19 Apr-3 May)
Polynomial linear algebraic methods with applications to
combinatorics, coding theory (PH: 3 lectures, 5-12 May)
VC dimension (new) (PH: 2 lectures, 17-19 May)
Introduction to oracle models of optimization. (PS: 2 lectures,
24-31 May)
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%
[AB ]
Sanjeev Arora and Boaz Barak.
Computational Complexity: A Modern Approach .
Cambridge University Press, 2009.
[ .html |
doi ]
[AHZ ]
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 ]
[Bab ]
László Babai: A short proof of the non-uniform Ray Chauhuri-Wilson inequality. Comb. 8(1): 133-135 (1988)
[ .doi ]
[GO ]
Anupam Gupta and Ryan O'Donnell.
15-859(E): Linear and Semidefinite Programming
(Advanced Algorithms) Fall 2011
A course offered at CMU.
[ .html ]
[PA ]
János Pach, Pankaj K. Agarwal.
Combinatorial Geometry .
Wiley-Interscience; 1st edition (1995)
[ doi ]
[Spi ]
Dan Spielman.
CPSC 662 / AMTH 561 : Spectral Graph Theory, Fall 2018.
A course on Spectral Methods offered at Yale University
[ .html ]
[VR ]
Umesh Vazirani and Satish Rao.
CS270: Combinatorial Algorithms and Data Structures Spring 2012
A course offered at Univ California, Berkeley.
[ .html ]
Previous avatars of this course: 2018
This page has been accessed at least
times since 17 March, 2021.