15-850: Advanced Algorithms, Spring 2024

Lecturer: Jason Li, GHC 7203, jmli at cs.cmu.edu

TAs: Emin Berker, GHC 6207, rberker at cs.cmu.edu

Office hours: Emin Wednesdays 2-3, Jason Fridays 1-2

Location: GHC 4303, MWF 3:30-4:50 3:30-4:50 (note: 3 days a week).

Piazza is the best way to contact the course staff.

Gradescope should be used to submit HWs. Entry code: NPVZXJ

Announcements

• The course policies have been moved here.
• We plan to have 3 lectures a week for the first ~10 weeks, see schedule below.
• A tentative schedule, though things will probably change around.


• Combined lecture notes from the 2020 version.
• Course offerings in previous years: Spring 23, Fall 20, Fall 18, Spring 17 and Spring 15.

Homeworks

• Homework 0 (due Friday, January 26) and Exercises 0
• Homework 1 (due Friday, Feb 9) and Exercises 1
• Homework 2 (due Monday, Feb 26) and Exercises 2
• Homework 3 (due Monday, Mar 24) and Exercises 3
• Homework 4 (due Friday, Apr 19) and Exercises 4

Lectures

• Week #1: Spanning Trees
  
  
  • Lecture 1. (Jan 17) MSTs. Recap Prim/Kruskal/Boruvka. Karger-Klein-Tarjan linear-time randomized algorithm. (draft notes)
    • 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.
    • Notes by Raimund Seidel and Gabriel Nivasch on the inverse Ackermann function.
    • 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.
  
  
  • Lecture 2. (Jan 19) The Karger-Klein-Tarjan randomized algorithm. Directed MSTs (aka Arborescences and Branchings). LP approaches. (draft notes)
    Arborescences:
    

    • The Chu-Liu (1965) and Edmonds (1966) papers. (I couldn't find the Bock '71 paper.) 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.

    References on basic LPs and duality:
    

    • Notes from 15-451 on basic LP concepts and LP duality.
    • Our Fall 2011 course on LPs/SDPs: the first few lectures are useful introductory material.
    • The Matousek and Gaertner book on LPs is a great introduction to LPs; CMU students can get PDF versions from Springer.
  
  
• Week #2: Shortest-Path Trees
  
  
  • Lecture 3. (Jan 22) Min-Cost Arborescences using LPs (finish). Shortest Paths and Min-Sum Products. (draft notes on arborescences, shortest paths)
    
    • Notes from 210, 451, and Jeff Erickson (SSSP, APSP), covering Dijkstra, Bellman-Ford-(Moore), Floyd-Warshall, and Johnson's algorithm.
    • History of shortest-path algorithms, by Lex Schrijver. (CMU only)
  
  
  • Lecture 4. (Jan 24) Seidel's APSP Algorithm. APSP Conjecture and Fine-Grained Reductions. (draft notes)
    
    Seidel's APSP Algorithm and Matrix Multiplication

    • 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 1992.
    • M. Fredman, New Bounds on the Complexity of the Shortest Path Problem, SICOMP 1976.

    References on the APSP Conjecture and fine-grained complexity:

    • 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.
    • Vassilevska Williams, Williams: Subcubic Equivalences Between Path, Matrix, and Triangle Problems, FOCS 2010.
  
  
  • Lecture 5. (Jan 27) Low-Diameter Decompositions and Low-stretch Trees. Bartal's construction. (draft 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 (Spielman-Teng, KMP, KOSZ).
  
  
