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

• A tentative schedule.
• Course description, policies, etc.

Homeworks

• Homework 1 (due Friday, Feb 3rd)
• Homework 2 (due Wednesday, Feb 15th)
• Homework 3 (due Friday, Mar 3rd)
• Homework 4 (due Monday, Mar 20th)
• Homework 5 (due Friday, Mar 31st)
• Homework 6 (due Friday, Apr 21st)

Lectures

• Lecture 1. Deterministic MSTs. Recap Prim/Kruskal/Boruvka. An $O(m \log^* n)$ time algorithm. (my notes, scribe notes)
  
  • Surveys on MSTs by Jason Eisner and Martin Mares. An older one by Graham and Hell.
  • The Fredman-Tarjan paper about Fibonacci heaps.
  • Some notes on Fibonacci heaps from Danny Sleator and Kevin Wayne (with figures).
  • Notes by Raimund Seidel and Gabriel Nivasch on the inverse Ackermann function.


• 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:
  • The Karger-Klein-Tarjan paper. Timothy Chan has a different proof of the sampling lemma.
  • The Komlos, King, and Hagerup papers on MST verification. Uri Zwick's notes on MST verification.
  References on arborescences:
  
  • Edmonds, Optimal Branchings, 1966. (I couldn't find the Chu-Liu '65 and Bock '71 papers.) Our proof follows Karp '71.
  • R. Tarjan, Finding optimal branchings: an $O(m log n)$ time algorithm. (and errata by Carmerini et al.)
  • Current best: Mendelson, Tarjan, Thorup, Zwick, gave an $O(m log log n)$ algorithm in 2004.


• Lecture 3. Dynamic Graph Connectivity algorithms. Frederickson, Kapron et al., Holm et al. (my notes, scribe notes)
  Worst-case update times:
  • Greg Frederickson, Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications, 1985. (and slides by Ran Duan)
  • Kapron, King, and Mountjoy, Dynamic graph connectivity in polylogarithmic worst case time, 2012. (and slides)
  • some recent developments by Nanongkai and Saranurak and by Wulff-Nilsen, 2016
  And for amortized update times which we did not go over:
  • the Holm, de Lichtenberg, Thorup paper (and slides by Pino Italiano and Ran Duan)
  • and a lower bound by Patrascu and Demaine.


• Lecture 4: Shortest Paths. Seidel's algorithm for (unweighted undirected) APSP using matrix multiplication. (my notes, scribe notes)
  • Slides (pdf) for the first 20 minutes.
  • Basic notes on shortest-paths from 210, 451, and from Jeff Erickson (SSSP, APSP)
  • R. Seidel. On the all-pairs-shortest-path problem, STOC 1992.
  • Alon, Galil, Margalit, Naor. Witnesses for Boolean Matrix Multiplication and for Shortest Paths, FOCS 92.
  
  
• 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:
  • The Calinescu-Karloff-Rabani/Fakchareonphol-Rao-Talwar schemes, the Miller Peng Xu scheme.
  And applications of low-stretch spanning trees to some problems:
  • Approximation Algorithms (a survey), solving linear systems (Speilman-Teng, KMP, KOSZ).
  
  
• Lecture 6 (2/6): Matchings in General Graphs: combinatorial algorithms (my notes, scribe notes)
  • Jack Edmonds: Paths, Trees, and Flowers, Canad. J. Math.
  • Notes on bipartite and non-bipartite matchings by Michel Goemans, and on non-bipartite matchings by Danny Sleator.
  • Lex Schrijver's notes on combinatorial optimization.
  • The Lovasz-Plummer book on matching theory.
  • Direct proofs of the Tutte-Berge formula from Lex Schrijver, Doug West, Andrei Kotlov.
  
  
• Lecture 7 (2/8): Matchings in Graphs: Linear Programs and Integrality of Polytopes (my LP notes, matching polytope notes, scribe notes)
• Blog post with additional comments and references.
• Notes from our LP/SDP course on the integrality of the non-bipartite perfect matching polytope.
• Edmonds: Maximum matching and a polyhedron with 0,1 vertices.
  This gives an algorithm to find a max-weight matching in general graphs, which we did not see.


• Lecture 8 (2/10): Max-Weight Matchings in Graphs: A Pricing-based Algorithm (my notes, scribe notes)
• Notes on Max-weight matchings from Goemans, from 451 (with our markets-based presentation).
• Chapters 10 and 15 of the Easley-Kleinberg book "Networks, Crowds, and Markets".
• Demange, Gale, Sotomayor paper on how the dynamics give VCG prices.
• Harold Kuhn's original paper preceded by reminescences, Andras Frank's tribute with technical context.


• Lecture 9 (2/13): Matchings in Graphs: Algebraic Algorithms (my notes, scribe notes)
  • Notes on some of this from our randomized algorithms course.
  • Papers introducing the Tutte matrix, Edmonds matrix.
  • Lovasz: On determinants, matchings, and random algorithms
  And other papers that we did not get to (or discussed in passing):
  • Mulmuley, Vazirani, Vazirani: Matching is as easy as Matrix Inversion.
  • Rabin and Vazirani, Maximum Matchings in General Graphs using Randomization
  • Mucha and Sankowski; see Marcin Mucha's thesis for a nice presentation. And Nick Harvey's cleaner solution for non-bipartite graphs.
  
  
• Lecture 10 (2/15): Smoothed Analysis (my notes, scribe notes)
• Courses on beyond-worst-case analysis, by Dan Spielman, and Tim Roughgarden.
• Lecture notes on smoothed analysis by Heiko Roglin (with slides).
• Beier and Voecking: Typical Properties of Winners and Losers
• Englert, Roglin, and Voecking on 2OPT: geometric instances, general instances.
  They give a much tighter bound on the expected length of improving paths than we did in lecture.


• 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)
• Some comments and examples on the blog.
• A monograph by Doyle and Snell: Random Walks and Electric Networks.
• Christiano et al.: Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs.
• Slides from Kurt Mehlhorn.
• Video of tutorial talk by Madry, other talks at the spectral algorithms boot camp.
• A different approach for max-flows via electrical flows, by Lee, Rao, and Srivastava.


