CS 270. Combinatorial Algorithms and Data Structures, Spring 2021

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)

  • Notes from Anupam Gupta's course

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. (board) (video)

  • Chapter 3 in Moitra's book

Embeddings

• (Feb 24) Dimension Reduction, Johnson-Lindenstrauss, Oblivious subspace embeddings. (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, Metric embeddings, Nearest neighbors.

  • Section 2.8 in Matousek's lecture notes on metric embeddings

• (Mar 3) Nearest neighbors, Locality sensitive hashing.

  • Lecture 8 and Lecture 9 from Andoni's class.

  • Section 2.9 in Matousek's lecture notes on metric embeddings

• (Mar 8) Bourgain's embedding, sparsest cut.

  • section 4.2,4.3 in Matousek's lecture notes on metric embeddings.

• (Mar 10) Tree embeddings

  • Lecture 5 in Anupam Gupta's course.

Spectral Graph Theory

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%

Tentative Plan

• Continuous Optimization (5 lectures)

  • Gradient Descent,

  • Mirror Descent,Multiplicative weights

  • Regret minimization, online convex optimization.

  • Ellipsoid Algorithm

    • Application: Solving LPs via multiplicative weights

• Linear algebraic primitives (4 lectures)

  • PCA, Power iteration

  • Tensors, power iteration, Jenrich's algorithm, Applications.

• Embeddings: (3 lectures)

  • Dimension reduction, Johnson-Lindenstrauss

  • Locality Sensitive Hashing, Nearest Neighbor Search

  • Low stretch spanning trees.

• Spectral Graph Theory (3 lectures)

  • Cheeger's inequality

  • Mixing of Markov chains

  • Electrical Flows

    • Application: Laplacian Solvers

• Semidefinite Programming: (4 lectures)

  • MaxCut

  • Matrix multiplicative weights

  • Sum of Squares SDPs: Proofs to Algorithms

    • Robust Linear Regression

• Differential Privacy (1 lecture)

• Other topics?

  • Interior point methods

  • Near-linear time Max Flow

  • Compressed sensing

  • Robust and heavy-tailed Statistics

  • Sparsest cut

  • Iterative rounding of linear programs

  • Primal-dual algorithms