• Week #3: Shortest-Path Trees (Finish), Matchings
  
  
  • Lecture 6. (Jan 29) A Near-linear-time Algorithm for Shortest Paths and Negative Edge Weights. (draft notes, old LaTeX notes)
    
    • Bernstein, Nanongkai, Wulff-Nilsen. Negative-Weight Single-Source Shortest Paths in Near-linear Time
      FOCS 2022 best paper award co-recipient for solving this long-standing open problem.
    • Quanta magazine article about the result.
    • Videos of technical presentations by Danupon Nanongkai and Aaron Bernstein.
    • Karl Bringmann, Alejandro Cassis, Nick Fischer. Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster! FOCS 2023.
  
  
  • Lecture 7. (Jan 31) A Near-linear-time Algorithm for Shortest Paths and Negative Edge Weights (finish). (draft notes, old LaTeX notes)
    
  
  
  • Lecture 8. (Feb 2) Matchings in Graphs: Combinatorial Algorithms (draft 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.
    • 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.
  
  
• Week #4: Matchings in Graphs (finish), Concentration of Measure
  
  
  • Lecture 9. (Feb 5) Matchings in Graphs II: Algebraic Algorithms (draft notes)
    
    • 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. (Feb 8) Matchings in Graphs III: Weighted Matching, the Hungarian Algorithm, Integrality of Polytopes (draft notes)
    
    • 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.
  
  
  • Lecture 11. (Feb 10) Concentration of Measure. Markov, Chebyshev, Chernoff-Hoeffding inequalities. (draft notes)
    
    • 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.

    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
  
  
• Week #5: Measure Concentration (Contd)
  
  
  • Lecture 12. (Feb 12) Concentration II: Proving Chernoff Bounds, Dimension Reduction, Sub-Gaussian r.v.s. (draft notes)
    
    • The references to Lecture 12 contain proofs of the standard Chernoff bounds.
    • 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 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. (Feb 14) Concentration III: Matrix Chernoff Bounds. Concentration Inequalities, a Survey. (draft notes)
    • Lecture notes on Bernstein's inequality and subexponential random variables from CMU's Advanced Statistics course.
    • Introduction to Random Matrix Theory, an active research field studying the concentration of random matrices, including Matrix Chernoff.
  
  
  • Lecture 14. (Feb 16) Data Streaming: Algorithms for Big Data. Alon-Mathias-Szegedy Frequency Estimator. (draft 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 (F20 version), with notes and pointers to other courses.
    • A more advanced course: David Woodruff's Algorithms for Big Data
  
  
• Week #6: Data Streaming (finish). Multiplicative Weights Update, Online Learning, and Max-Flow.
  
  
  • Lecture 15. (Feb 19) Data Streaming: Algorithms for Big Data. Distinct Elements Estimator. (draft notes)
    • Lecture notes from Jelani Nelson's course on Sketching Algorithms for Big Data.
    • The original paper by Flajolet and Martin.
  
  
  • Lecture 16. (Feb 21) Approximate Max-Flow by Multiplicative Weights Update. (draft notes)
    • Lecture notes from Debmalya Panigrahi's course on Graph Algorithms.
    • The original paper by Garg and Konemann which generalizes to multi-commodity flows.
  
  
  • Lecture 17. (Feb 23) Online Learning, the Hedge Algorithm, and Solving LPs. (draft notes)
    
    • The Arora-Hazan-Kale survey on the MW Framework.
    • 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.
  
  
• Week #7: Online Learning (Finish). First-Order Convex Optimization.
  
  
  • Lecture 18. (Feb 26) Zero-sum games and Von Neumann's Minimax Theorem (draft notes)
    
    • Pages of the Arora-Hazan-Kale survey talking about zero-sum games.
    • Lecture notes on duality and the minimax theorem from Shayan Oveis Gharan's algorithms course.
  
  
  • Lecture 19. (Feb 28) Gradient Descent: Yet another low-regret algorithm. (draft notes)
    
    • Potential function proofs of first-order methods by Nikhil Bansal and Anupam Gupta.
    • 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.
  
  
  • (Feb 28) Class Cancelled.


• Spring Break!!!
  
  
• Week #8: Convex Optimization (finish). Solving LPs in Polynomial Time.
  
  
  • Lecture 20. (Mar 11) Mirror Descent: generalizing MW and GD. (draft notes)
    
    • 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.
  
  
  • Lecture 21. (Mar 13) The Centroid and Ellipsoid Algorithms (draft notes)
    
    • The Bertsemas-Vempala paper on computing approximate centroids by random sampling, allowing the centroid algorithm to run in polynomial time.
    • See Chapter 7.1 of the Matousek and Gaertner book for a discussion on Ellipsoid.
    • The Grotschel-Lovasz-Schrijver book gives a comprehensive discussion.
    • Eugene Lawler's account of developments in 1979, and Gina Kolata's excellent report for Science magazine.
  
  
  • Lecture 22. (Mar 15) Interior-point Methods (draft notes)
    
    • We followed the explanation in this paper by Yin Tat Lee and Santosh Vempala.
      Our Lemmas 1 and 2 were their Lemmas 7 and 8.

    And many other resources are available:

    • 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).
  
  
• Week #9: Algorithm Game Theory (Emin guest-lecturing). Listener's Choice: Approximation Algorithms.
  
  
  • Lecture 23. (Mar 18) Algorithmic Game Theory: Sealed Bid Auctions, Myerson's Lemma (Emin's notes)
    
    • Lecture notes from Tim Roughgarden's class. We covered lectures 1 to 4.
  
  
  • Lecture 24. (Mar 20) Algorithmic Game Theory: House Allocation Problem, Kidney Exchange (Emin's notes)
    
    • Lecture notes from Tim Roughgarden's class. We covered lectures 9 and 10.
  
  
  • Lecture 25. (Mar 22) Approximation Algorithms: Vertex Cover, Set Cover, Max Coverage (draft notes)
    
    • The Shmoys and Williamson textbook on approximation algorithms.
    • Our approximation algorithms course from 2021, and older courses from 2005 and 2008.
    • Lecture notes on Vertex Cover from Avrim Blum's class at CMU
    • Lecture notes on Set Cover and Max Coverage from Viswanath Nagarajan's class
  
  
• Week #10: Listener's Choice Topics: Sparsest Cut, Dynamic Graph Connectivity, Sum-of-Squares
  
  
  • Lecture 26. (Mar 25) Sparsest Cut, Leighton-Rao Rounding Algorithm, Expanders (draft notes)
    
    • Lecture notes from Anupam Gupta's approximation algorithms class.
    • The Leighton-Rao paper.
    • Chapter 8 of [Williamson Shmoys] talks about region growing in detail.
    • A survey on Approximations for Cut Problems by David Shmoys gives the history, and discusses divide-and-conquer applications.
    • Some notes on the Leighton-Rao Rounding from Rajmohan Rajaraman.
  
  
  • Lecture 27. (Mar 27) Dynamic Connectivity, Kapron-King-Mountjoy Graph Sketching Algorithm, Nanongkai-Saranurak Expander Decomposition Algorithm (draft notes)
    
    • We followed Chapter 3.4 of the course notes
    • The original Kapron-King-Mountjoy paper
    • We followed Thatchaphol Saranurak's lecture notes on dynamic connectivity for expanders
    • The original Nanongkai-Saranurak paper
  
  
  • Lecture 28. (Mar 29) The Sum-of-Squares Method. Goemans-Williamson Rounding Algorithm for Max-Cut. (draft notes)
    
    • We followed Ankur Moitra's lecture notes on Sum-of-Squares for Max-Cut
    • Notes from the CMU course on "Proofs vs Algorithms: The Sum-of-Squares Method".
    • Online notes on Sum-of-Squares Method.
    • Chapter 6 (and section 6.1) of [Williamson-Shmoys] covers the semi-definite programming approach to max-cut
    • The original Goemans-Williamson paper.
    • Lower bounds on linear programs for Max-Cut: Chan, Lee, Raghavendra, Steurer and Kothari, Meka, Raghavendra.
  
  

---

Original by Anupam Gupta, maintained by Jason Li