• Lecture 14 (2/24): Gradient Descent. Yet another low-regret algorithm. (my notes, older notes, scribe notes)
• Books on Online Machine Learning/Convex Optimization by S. Bubeck, S. Boyd and L. Vanderberghe, Yu. Nesterov (and here), S. Shalev-Shwartz, E. Hazan, N. Vishnoi.
• MLD's F16 Optimization course has much more on GD and variants, and on other techniques too.
• Moritz Hardt's explanation on improving the $\alpha/\beta$ to $\sqrt{\alpha/\beta}$ for well-conditioned convex fns.


• 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)
• Notes (part 1, part 2) from the LP/SDP course
• Sebastian Bubeck's notes on center-of-gravity and ellipsoid.
• The Grotschel-Lovasz-Schrijver book.
• The Bertsemas-Vempala paper on the center-of-gravity approach.
• Since we refer to Gaussian Elimination all the time, notes by Laci Lovasz and Peter Gacs.


• Lecture 17 (3/3): Ellipsoid wrap-up. Interior-point Methods: an overview (my notes, scribe notes)
• Notes from the Matousek and Gaertner book (to scan)
• Notes from our LP/SDP course, for Renegar's original algorithm.
• Books by Jim Renegar, Steven Wright.
• Lecture notes by Yuri Nesterov and Arkadi Nemirovski, and Ben-Tal and Nemirovski.
• Survey/tutorial by Todd and Nemirovski (2009).


• 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:
• Hoeffding's 1963 paper has a nice comparison of the bounds
• Chernoff's 1952 paper (and he attributes his Chernoff bound proof to Herman Rubin)
• Cast: Chebyshev, Bienayme, Markov, Bernstein, Bennett, Cramer, Chernoff, Hoeffding


• Lecture 19 (3/8): Dimension Reduction: JL and related topics (my notes, old scribe notes, scribe notes)
• Some proofs of Johnson-Lindenstrauss: Indyk/Motwani, Dasgupta/Gupta, Achlioptas. Jelani Nelson's notes with more proofs.
• Lower bounds due Noga Alon, and a brand new (tight!) lower bound of Larsen and Nelson.
• Notes on sub-Gaussian/sub-exponential r.v.s by Martin Wainwright, Roman Vershynin.
• The (distributional) JL property gives compressive sensing: notes by Jirka Matousek.
And stuff we did not cover:
• The Ailon-Chazelle paper on the Fast JL transform.
• J-L Applications: near-neighbor search, robust concept learning and mixtures of Gaussians. There are many other application papers.


• No Lecture on March 10. Happy Spring Break!!


• Lecture 20 (3/20): Streaming I: Computing Frequency Moments and JL (my notes, my old notes)
• The Alon-Mathias-Szegedy paper.
• A chapter from Andrew McGregor and Muthu Muthukrishnan's book in preparation.
• Courses by Jelani Nelson and Chandra Chekuri, with notes and pointers to other courses.


