15-850: Advanced Algorithms, Spring 2017
- Lecturer: Anupam
Gupta, GHC 7203.
- TA: Guru Guruganesh , GHC 7503
- Office hours: Anupam: Tuesday 5-6:30 (or by appointment),
Guru: Thursday 4-5:30 (or by appointment)
- Location: GHC 4211, MWF 10:30-11:50.
- Blog: https://cmuadvancedalgos.wordpress.com
- Piazza: here
Announcements
Homeworks
Lectures
- Lecture 1. Deterministic MSTs. Recap Prim/Kruskal/Boruvka. An $O(m \log^* n)$ time
algorithm. (my notes, scribe notes)
- Lecture 2. The Randomized MST algorithm of Karger, Klein and
Tarjan. LP approaches and Directed MSTs. (my
notes 1, 2, scribe notes)
Links for randomized MSTs:
References on arborescences:
- Lecture 3. Dynamic Graph Connectivity
algorithms. Frederickson, Kapron et al., Holm et al. (my notes, scribe notes)
Worst-case update times:
And for amortized update times which we did not go over:
- Lecture 4: Shortest Paths. Seidel's algorithm for (unweighted
undirected) APSP using
matrix multiplication.
(my notes, scribe notes)
- Lecture 5 (2/3): Low-stretch Trees. Bartal's construction.
(my notes, scribes notes)
- Lecture
notes from our randomized algorithms course (S11).
- Alon, Karp, Peleg, West: A Graph-Theoretic Game and its
Application to the k-Server Problem, SICOMP.
- Bartal: Probabilistic Approximation of Metric Spaces and its
Algorithmic Applications, FOCS 96
Our presentation pretty much followed his general construction.
- Fakcharoenphol, Rao,
Talwar, A
tight bound on approximating arbitrary metrics by tree
metrics, STOC 03.
This paper gives the best possible algorithm
for the metric graph case.
- Abraham, Neiman: Using Petal-Decompositions to Build a Low Stretch
Spanning Tree.
This paper gives the current best algorithm
for the general graph case.
Some other low-diameter decomposition schemes:
And applications of low-stretch spanning trees to some problems:
- Lecture 6 (2/6): Matchings in General Graphs: combinatorial algorithms
(my notes, scribe notes)
- Lecture 7 (2/8): Matchings in Graphs: Linear Programs and
Integrality of Polytopes (my LP
notes, matching polytope notes, scribe notes)
- Lecture 8 (2/10): Max-Weight Matchings in Graphs: A
Pricing-based Algorithm (my
notes, scribe notes)
- Lecture 9 (2/13): Matchings in Graphs: Algebraic Algorithms
(my notes, scribe notes)
And other papers that we did not get to (or discussed in passing):
- Lecture 10 (2/15): Smoothed Analysis (my notes, scribe notes)
- Lecture 11 (2/17): Online Learning and the Multiplicative Weights Framework
(old
notes from the LP/SDP course, scribe notes)
- Avrim's slides
from 15-451 (F13).
- The
Arora-Hazan-Kale survey.
- Lecture 12 (2/20): Applications of MW:
zero-sum-games, solving LPs
(my notes, scribe notes)
- Pages of the
Arora-Hazan-Kale survey
talking about zero-sum games.
- Derivation
of the regret bound when losses are not in $[-1,1]^N$ but in
$[-\gamma, \rho]^N$.
- The notes
from the LP/SDP course have Ax ge b instead of Ax le b, but the idea
is really the same.
Also, it has an example running the
algorithm for solving the Set Cover LP.
- Rohit
Khandekar's thesis
makes great reading about solving convex programs using MW; so
does Satyen
Kale's thesis;
both have excellent survey chapters.
- Relevant section of the
Arora-Hazan-Kale survey.
- Lecture 13 (2/22): Applications of MW: max-flows
using electrical flows.
(electrical flow
notes, scribe notes)
- Lecture 14 (2/24): Gradient Descent. Yet another low-regret
algorithm.
(my
notes, older notes, scribe notes)
- Lecture 15 (2/27): Mirror Descent: generalizing MW and GD.
(my notes, scribe notes)
- Our view is based on discussions with Nikhil Bansal for this course.
See his notes
(based on the FTRL equivalence).
- Our presentation largely follows Sebastien Bubeck's.
- Elad
Hazan
and Shai
Shalev-Shwartz present it using the equivalence to Follow the
Regularized Leader.
We did not talk about this connection, but
you may see this as a HW problem, time permitting.
- Lecture 16 (3/1): The Ellipsoid Algorithm: an overview
(my notes, scribe notes)
- Lecture 17 (3/3): Ellipsoid wrap-up. Interior-point Methods: an overview
(my notes, scribe notes)
- Lecture 18 (3/6): Concentration of Measure: "Chernoff-Hoeffding" Bounds.
(my notes, scribe notes)
- Notes by Jiri Matousek and Jan Vondrak.
- Notes on Chernoff bounds from our randomized algorithms
course (S11, S04).
- Need some advanced concentration inequalities? Look at
these notes by Colin McDiarmid, or Gabor
Lugosi.
- Or these fine books
by Alon
&
Spencer, Boucheron, Lugosi, Massart, Dubhashi & Panconesi, Motwani & Raghavan, Mitzenmacher & Upfal, Steele, and Janson, Luczak, Rucinski.
- David Wajc's notes and Robin Pemantle's talk on negative association and related topics.
And some history:
- Lecture 19 (3/8): Dimension Reduction: JL and related topics
(my notes, old scribe notes, scribe notes)
And stuff we did not cover:
- No Lecture on March 10. Happy Spring Break!!
- Lecture 20 (3/20): Streaming I: Computing Frequency Moments and JL
(my notes, my old notes)
- Lecture 21 (3/22): Dimension Reduction: Singular Value Decompositions
(my notes)
- Lecture 22 (3/24): Online Algorithms: Rent-or-Buy and Paging,
Online Primal-Dual
(my notes)
- Lecture 23 (3/27): Approximation Algorithms
- Lecture 24 (3/29): Semidefinite Programs I: Intro, Examples
(Eigenvalues, SoS Representations),
Duality
(my notes)
- Lecture 25 (3/31): Semidefinite Programs II: Approximation
Algorithms using SDPs
(my notes)
- Lecture 26 (4/3): Convex Programming Hierarchies
(my notes)
- Lecture 27 (4/5): Matroids and Matroid Intersection
(my notes)
- Lecture 28 (4/7): Submodularity
(my notes)
- Lecture 29 (4/14): Fixed-Parameter Tractable Algorithms
(my notes)
- End of Classes!!!
Maintained by Anupam Gupta