15-850: Advanced Algorithms, Fall 2020

Lecturer: Anupam Gupta, GHC 7203, anupamg at cs.

TAs: Alex Wang (alw1 at andrew), Isaac Grosof (igrosof at andrew)

Office hours: Isaac: Tue 3-4:30 p.m., Alex: Wed 5-6:30 p.m., Anupam: Friday 3-4 p.m. (All times ET, check Piazza for Zoom links)

Location: GHC 4211 online on Zoom, MWF 1:30-2:50 (note: 3 days a week). See Piazza for links to Zoom, Jamboard, and gather.town (for post-lecture discussions).

Piazza: is the best way to contact the course staff. here

Gradescope: used to submit HWs.

Announcements

• Combined lecture notes as a single file.
• The course policies have been moved here; please read them.
• All course announcements will be on Piazza: please make sure you check that regularly.
• The first lecture will be on Monday August 31. We plan to have 3 lectures a week for the first 10 weeks of the semester.
• A tentative schedule, though things will probably change around.
• Course offerings in previous years: Fall 18, Spring 17 and Spring 15.

Homeworks

• Homework 0 (due Tuesday, September 8)
• Homework 1 (due Sunday, September 20)
• Homework 2 (due Sunday, October 4)
• Homework 3 (due Sunday, October 18)
• Homework 4 (due Sunday, November 1)
• Homework 5 (due Wednesday, November 18)

Lectures

• Week #1: Spanning Trees
  
  
  • Lecture 1. (Aug 31) MSTs. Recap Prim/Kruskal/Boruvka. The Fredman-Tarjan \(O(m \log^\star n)\) time algorithm. The Karger-Klein-Tarjan randomized algorithm. (draft notes, board)
    • Surveys on MSTs by Jason Eisner and Martin Mares. An older one by Graham and Hell.
    • Translations and commentary on Boruvka's and Jarnik's original papers.
    • 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. (Sep 2) Randomized MST. Directed MSTs (aka Arborescences and Branchings). LP approaches. (draft notes for MSTs, arborescences, board)
    Randomized MSTs:

    • The Karger-Klein-Tarjan paper. a different proof of the sampling lemma.
    • The Komlos, King, and Hagerup papers on MST verification. Uri Zwick's slides on MST verification.

    Arborescences:
    

    • Edmonds, Optimal Branchings, 1966. (I couldn't find the Chu-Liu '65 and Bock '71 papers.) Our first 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. (Sep 4) Dynamic Graph Connectivity algorithms. Frederickson (worst-case), Holm et al. (amortized), Kapron et al. (randomized) (draft notes, board)
    
    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, SODA 2013. (and slides)
      See also: a SODA 2012 paper of Ahn, Guha, and McGregor with a similar sketching idea.
    • A recent breakthough getting \(n^{o(1)}\) worst-case updates, by Chuzhoy, Gao, Li, Nanongkai, Peng, and Saranurak, to appear at FOCS 2020.
      Features some (current and former) CMU students: Richard Peng and Jason Li.

    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 the logarithmic lower bound by Patrascu and Demaine. (Notes by Erik Demaine.)
  
  
• Week #2: Shortest-Path Trees
  
  
  • Labor Day. (Sep 7)
  
  
  • Lecture 4. (Sep 9) Shortest Paths. Seidel's algorithm for (unweighted undirected) APSP using matrix multiplication. (draft notes, board, slides (annotated))
    
    • Notes from 210, 451, and Jeff Erickson (SSSP, APSP), covering Dijkstra, Bellman-Ford-(Moore), Floyd-Warshall, and Johnson's algorithm.
    • R. Seidel. On the all-pairs-shortest-path problem, STOC 1992. (and on Wikipedia)
    • Alon, Galil, Margalit, Naor. Witnesses for Boolean Matrix Multiplication and for Shortest Paths, FOCS 92.
    • M. Fredman, New Bounds on the Complexity of the Shortest Path Problem, SICOMP.

    And some newer results which we won't have time to cover:

    • Ryan Williams' algorithm in time \(n^3/\exp(\sqrt{\log n})\), 2014. (my notes, scribe notes)
    • What if APSP cannot be solved in \(n^{3-\varepsilon}\) time: a survey by Virginia Vassilevska Williams for the Math Congress, 2018.
  
  
  • Lecture 5. (Sep 11) Low-stretch Trees. Bartal's construction. (draft notes, board)
    
    • 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).
  
  
• Week #3: Matchings
  
  
  • Lecture 6. (Sep 14) Matchings in Graphs: Combinatorial Algorithms (draft notes, board)
    
    • 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.
    • Seth Pettie's handy collection of papers related to matchings and their algorithms.
    • Direct proofs of the Tutte-Berge formula from Lex Schrijver, Doug West, Andrei Kotlov.
  
  
  • Lecture 7. (Sep 16) Matchings in Graphs: Linear Programs and Integrality of Polytopes (draft notes, board)
    
    • The proof I was trying to explain at the end (and that we will finish next time) appears in section 7.2.3 of the notes.
    • The Matousek and Gaertner book on LPs is a great introduction to LPs; CMU students can get PDF versions from Springer.
  
  
  • Lecture 8. (Sep 18) Matchings in Graphs: Linear Programs and Integrality of Polytopes (contd.) (draft notes (same as above), board)
    
    • Harold Kuhn's original paper, Andras Frank's tribute with technical context.
    • Chapters 10 and 15 of the Easley-Kleinberg book "Networks, Crowds, and Markets".
    • Paper by Gabrielle Demange, David Gale, Marilda Sotomayor on how the pricing dynamics give VCG prices.
  
  