• Lecture 21 (3/22): Dimension Reduction: Singular Value Decompositions (my notes)
• My lecture was partly based on Chapter 3 in the Blum-Hopcroft-Kannan book.
• Book chapter from the Mining of Massive Datasets book, by Leskovec, Rajaraman and Ullman, with a more practical treatment of SVDs.
• Survey on SVD computation: how to avoid actually computing $A^TA$.
• Nick Harvey's notes on basic properties of symmetric matrices.
• Stewart's History of the SVD is a fun read: the Eckart-Young theorem was first proved by Schmidt (of Gram-Schmidt fame)


• Lecture 22 (3/24): Online Algorithms: Rent-or-Buy and Paging, Online Primal-Dual (my notes)
• Online algorithms courses from Avrim, Serge Plotkin, Yair Bartal.
• Notes on ski-rental and paging by Avrim and Danny.
• Survey on paging by Sandy Irani.
• A paper of Raghavan and Snir showing that any randomized memoryless paging algorithm has competitive ratio at least k.
• Seffi Naor's slides (1, 2, 3) on online primal-dual from here, and a monograph by Niv Buchbinder and Seffi.
• A workshop to bring together online learning and online algorithms.


• Lecture 23 (3/27): Approximation Algorithms
• Dual fitting for Set Cover (notes)
• Primal-dual for Vertex Cover (notes)
• Bin-Packing algorithm of Fernandez de la Vega and Lueker (notes)
  And the recent improvements of Hoberg and Rothvoss.


• Lecture 24 (3/29): Semidefinite Programs I: Intro, Examples (Eigenvalues, SoS Representations), Duality (my notes)
• Comments, caveats, clarifications on the blog.
• Laci Lovasz's notes; notes/surveys by Todd, Boyd and Vandenberghe, Alizadeh.
• Notes from our LP/SDP class (duality notes, and the duality gap example), and Ryan's toolkit class.
• Farid Alizadeh's page of SDP references.
• Caveats about SDP runtimes, and a recent paper of Ryan with a similar caveat for SOS proof systems.


• Lecture 25 (3/31): Semidefinite Programs II: Approximation Algorithms using SDPs (my notes)
• MaxCut: notes on the GW analysis, integrality gap, UG hardness. (The latter notes are from our advanced approx.algos course).
• Some notes on the Karger Motwani and Sudan result on coloring 3-colorable graphs.
  The latest step in the series of improvements is by Kawarabayashi and Thorup getting $n^{1/5-\epsilon}$ colors.
• The Alon-Naor paper on Grothendieck's Inequality, and the original Krivine paper.
  An improvement by Braverman et al. beating the Krivine bound, and a detailed survey by Gilles Pisier.


• Lecture 26 (4/3): Convex Programming Hierarchies (my notes)
• Surveys by Monique Laurent (1, 2), and by Chlamtac and Tulsiani (from the approximation perspective).
• Sister courses on SoS by Boaz Barak and Pablo Parillo and by David Steurer and Pravesh Kothari
• A course by Nikhil Bansal and Daniel Dadush (and a hierarchies reading group)


• Lecture 27 (4/5): Matroids and Matroid Intersection (my notes)
• James Oxley on "What is a Matroid?" (and a talk by him at Banff)
• A brief history of matroids and their algorithms, by Bill Cunningham.
• Edmonds: Matroid Partition, Submodular Functions, Matroids, and Certain Polyhedra
• Notes by Lex Schrijver, Michel Goemans (more) Chandra Chekuri (more)


• Lecture 28 (4/7): Submodularity (my notes)
• Laci Lovasz's notes on submodularity.
• Chandra Chekuri's notes on submodular minimization.
• Andras Frank's survey on using submodularity for proofs in graph theory


• Lecture 29 (4/14): Fixed-Parameter Tractable Algorithms (my notes)
• The Parameterized Algorithms book by Cygan et al.: all you want to know about FPT algorithms and more.
  Other books by Dowdney and Fellows, Flum and Grohe, Neidermeier, exact algos book by Fomin and Kratsch.
• Tons of great stuff from this Summer school on FPT, and a set of open problems!
• Slides from Rolf Neidermeier and Jiong Guo. It has a lot of material, including some of what we discussed.
• Surveys by Neidermeier on FPT, Woeginger and Fomin and Kaski on exact algos.


• End of Classes!!!