CS 270. Combinatorial Algorithms and Data Structures, Spring 2021 (original) (raw)
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)
Lectures
Convex Optimization Tools
- (Jan 20) Gradient Descent and its variants (scribe notes)(board) (video)
- section 2.1-2.6 in book by Nisheeth Vishnoi for mathematical preliminaries.
- Notes from Anupam Gupta's course
- (Jan 25) Mirror Descent and multiplicative weights (scribe notes)(board) (video)
- Proof of projected gradient descent (Theorem 3.2 in Bubeck's book)
- Notes from Anupam Gupta's course
- (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)
- Notes from Anupam Gupta's course
- Chapter 7,Vishnoi's book
- (Feb 3) Centroid and Ellipsoid Algorithm (scribe notes) (board) (video)
Linear Algebraic Toolkit
- (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
Embeddings
- (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)
- Blog by James R Lee
- 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.
Spectral Graph Theory
- (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.
Semidefinite programming
- (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)
A few other topics
- (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.
Assessment:
- 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%