• Week #4: Matchings, and then Interlude: Measure Concentration
  
  
  • Lecture 9. (Sep 21) Matchings in Graphs: Algebraic Algorithms (draft notes, board)
    
    • Notes on some of this from our randomized algorithms course.
    • Lovasz: On determinants, matchings, and random algorithms
    • Papers introducing the Tutte matrix, Edmonds matrix.

    Some other papers that explore this approach:

    • Mulmuley, Vazirani, Vazirani: Matching is as easy as Matrix Inversion.
    • The best result is due to Mucha and Sankowski; see Marcin Mucha's thesis for a nice presentation. And Nick Harvey's cleaner solution for non-bipartite graphs.
  
  
  • Lecture 10. (Sep 23) Concentration of Measure: "Chernoff-Hoeffding" Bounds. (draft notes, board)
    
    • A gentle introduction to the probabilistic method by the 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, Janson, Luczak, Rucinski, and Vershynin
    • Notes from Pascal Massart's St. Flour lectures, and some notes by David Pollard.
    • 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 11. (Sep 25) Concentration II: Hypercube Routing and Dimension Reduction. (draft notes, board)
    
    • The papers Valiant and Brebner, and a preceding paper of Valiant.
    • Some proofs of Johnson-Lindenstrauss: Indyk/Motwani, Dasgupta/Gupta, Achlioptas. Jelani Nelson's notes with more proofs.
  
  
• Week #5: Measure Concentration, and then Experts
  
  
  • Lecture 12. (Sep 28) Concentration III: Dimension Reduction and sub-Gaussianness. (draft notes, board)
    
    • Some proofs of Johnson-Lindenstrauss: Indyk/Motwani, Dasgupta/Gupta, Achlioptas. Jelani Nelson's notes with more proofs.
    • A (slightly weaker) lower bound due Noga Alon, and a tight lower bound of Larsen and Nelson.
    • Notes on sub-Gaussian/sub-exponential r.v.s by Martin Wainwright, Roman Vershynin, Ramon van Handel.

    And stuff we will not be able to cover:

    • The (distributional) JL property gives compressive sensing: notes by Jirka Matousek.
    • The Ailon-Chazelle paper on the Fast JL transform.
    • J-L Applications: solving LPs, spectral sparsification, near-neighbor search. There are many other application papers.
  
  
  • Lecture 13. (Sep 30) Data Streaming: Algorithms for Big Data. (draft notes, board)
    
    • The Alon-Mathias-Szegedy paper.
    • A chapter from Andrew McGregor and Muthu Muthukrishnan's book in preparation.
    • Courses by Jelani Nelson and Chandra Chekuri (F20 version), with notes and pointers to other courses.
    • A more advanced course: David Woodruff's Algorithms for Big Data
  
  
  • Lecture 14. (Oct 2) Online Learning and the Multiplicative Weights Framework. (draft notes, board)
    
    • The Arora-Hazan-Kale survey on the MW Framework.
    • The original Weighted Majority paper by Littlestone and Warmuth
  
  
• Week #6: Online Learning and Using it to Solve LPs
  
  
  • Lecture 15. (Oct 5) Applications of MW: zero-sum-games, solving LPs (draft notes, board)
    
    • Pages of the Arora-Hazan-Kale survey talking about zero-sum games.
    • 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 about solving LPs.
  
  
  • Lecture 16. (Oct 7) Applications of MW: max-flows (draft notes, board)
    
    • Derivation of the regret bound when losses are not in \([-1,1]^N\) but in \([-\gamma, \rho]^N\).
  
  
  • Lecture 17. (Oct 9) Applications of MW: max-flows from electrical flows. (draft notes (same as lecture 16), board)
    
    • 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 (alternating minimization) approach for max-flows via electrical flows, by Lee, Rao, and Srivastava.

    We briefly mentioned the near-linear time linear system solver:

    • The Kelner, Orecchia, Sidford, Allen-Zhu paper.
    • Talk slides from Lorenzo Orecchia. These have a very nice intro to electrical networks, in case you need a refresher.
  
  
• Week #7: Convex Optimization: First-Order Methods and Connections to Online Learning
  
  
  • Lecture 18. (Oct 12) Gradient Descent: Yet another low-regret algorithm. (draft notes, board)
    
    • Potential function proofs of first-order methods by Nikhil Bansal and myself.
    • 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.
  
  
  • Lecture 19. (Oct 14) Mirror Descent: generalizing MW and GD. (draft notes, board)
    
    • Potential function proofs of first-order methods by Nikhil Bansal and myself.
    • Sebastien Bubeck uses the mirror-map approach;
      Elad Hazan and Shai Shalev-Shwartz present it using the equivalence to Follow the Regularized Leader.
      We did not talk about the latter connection, but you may see this as a HW problem, time permitting.
  
  
  • No Lecture (Oct 16) Community engagement day holiday.
  
  
