Site menu:

Course notes

Lecture 1 (May 9): Introduction [pdf, one]
  • course overview, Karger's min-cut algorithm, Ramsey number
Lecture 2 (May 11): Isolating Cuts [pdf, one]
  • isolating cuts algorithm, minimum Steiner cut
Lecture 3 (May 16): Concentration Inequalities [pdf, one]
  • Markov's inequality, Chebeshev's inequality, second moment method, Chernoff bounds
Lecture 4 (May 18): Approximation Algorithms [pdf, one]
  • congestion minimization, graph sparsification
Lecture 5 (May 25, 30): Dimension Reduction and Compressed Sensing [pdf, one]
  • Johnson-Lindenstrauss lemma, restricted isometry property, l0-l1 minimization
Lecture 6 (June 1, 6): Graph Sketching [pdf, one]
  • sparse recovery, l0-sampling, graph streaming algorithms
Lecture 7 (June 6, 8): Local Lemma [pdf, one]
  • k-SAT, palette sparsification, Moser's algorithmic proof
Lecture 8 (June 13): Martingales [pdf, one]
  • Doob martingale, Azuma-Hoeffding inequality, method of bounded differences
Lecture 9 (June 15): Discrepancy Minimization [pdf, one]
  • Lovett-Meka constrained random walk algorithm
Lecture 10 (June 27): Spectral Sparsification [pdf, one]
  • random sampling, matrix Chernoff
Lecture 11 (June 29): Numerical Linear Algebra [pdf, one]
  • subspace embedding, input sparsity time, row sampling
Lecture 12 (July 4): Random Walks [pdf, one]
  • fundamental theorem, pagerank, perfect machings in regular bipartite graphs
Lecture 13 (July 6): Electrical Networks [pdf, one]
  • electrical flows, effective resistances, commute time, cover time
Lecture 14 (July 11, 13): Mixing Time [pdf, one]
  • eigenvalues, Lovasz-Simonovits curve, local graph partitioning
Lecture 15 (July 18): Markov Chain Monte Carlo [pdf, one]
  • Monte Carlo method, approximate counting to approximate sampling, Markov chains
Lecture 16 (July 20): Coupling [pdf, one]
  • stationary distribution, card shuffling, random spanning tree, independent sets
Lecture 17 (July 25): Polynomial Identity Testing [pdf, one]
  • string equality, Schwartz-Zippel lemma, parallel matching
Lecture 18 (July 27): Network Coding [pdf, one]
  • max-information-flow min-cut, distrbuted algorithm
Lecture 19 (Optional): Interactive Proofs [pdf, one]
  • graph non-isomorphism, #SAT