CMU Advanced Algorithms, Spring 2024 (original) (raw)

• 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'sslides 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 andAaron 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 onnon-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)

• 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 from2021, 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