Advanced Algorithm Design

COS 521
Fall 2020

General Information:

Instructor: Sahil Singla (singla at cs dot princeton dot edu) (office hours: Tuesday and Thursday 3:00-4:00 PM)
TAs: Kritkorn Karntikoon, Antonio Molina Lovett, and Barak Nehoran.
Meeting time: Tuesday and Thursday 1:30-2:50 PM, Zoom Link
Course Information Sheet: Link
Piazza: Link
CodePost Use your princeton email to signup here

For a headstart, you may want to consult course notes from previous years: 2019 and 2018.

Homework: Homeworks will be posted below when they become available. Here is a LaTeX template you may use for the homework, and here is a short guide to LaTeX. Submit your homework on codePost.

Tentative Schedule:

Date Topic Notes
Sep 1 Introduction and Randomized Min-Cut Lecture 1
Sep 3 Hashing Lecture 2
Sep 8 Concentration Bounds Lecture 3
Sep 10 Hashing to Reals Lecture 4
Sep 15 Linear Programs and LP Rounding Lecture 5
Sep 17 LP Based Approximation and Duality Lecture 6
Sep 22 Strong Duality and Dual Fitting Lecture 7
Sep 24 Multiplicative Weights Lecture 8
Sep 29 (Online) Gradient Descent Lecture 9
Oct 1 Ellipsoid Algorithm Lecture 10
Oct 6 Semi-Definite Programs Lecture 11
Oct 8 Johnson-Lindenstrauss Lecture 12
Oct 13 Fall Break
Oct 15 Counting and Sampling Problems Lecture 13
Oct 20 Random Walks and Markov Chains Lecture 14
Oct 22 Low-Rank Approximations and SVD Lecture 15
Oct 27 Discrepancy Theory
Oct 29 Submodular Minimization
Nov 3 Online Algorithms
Nov 5 Online Primal-Dual for Set Cover
Nov 10 ProbeMax: Stochastic Optimization via LPs
Nov 12 Combinatorial Auctions
Nov 17 Communication Complexity
Nov 19 Coding Theory
Nov 24 Differential Privacy