15-457A/15-859E: Advanced Algorithms, Spring 2015

Lecturer: Anupam Gupta, GHC 7203.

TA: Euiwoong Lee GHC 7503.
Office hours: Anupam: Mondays 3-4pm (or as announced on the blog); Euiwoong: Thursdays 4-5pm (or by email).

Location: GHC 4211, MWF 1:30-2:50.

Blog: https://cmuadvancedalgos.wordpress.com

Announcements

• A tentative schedule for the next few weeks.
• Scribing instructions
• Course Description, Policies, etc.

Homeworks

• Homework 1 (due Wednesday, Jan 21st)
• Homework 2 (due Friday, Jan 30th)
• Homework 3 (due Friday, Feb 13th)
• Homework 4 (due Friday, Feb 27th)
• Homework 5 (due Friday, Mar 20th)
• Homework 6 (due Friday, Apr 17th)

Lectures

• Lecture 1. MSTs. Recap Prim/Kruskal/Boruvka. An $O(m \log^* n)$ time algorithm. (unedited scribe notes, my notes)
  • Jason Eisner's comprehensive survey on MSTs. (Other surveys by Mares, Graham-Hell)
  • The Fredman-Tarjan paper.
  • Some notes on Fibonacci heaps from Danny Sleator and Kevin Wayne (with figures).
  • Raimund Seidel's notes on the inverse Ackermann function.
    Update: a well-written short exposition on inverse Ackermann by Gabriel Nivasch.
  
  
• Lecture 2. MSTs. A randomized linear time-algorithm. MST verification. (unedited scribe notes, my notes)
  • 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.
  
  
• Lecture 3: Directed MSTs a.k.a. arborescences. Chu-Liu-Edmonds-Bock algorithm. LP Dual fitting. (my notes)
  • 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.
  And some very basic information on LPs and duality:
  • Very basic notes from 15-451: basics, duality
  • Course on linear programs/semidefinite programs in CS by Ryan O'Donnell and me.
  • Chapter on duality from the excellent Matousek and Gaertner book. (CMU only)


• Lecture 4: Shortest Paths. Seidel's algorithm for (unweighted undirected) APSP using matrix multiplication. (unedited scribe notes, my 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: Shortest Paths. Williams' algorithm for APSP using polynomials and matrix multiplication. (unedited scribe notes, my notes)
  • R. Williams, Faster all-pairs shortest paths via circuit complexity, STOC 14.
  We didn't get a chance to go over Fredman's proof that APSP can be solved using only $O(n^{2.5})$ comparisons.
  • Blog post about this.
  • M. Fredman, New Bounds on the Complexity of the Shortest Path Problem, SICOMP.
  
  
• Lecture 6: Low-stretch Trees. Bartal's construction. (unedited scribe notes, my 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 CalinescuKR/FakchareonpholRT schemes, the Miller Peng Xu scheme.
  And applications of low-stretch spanning trees to some problems:
  • Approximation Algorithms, solving linear systems.
  
  
• Lecture 7: Matchings in Graphs: combinatorial algorithms (unedited scribe notes, my notes)
  • Michel Goemans' notes on bipartite and non-bipartite matchings.
  • Schrijver's notes on combinatorial optimization.
  • The Lovasz-Plummer book on matching theory.
  
  
• Lecture 8: Edmonds' Blossom Algorithm. (unedited scribe notes, my notes, same as for Lec#7)
  • Notes on non-bipartite matchings: Michel Goemans, Danny Sleator.
  • Jack Edmonds: Paths, Trees, and Flowers, Canad. J. Math.
  • Direct proofs of the Tutte-Berge formula from Lex Schrijver, Doug West, Andrei Kotlov.
  • Seth Pettie's matching page, for all your matching bibliography needs.
  
  
