15-850: Advanced Algorithms, Spring 2023

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

TAs: Madhusudhan Pittu (mpittu@andrew)

Office hours: Madhusudhan Thu evenings, Anupam Fridays 1-2

Location: Posner 153, MWF 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: 3J7YX4

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: Fall 20, Fall 18, Spring 17 and Spring 15.

Homeworks

• Homework 0 (due Monday, January 23) and Exercises 0
• Homework 1 (due Friday, Feb 3) and Exercises 1
• Homework 2 (due Friday, Feb 17) and Exercises 2
• Homework 3 (due Friday, Mar 3) and Exercises 3
• Homework 4 (due Friday, Mar 24) and Exercises 4
• (Optional) Homework 5 (due Friday, Apr 28)

Lectures

• Week #1: Spanning Trees
  
  
  • Lecture 1. (Jan 18) MSTs. Recap Prim/Kruskal/Boruvka. The Fredman-Tarjan $O(m \log^\star n)$ time 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.
    • 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. (Jan 20) The Karger-Klein-Tarjan randomized algorithm. Directed MSTs (aka Arborescences and Branchings). LP approaches. (draft notes for MSTs, arborescences)
    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:
    

    • 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 23) Min-Cost Arborescences using LPs (finish). Shortest Paths. (draft notes, slides)
    
    • 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 25) Shortest Paths using Min-Sum Products. Seidel's algorithm for (unweighted undirected) APSP using matrix multiplication. Motivate Low-Sretch Spanning Trees. (draft notes for shortest paths, LDDs)
    
    • 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 1992.
    • M. Fredman, New Bounds on the Complexity of the Shortest Path Problem, SICOMP 1976.
  
  
  • 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 30) A Near-linear-time Algorithm for Shortest Paths and Negative Edge Weights. (handwritten notes)
    
    • Bernstein, Nanongkai, Wulff-Neilsen. 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.
  
  
  • Lecture 7. (Feb 1) 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.
  
  
  • Lecture 8. (Feb 3) 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.
  
  
• Week #4: Matchings (Contd), Measure Concentration (Start)
  
  
  • Lecture 9. (Feb 6) Matchings in Graphs III: Linear Programs and Integrality of Polytopes (draft notes)
    
    • The Matousek and Gaertner book on LPs is a great introduction to LPs; CMU students can get PDF versions from Springer.
  
  
  • Lecture 10. (Feb 8) Matchings in Graphs IV: Linear Programs and Integrality of Polytopes (contd.) (draft notes (same as above))
    
    • 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: "Chernoff-Hoeffding" Bounds. An Application to Hypercube Routing. (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.
    • David Wajc's notes and Robin Pemantle's talk on negative association and related topics.
    • The papers on Oblivious Hypercube routing: Valiant and Brebner, and a preceding paper of Valiant.

    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 13) Concentration II: Proving Chernoff Bounds, Dimension Reduction, Sub-Gaussian r.v.s. (draft notes for Chernoff bounds, dim.red.)
    
    • The references to Lecture 11 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 15) Concentration III: Dimension Reduction and sub-Gaussian random variables. Compressive Sensing (draft notes)
    
    • The (distributional) JL property gives compressive sensing: notes by Jirka Matousek.
    • My home-brewed html and jupyter notebook. We use basis pursuit (L1 minimization) for sparse signal recovery.
    • Articles from AMS and Wired about compressive sensing. Terry Tao's blog post.
    • Notes on compressive sensing by Roughgarden/Valiant.
    • The Compressive Sensing resource page at Rice.
  
  
  • Lecture 14. (Feb 17) Compressive Sensing (finish). Data Streaming: Algorithms for Big Data. (draft notes for comp.sensing and streaming)
    
    • 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: Experts (and Submodularity)
  
  
  • Lecture 15. (Feb 20) Online Learning and the Multiplicative Weights Framework. (draft notes)
    
    • The Arora-Hazan-Kale survey on the MW Framework.
    • The original Weighted Majority paper by Littlestone and Warmuth
  
  
  • Lecture 16. (Feb 22) Submodularity. (Guest Lecture by Madhusudhan Pittu.)
  
  
  • Lecture 17. (Feb 24) Applications of MW: zero-sum-games, solving LPs (draft notes)
    
    • 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.
  
  
