Lecture: Monday/Wednesday 5:00-6:30pm
Instructor: Prasad Raghavendra
Office hours: Tuesday 2:30-3:30pm (zoom link in piazza)
TA: Emaan Hariri
Office hours: Thursday 2:00-3:00pm (zoom link in piazza)
(Jan 20) Gradient Descent and its variants (scribe notes)(board) (video)
section 2.1-2.6 in book by Nisheeth Vishnoi for mathematical preliminaries.
(Jan 25) Mirror Descent and multiplicative weights (scribe notes)(board) (video)
Proof of projected gradient descent (Theorem 3.2 in Bubeck's book)
(Jan 27) NO LECTURE
(Feb 1) Mirror Descent, Online Convex Optimization, Solving LPs via online convex optimization. (scribe notes)(board)(video)
Proof of Mirror descent (Theorem 4.2 in Bubeck's book)
(Feb 3) Centroid and Ellipsoid Algorithm (scribe notes) (board) (video)
(Feb 8) Solving linear systems, Preconditioninng, PCA, SVD, Power method (scribe notes) (board) (video)
Chapter 3 in Blum-Hopcroft-Kannan
Chapter 15 in Vishnoi's book
Conjugate Gradient Descent in Chapter 16 of Vishnoi's book
(Feb 10) Applications of PCA: Gaussian Mixtures, Robust Mean estimation. (scribe notes) (board) (video)
Chapter 3 in Blum-Hopcroft-Kannan
Section 2.1,2.2,2.3 in survey by Diakonikolas-Kane
(Feb 17) Robust Mean Estimation, Tensors. (scribe notes) (board) (video)
Section 2.1,2.2,2.3 in survey by Diakonikolas-Kane
Chapter 3 in Moitra's book
(Feb 22) Tensors, Jenrich's algorithm, Independent component analysis. (scribe notes) (board) (video)
Chapter 3 in Moitra's book
(Feb 24) Dimension Reduction, Johnson-Lindenstrauss, Oblivious subspace embeddings. (scribe notes) (board) (video)
Section 10.2,10.3, 10.4 in Anupam Gupta's notes
Section 2.1 in David Woodruff's survey
(Mar 1) Compressed sensing, RIP property. (scribe notes) (board) (video)
Section 2.8 in Matousek's lecture notes on metric embeddings
(Mar 3) Nearest neighbors, Locality sensitive hashing. (scribe notes) (board) (video)
lecture 16 and lecture 17 from Moses Charikar's class.
Section 2.9 in Matousek's lecture notes on metric embeddings
(Mar 8) Low-diameter decompositions and HSTs (scribe notes) (board) (video)
Lecture 5 in Anupam Gupta's course.
(Mar 10) Graph expansion, uniform sparsest cut and Bourgain's embedding. (scribe notes) (board) (video)
section 4.2,4.3 in Matousek's lecture notes on metric embeddings.
(Mar 15) Cheeger's Inequality. (scribe notes) (board)(video)
Chap 2, Chap 21 in Spielman's book on spectral graph theory.
(Mar 17) Second eigenvalue of planar graphs, random walks, s-t connectivity. (scribe notes) (board) (video)
Chap 25 in Spielman's book on spectral graph theory.
scribe notes from Williamson's class.
(March 30) Effective resistances, commute times.(board) (scribe notes) (video)
scribe notes from Williamson's class.
(April 1) Solving Laplacian systems (board) (scribe notes) (video)
Chap 14 from Vishnoi's book.
(April 6) Approximate maximum flow in undirected graphs (board) (scribe notes) (video)
Lec 15 from Anupam Gupta's course.
(April 8) Semidefinite programming, Maximum cut (board) (scribe notes) (video)
Section 6.1,6.2 in Shmoys-Williamson book
(April 12) Sum-of-Square SDP Hierarchy (board) (scribe notes) (video)
(April 14) Duality, Sum-of-squares proofs (board) (scribe notes) (video)
(April 19) SoS Application: Robust linear regression. (board) (video)
Scribe notes from SoS SDP class (link)
(April 21) Linear programming, Integrality of polytopes, Iterative rounding, Bounded degree spanning tree (board) (scribe notes) (video)
Section 3.1, 4.1 and 4.3 in book by Lau, Ravi and Singh.
(April 26) Perfect Matchings: polyhedral and algebraic techniques. (board) (scribe notes) (video)
(April 28) Property Testing, sortedness, maximal matching (board) (scribe notes) (video)
Lecture from Nick Harvey's class.
(May 3) Lovasz local lemma, Moser's algorithm. (board) (video)
(lecture 18) and (lecture 19) from Nick Harvey's class.
Regular bi-weekly homeworks (collaboration allowed): 35%
1 take-home final (collaboration prohibited): 25%
Scribe 1 lecture: 10%
Project: In groups of 2 or 3, write a survey on an area of active research : 30%