• Lecture 9: Max-Weight Matchings. (unedited scribe notes, my notes)
  • Notes on Max-weight matchings from Goemans, from 451 (with a 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 10: LPs. The Perfect Matching Polytope. Integrality of polytopes. (unedited scribe notes, my notes 1, 2)
  • Notes from our LP/SDP course on the integrality of the non-bipartite case.
  • 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 11: Matrix-based algorithms for Matchings via Polynomial Identity Testing. (unedited scribe notes, my 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 12: Online Learning and the Multiplicative-Weights Algorithm. (unedited scribe notes, my notes from the LP/SDP course)
• Avrim's slides from 15-451 (F13).
• The Arora-Hazan-Kale survey.


• Lecture 13: Applications of MW: zero-sum-games, solving LPs (start) (unedited scribe notes, notes on 0-sum games, my notes from the LP/SDP course)
• Pages of the Arora-Hazan-Kale survey talking about zero-sum games.


• Lecture 14: Applications of MW: solving LPs, max-flows using shortest paths. (unedited scribe notes, LP notes, flow notes)
• 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 great survey chapters.
• Relevant section of the Arora-Hazan-Kale survey.


• Lecture 15: Applications of MW: max-flows using electrical flows. (unedited scribe notes, electrical flow notes)
• Some comments and examples on the blog.
• 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.


• Lecture 16: Gradient Descent. Yet another low-regret algorithm. (unedited scribe notes, my notes)
• Nisheeth Vishnoi's notes.
• Books on Online Machine Learning/Convex Optimization by S. Bubeck, S. Shalev-Shwartz, E. Hazan.
• Lecture notes on Convex Optimization by S. Boyd and L. Vanderberghe, Yu. Nesterov.
• MLD's F12 Optimization course: all you want to know about GD and related things.


• Lecture 17: The Ellipsoid Algorithm: an overview (scribe notes, my notes)
• Comments and erratum on the blog.
• 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.


• Lecture 18: Concentration of Measure: "Chernoff-Hoeffding" Bounds. (unedited scribe notes, my 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, Dubhashi-Panconesi book, Motwani & Raghavan, Mitzenmacher & Upfal, Steele, and Janson, Luczak, Rucinski.
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: Dimension Reduction: JL and related topics (my scribe notes)
• Proofs of Johnson-Lindenstrauss: Indyk/Motwani, Dasgupta/Gupta, Achlioptas. Each of these proofs is a bit different.
• The Ailon-Chazelle paper on the Fast JL transform.
• Jelani Nelson's notes with different proofs, and many pointers.
• Using J-L for learning applications: robust concept learning and mixtures of Gaussians. There are many other application papers: these are the pioneering ones.
• Lower bounds due Noga Alon, and Larsen and Nelson.


• No Lecture on Feb 27. HW #4 due, please give to Euiwoong.


• Lecture 20: Streaming I: Computing Frequency Moments and JL (my scribe 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: Dimension Reduction: Singular Value Decompositions (scribe notes, my notes)
• Comments on the blog.
• My lecture was partly based on Chapter 3 in the 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: SVDs II: Fast SVDs via sampling (my notes)
• Clarifications on the blog.
• The Rudelson Vershynin paper: our presentation followed Nick Harvey's.
• Kannan and Vempala's monograph: Spectral Algorithms.
  Chapter 6 talks about length-squared sampling and CUR decompositions.
• Terry Tao's blog post on the behavior of eigenvalues under matrix sums, which give us perturbation theorems.
• The Boutsidis-Woodruff paper on optimal CUR decompositions.


• Lecture 23: SVDs III: Misra-Gries, Deterministic Streaming SVDs (my notes)
• The Misra-Gries algorithm for frequent items (and here, here, here).
• The Berinde, Cormode, Indyk, Strauss paper, with many other references.
• The Ghashami-Liberty-Phillips-Woodruff fast deterministic algorithms for Low-Rank Matrix Approx that we saw in lecture.


• Lecture 24: Fixed-Parameter and Exact Algorithms I (my notes)
• Tons of great stuff from this Summer school on FPT, and a set of open problems!
• FPT books by Dowdney and Fellows, Flum and Grohe, Neidermeier, exact algos book by Fomin and Kratsch.
• 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.


• Lecture 25: Fixed-Parameter and Exact Algorithms II
• See the handwritten notes and links for Lecture 24.
• Chandra Chekuri's survey talk on treewidth.
• Treewidth notes from Ryan's Theorist's Toolkit class


• Lecture 26: Online Algorithms: Rent-or-Buy and Paging, Online Primal-Dual (my notes)
• A bad example for just random eviction.
• 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.


• No Lectures March 27-April 1. Happy Spring Break! Next lecture on Friday, April 3.


• Lecture 27: Semidefinite Programs I: Intro, Examples, MaxCut, Duality (my notes)
• 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.
• MaxCut: notes on the GW analysis, integrality gap, UG hardness. (Latter notes from our advanced approx.algos course).
• Farid Alizadeh's page of SDP references.
• Erratum: caveats about SDP runtimes. (thanks, Guru)


• Lecture 28: Semidefinite Programs II (Checking SoS) + Smoothed Analysis I (Definitions)
Sum-of-Squares: (my notes on SoS, Grothendieck which we did not cover)
• Notes on checking if a polynomial is a sum-of-squares.
• Introduction to SoS Proof Systems: O'Donnell-Zhou, Barak and Steurer survey.
• Courses by Boaz Barak, Monique Laurent, Pablo Parillo.

Smooth Complexity: (unedited scribe notes joint with lecture 29, my notes)
• The smoothed analysis page maintained by Dan Spielman.
• The original Spielman-Teng paper, and survey articles by them (ICM, FoCM).
• Roman Vershynin's paper giving a better upper bound.
• Lecture notes by Heiko Roglin (with slides).
• Martin Licht's thesis is an elaboration of [ST04].


• Lecture 29: Smoothed Analysis, and Beyond-Worst Case (unedited scribe notes, my notes)
• Courses on beyond-worst-case analysis, by Dan Spielman, and Tim Roughgarden.
• Lecture notes by Heiko Roglin (with slides).
• Beier and Voecking: Typical Properties of Winners and Losers