• Week #7: Online Learning (Experts) and First-Order Convex Optimization
  
  
  • Lecture 18. (Feb 27) Solving LPs and Flows via MW (draft notes for LPs, flows)
    
    See references from Lecture #17. Moreover, using electrical flows:

    • 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.
  
  
  • Lecture 19. (Mar 1) Brief intro to Laplacians (continued). Gradient Descent: Yet another low-regret algorithm. (draft notes)
    
    We first gave an overview of Graph Laplacians, and how they arise in electrical flows:

    • Draft of the Spectral and Algebraic Graph Theory book by Dan Spielman.
    • Talk slides from Lorenzo Orecchia. These have a very nice intro to electrical networks, in case you need a refresher.

    Then we started to look at Convexity and Gradient Methods:

    • 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 20. (Mar 3) Mirror Descent: generalizing MW and GD. (draft notes)
    
    • 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.
  
  
• Spring Break!!!
  
  
• Week #8: Convex Optimization (Contd.)
  
  
  • Lecture 21. (Mar 14) The Centroid and Ellipsoid Algorithms (draft notes)
    
    • 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 22. (Mar 16) Ellipsoid (contd) (draft notes for Ellipsoid same as last lecture)
    
  
  
  • Lecture 23. (Mar 18) Interior-point Methods (finish) (handwritten notes we followed today, and draft notes from last year)
    
    • 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: Approximation and Online Algorithms
  
  
  • Lecture 24. (Mar 20) Approximation Algorithms for Set Cover and Bin Packing (draft notes)
    
    • The Shmoys and Williamson textbook on approximation algorithms.
    • Our approximation algorithms course from 2021, and older courses from 2005 and 2008.
    • The bin-packing algorithm of Fernandez de la Vega and Lueker (notes)
      And the recent improvements of Hoberg and Rothvoss.
  
  
  • Lecture 25. (Mar 22) Approximation Algorithms for Bin Packing (end), MaxCut and Coloring (draft notes)
    
    • 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).
  
  
  • Lecture 26. (Mar 24) Online Algorithms and Competitive Analysis (draft 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.
  
  
• No class during the Week of Mar 27.
  
  
• Week #10: Listener's Choice
  
  
  • Lecture 27. (Apr 3) The Sums-of-Squares Paradigm (some handwritten notes)
    
    • Pravesh's Proofs vs Algorithms: The Sum-of-Squares Method course (with videos).
    • 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)
    • Claus Scheiderer's Guide to Positivity and sums of squares has many results about Null-satze and P-satze.
  
  
  • Lecture 28. (Apr 5) Martingale Concentration Bounds (draft notes)
    
    • For more discussion (and applications) of Martingales, see our randomized algorithms course.
    • We did not get to using Martingales in our discrepancy minimization algos; see here for notes.
  
  
  • No class on Friday Apr 7.
    
    
• Week #11: Listener's Choice (contd.)
  
  
  • Lecture 29. (Apr 10) Introduction to Expanders and High-dimensional Expanders (draft notes)
    
    • Dan Spielman's book on Spectral Graph Theory.
    • Lap Chi Lau's course on Eigenvalues and Polynomials.
    • The Hoory, Linial, and Wigderson survey paper on Expander graphs.
  
  
  • Lecture 30. (Apr 12) High-dimensional Expanders and Sampling Matroid Bases (draft notes)
    
    • Courses on HDXs by Irit Dinur, Gil Kalai and Alex Lubotzky, Shayan Oveis Gharan, Max Hopkins and Shachar Lovett.
    • Simons Institute program on Error-Correcting Codes and High-Dimensional Expansion.
    • Summer school on Rapid Mixing using Polynomial Methods.
  
  
  • End of Course!!!