• Week #8: Convex Optimization: Second-Order Methods and Poly-time Algorithms
  
  
  • Lecture 20. (Oct 19) The Centroid and Ellipsoid Algorithms (draft notes, board)
    
    • The Bertsemas-Vempala paper on the centroid approach for convex programming.
    • See Chapter 7.1 of the Matousek and Gaertner book for a discussion on Ellipsoid.
    • The Grotschel-Lovasz-Schrijver book gives a comprehensive discussion.
    • Since we refer to Gaussian Elimination all the time, notes by Laci Lovasz and Peter Gacs.
    • Eugene Lawler's account of developments in 1979, and Gina Kolata's excellent report for Science magazine.
  
  
  • Lecture 21. (Oct 21) Ellipsoid (contd) and Interior-point Methods (start) (draft notes for Ellipsoid same as last lecture, board)
    
    • See references above (Lecture 20) for Ellipsoid, and below (Lecture 22) for Interior-point methods.
  
  
  • October 23: Mid-Semester Break!
    
    
• Week #9: Interior-point Methods, and Approximation Algorithms
  
  
  • Lecture 22. (Oct 26) Interior-point Methods (finish) (draft notes, board)
    
    • Chapter 7.2 of the Matousek and Gaertner book has several detatails we skip in our lecture notes.
    • Notes from our LP/SDP course, for Renegar's algorithm.
    • Four lectures by Steve Wright, Alexander Madry, and Aaron Sidford at the Bridging Continuous and Discrete Methods Boot Camp.
    • Books by Steve Wright and Jim Renegar are authoritative references.
    • As are lecture notes by Yuri Nesterov and Arkadi Nemirovski, and Ben-Tal and Nemirovski; they use the self-concordance viewpoint.
    • A survey/tutorial by Mike Todd and Arkadi Nemirovski (2009).
  
  
  • Lecture 23. (Oct 28) Approximation Algorithms (draft notes, board)
    
    • The Shmoys and Williamson textbook on approximation algorithms.
    • Our approximation algorithms courses from 2005 and 2008.
  
  
  • Lecture 24. (Oct 30) Approximation Algorithms for Bin Packing and MaxCut (draft notes, board)
    
    • The bin-packing algorithm of Fernandez de la Vega and Lueker (notes). And the recent improvements of Hoberg and Rothvoss.
    • MaxCut: notes on the hyperplane rounding analysis, integrality gap, UG hardness. (The latter notes are from our advanced approx.algos course).
    • Another book by Gaertner and Matousek: Approximation Algorithms via Semidefinite Programming. Also free on Springer (for CMU students).
  
  
• Week #10: Online Algorithms, and Students' Requests
  
  
  • Lecture 25. (Nov 2) Online Algorithms and Competitive Analysis (draft notes that are pretty draft-y right now, board)
    
    • 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.
  
  
  • Lecture 26. (Nov 4) Students' Choice #1: Smoothed Analysis of Algorithms: Beyond the Worst-Case (my hand-written notes, also draft-y draft notes, board)
    
    • CACM article on Beyond-Worst-Case Analysis by Tim Roughgarden, a book with contributed chapters, and courses by Nikhil Bansal, Tim Roughgarden, and Dan Spielman.
    • Lecture notes on smoothed analysis by Heiko Roglin (with slides).
    • Survey article on smoothed simplex by Daniel Dadush and Sophie Huiberts
    • 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 27. (Nov 6) Students' Choice #2: Secretary and Prophet Problems (draft notes, board)
    
    • A survey on the secretary problem and random-order models. See the notes and survey for pointers.
  
  
• Week #11: Students' Requests
  
  
  • Lecture 28. (Nov 9) Students' Choice #3: Martingales and Concentration Inequalities (board)
    
    • Lecture notes from our Randomized Algorithms course.
    • Notes on Concentration by Colin McDiarmid, or Gabor Lugosi, and Ramon van Handel.
    • This monograph by Mike Steele on concentration methods for combinatorial problems gives a clear explanation of Talagrand's proof for TSP.
    • There are many lecture notes on Martingales online: these by Manjunath Krishnapur are solid.
  
  
  • Lecture 29. (Nov 11) Students' Choice #4: Improving on Christofides' Algorithm for the Traveling Salesman Problem (draft notes, board)
    
    • Notes by Shayan Oveis Gharan, as part of his course on the polynomial paradigm.
    • Talks by Shayan and by Nathan Klein.
    • The original papers: Christofides and Serdyukov, Oveis Gharan, Saberi, and Singh, Karlin Klein Oveis Gharan (2019 paper for half-integral case), (2020 paper for general case).
    • A survey by Jens Vygen.
    • Improvements for the graphic case: Momke and Svensson, Mucha, and Sebo and Vygen.