15-850: Advanced Algorithms, Fall 2018

Lecturer: Anupam Gupta, GHC 7203.

TAs: Jason Li, Goran Zuzic

Office hours: Anupam: Tue 4-5 p.m. in GHC 7203, Jason: Thu 10–11 a.m. in GHC 7607, Goran: Wed 5–6 p.m. in GHC 7515

Location: GHC 4211, MWF 1:30-2:50 (note: 3 days a week)

Blog: https://cmualgos.github.io/

Piazza: here

Gradescope: Use course code 92K6XG to enroll.

Announcements

• All announcements will be on Piazza, please make sure you're signed up there!
• A preliminary schedule for the lectures. Please sign up to scribe!

Homeworks

• Homework 0 (due Friday, August 31)
• Homework 1 (due Thursday, September 13)
• Homework 2 (due Thursday, September 27)
• Homework 3 (due Thursday, October 11)
• Homework 4 (due Sunday, October 28)
• Homework 5 (due Sunday, November 18)

Lectures

• Week #1: Spanning Trees
  
  
  • Lecture 1. (Aug 27) MSTs. Recap Prim/Kruskal/Boruvka. The Fredman-Tarjan \(O(m \log^\star n)\) time algorithm. The Karger-Klein-Tarjan randomized algorithm (my notes det, rand, prelim scribe notes)
    
    Deterministic MSTs:

    • 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.

    Randomized MSTs:

    • The Karger-Klein-Tarjan paper. Timothy Chan has a different proof of the sampling lemma.
    • Notes on Komlos' MST verification algorithm from the S15 course.
    • The Komlos, King, and Hagerup papers on MST verification. Uri Zwick's notes on MST verification.
  
  
  • Lecture 2. Directed MSTs (aka Arborescences and Branchings). LP approaches. (my notes, my LP notes, Corwin's scribe notes, slides, blog post)
    
    References on 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.

    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.
  
  
  • Lecture 3. Dynamic Graph Connectivity algorithms. Frederickson, Kapron et al., Holm et al. (my notes, Justin's and Anish's unedited scribe notes, blog post)
    
    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.
    • Recent progress on worst-case dynamic MST by Nanongkai and Saranurak and Wulff-Nilsen, FOCS 2017.

    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 Demaine.)
  
  
• Week #2: Shortest-Path Trees
  
  
  • Lecture 4: Shortest Paths. Seidel's algorithm for (unweighted undirected) APSP using matrix multiplication. (my notes, Alireza's scribe notes, slides, blog post)
    • 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.
    • 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: Low-stretch Trees. Bartal's construction. [Jason guest-lecturing!] (Anupam's notes, Roie's scribe notes, blog post)
    • 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: Matchings in Graphs: combinatorial algorithms (my notes, (unedited) Vy's scribe 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.
    • Direct proofs of the Tutte-Berge formula from Lex Schrijver, Doug West, Andrei Kotlov.
  
  
  • Lecture 7: Matchings in Graphs: Linear Programs and Integrality of Polytopes (my LP notes, my matching polytope notes, (unedited) Greg's scribe notes, blog post)
    • Notes from our LP/SDP course on the integrality of the non-bipartite perfect matching polytope.
    • Edmonds: Maximum matching and a polyhedron with 0,1 vertices.
      This gives a combinatorial algorithm to find a max-weight matching in general graphs, which we did not see. Of course, you can just solve the LP to find a vertex solution, and it will be integral.
  
  
  • Lecture 8: Matchings in Graphs: Algebraic Algorithms (my notes, old scribe notes, blog post)
    • 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 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.
  
  
• Week #4: Concentration of Measure and Dimension Reduction Techniques
  
  
  • Lecture 9 (9/17): Concentration of Measure: "Chernoff-Hoeffding" Bounds. (my notes, (unedited) Sarthak's scribe notes)
    • A gentle introduction to the probabilistic method 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, 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 10: (9/19) Dimension Reduction: Johnson-Lindenstrauss and related topics (my notes, old scribe notes)
    • 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.

    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: near-neighbor search, robust concept learning and mixtures of Gaussians. There are many other application papers.
  
  
  • Lecture 11 (9/21): Dimension Reduction: Singular Value Decompositions (my notes, old scribe notes)
    • My lecture was partly based on Chapter 3 in the Blum-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^\intercal A\).
    • 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)
  
  
• Week #5: Fixed-Parameter Algorithms and More Large-Deviation Bounds
  
  
  • Lecture 12: (9/24) FPT Algorithms: Color-Coding, Branching, Kernelization. [Jason guest-lecturing!] (Jason's notes, (unedited) David, George, and Mounira's scribe notes)
  • Well-written, thorough introduction to FPT algorithms: Cygan et al. textbook. We covered Sections 2.2.1, 3.1, 5.2.1.
  
  
  • Lecture 13: (9/26) Algorithmic Graph Theory: Treewidth and Planarity [Jason guest-lecturing!] (Jason's notes, (unedited) Benjamin and Yao Chong's scribe notes)
  • Well-written introduction to treewidth: Cygan et al. textbook, Chapter 7
  • Computing treewidth: a simple 4-approximation to treewidth: Chapter 7.6 of the textbook
  • Baker's technique: Section 11.3 of Jeff Erickson's notes
  
  
  • Lecture 14: (9/28) Applications of Concentration Inequalities [Goran guest-lecturing!] (Goran's notes, blog post, Ziye and Tai's scribe notes)
  • Discrepancy lecture notes by Nikhil Bansal (including algorithmic considerations)
  • Introduction to Martingales by Karl Sigman
  • The "Abracadabra problem", a surprising application of martingales. Notes by Adam Lelkes.
  • Using random walks for 2-SAT and 3-SAT. Lecture notes by Shachar Lovett.
  
  
• Week #6: Online Learning and Using it to Solve LPs
  
  
  • Lecture 15 (10/1): Online Learning and the Multiplicative Weights Framework (old notes from the LP/SDP course, old scribe notes)
  • Avrim's slides from 15-451 (F13).
  • The Arora-Hazan-Kale survey.
  
  
  • Lecture 16 (10/3): Applications of MW: zero-sum-games, solving LPs (my notes, Paul's scribe notes, blog post)
  • 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.
  
  
  • Lecture 17 (10/5): Applications of MW: max-flows using electrical flows. (electrical flow notes, Chun Kai's and Hoon's scribe notes, blog post)
  • Derivation of the regret bound when losses are not in \([-1,1]^N\) but in \([-\gamma, \rho]^N\).
  • 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 approach for max-flows via electrical flows, by Lee, Rao, and Srivastava.
  
  
• Week #7: Convex Optimization: First-Order Methods and Connections to Online Learning
  
  
  • Lecture 18 (10/8): Gradient Descent. Yet another low-regret algorithm. (my notes, older handwritten notes, Daniel's and Mark's scribe notes)
    • 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 (10/10): Mirror Descent: generalizing MW and GD. (my notes, Eliot's and Tai's unedited scribe notes, blog post)
    Potential function proofs of first-order methods by Nikhil Bansal and myself.
    Our presentation is inspired by Sebastien Bubeck's.
    Elad Hazan and Shai Shalev-Shwartz present it using the equivalence to Follow the Regularized Leader.
    We did not talk about this connection, but you may see this as a HW problem, time permitting.
  
  
  • Lecture 20 (10/12): Mirror Descent: generalizing MW and GD (contd.) (my notes, Eliot's and Tai's unedited scribe notes (contd.))
    We will cover the mirror-map based proof, and other details we skipped over today.
    See the references above.
  
  
• Week #8: Linear and Convex Optimization: Polynomial-time Algorithms
  
  
  • Lecture 21 (10/15): The Center-of-Gravity and Ellipsoid Algorithms (my notes, old scribe notes)
    • 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.
    • Since we refer to Gaussian Elimination all the time, notes by Laci Lovasz and Peter Gacs.
    
    
  • Lecture 22 (10/17): Interior-point Methods: an overview (my notes, Di's and Jalani's (unedited) scribe notes, blog post)
    • Notes from the Matousek and Gaertner book (to scan)
    • Notes from our LP/SDP course, for Renegar's original algorithm.
    • Books by Jim Renegar, Steven Wright.
    • Lecture notes by Yuri Nesterov and Arkadi Nemirovski, and Ben-Tal and Nemirovski.
    • Survey/tutorial by Todd and Nemirovski (2009).
    
    
  • October 19: Mid-Semester Break!
  
  
• Week #9: Approximation and Online Algorithms
  
  
  • Lecture 23 (10/22): Approximation Algorithms (Hang's and Zhen's (unedited) notes, blog post)
  • The Shmoys and Williamson textbook on approximation algorithms.
  • Our approximation algorithms 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 24 (10/24): Online Algorithms: Rent-or-Buy and Paging, Online Primal-Dual (my notes, Thomas' (unedited) notes, blog post)
  • 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 25 (10/26): Online Algorithms using Projections (blog post)
  (Given the university holiday, this lecture is optional, you will not be evaluated on it.)
  • We will talk about results from this preprint.
  • Blog post on the method of Lagrange multipliers.
  • The preprint above directly builds on papers by Bubeck et al., and Buchbinder, Chen and Naor, among others.
  • A workshop to bring together online learning and online algorithms.
  • Seffi Naor's slides (1, 2, 3) on online primal-dual from here, and a monograph by Niv Buchbinder and Seffi.
  
  
• Week #10: Listeners' Choice Week


• Lecture 26 (10/29): Approximation Algorithms using Semidefinite Programming (Alex's and Pedro's (unedited) notes, my notes)
• MaxCut: notes on the GW analysis, integrality gap, UG hardness. (The latter notes are from our advanced approx.algos course).
• Some notes on the Karger Motwani and Sudan result on coloring 3-colorable graphs.
  The latest step in the series of improvements is by Kawarabayashi and Thorup getting \(n^{1/5-\epsilon}\) colors.
And more background on SDPs and their duality:
• 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.
• Farid Alizadeh's page of SDP references.


• Lecture 27 (10/31): Semidefinite Programming: Duality and SOS (my notes, blog post)
• Please see the references for lecture 26; more to come.


• Lecture 28 (11/02): Decision-making under uncertainty: the secretary and the prophet inequality problems (blog post)
• A short introduction to secretary problems and prophet inequalities; from the IPCO 2017 summer school.

Description

An intensive graduate course on the design and analysis of algorithms, picking up from where 15-451 stopped. It will be more specialized and in-depth than the Graduate Algorithms course 15-750. We will cover advanced algorithmic ideas (some classical, some very recent), and the theory behind it (theorems, proofs). For topics that were covered in 451/750, the goal is to cover advanced content and new techniques.

Syllabus

1. MSTs. Recap Prim/Kruskal/Boruvka, an \(O(m \log^\star n)\) time algorithm, a randomized linear-time algorithm, MSTs in directed graphs
2. Shortest paths. recall Dijkstra/Bellman-Ford/etc, Seidel's algorithm using matrix multiplication, Williams' subcubic APSP algorithm for general graphs.
3. Matchings: classical matchings using augmenting paths, matching using matrix inversions (Tutte/Lovasz, Mucha-Sankowski), matchings using random walks.
4. The Experts algorithm via multiplicative weights, online gradient descent.
5. Flows: max-flows via electrical flows, Sherman's near-linear time max-flow.
6. Linear and Convex Programming
• Solving convex optimization problems via gradient descent, ellipsoid, interior-point methods
• Using convex optimization to solve combinatorial problems (maybe)
7. High-dimensional geometry: Dimension reduction and singular value decompositions.
8. Fixed-parameter tractable algorithms.
9. Streaming algorithms (a.k.a. algorithms for big data)
10. Online algorithms
11. Approximation Algorithms
12. The Sums-of-Squares Paradigm
13. Submodular Optimization

Effort and Criteria for Evaluation:

We have 3 lectures a week for the first ~10 weeks of the semester. Attendance is required. You will scribe 1-2 lectures in Latex: either you will polish/augment old lecture notes, or will write new notes. We have ~7 HWs (including HW0), half solved with collaboration, others solved individually. Your grade will depend on these HWs, scribe notes, class participation, and attendance.

Textbook:

There is no textbook for the course. Most of our material is not in textbooks (yet), so we will rely on papers, monographs, and lecture notes.

Prerequisites:

You should know material in standard UG courses in algorithms, probability, and linear algebra very well. Above all, mathematical maturity/curiosity and problem-solving skills are a must. That way you can make up for gaps in your knowledge yourself. It is natural to not know everything, or for you to get rusty on concepts, but you should learn how to learn. This may seem vague, so here are concrete things.

• You should know material from an undergraduate Algorithms course, say until Lecture 16 (P/NP) from our Spring 2018 version of 15-451. You should definitely know DP, flows, basics of linear programming, duality, etc. If not, please pick these up from the 451 lecture notes/textbooks/Wikipedia/Khan Academy.
• Same for undergraduate probability and linear algebra courses. E.g., for LinAlg, see whether you can solve the first homework from Steve Vavasis' Optimization course at Waterloo. For probability (and randomized algorithms), I will give some problems in HW0.
• HW0 will make an attempt to test this preparedness, and to give you and us feedback. Students late in submitting HW0 will risk being dropped from the course (we are over-subscribed, and have a wait-list), sorry! So talk to us in Lecture #1 if you have a good reason for being late.

FAQs:

• Q: Will you give the real-world context for the algorithms you cover?
  This class will focus on the theoretical side, so we will not have much time to motivate the choice of topics or give much real-world context (of which there is plenty). If you are looking for the latter, you should consider taking 15-853: Algos in the Real World.


• Q: I am on the wait-list: will I get in?
  We hope everyone who wants to take the class will get in. (Usually some students are "shopping around" in the first couple weeks, and things settle down after that.) Just come to the lectures, and we will try to get clear the wait-lists soon. OTOH, if you are on the wait-list because you have too many credits, or are enrolled for a course with a conflicting time-slot, you should fix those issues yourself.


• Q: I am struggling with the homework: what should I do?
  A little struggle in doing the homework is expected (and healthy), since these are not trivial problems, you're probably learning something new. However, if you are struggling a fair bit, or if the struggle is unpleasant for you, come talk to us. You may consider taking 15-451 (UG Algos) or 15-750 (Graduate Algos) instead of this course.

Your Health & Well-being

This is an intensive (and somewhat intense) course: 3 days a week, studying new/advanced topics, several HWs. One major goal is that you will have fun taking it and learning this new cool material, as much as I hope to have fun teaching it. Part of making sure you have fun involves taking care of yourself. Do your best to maintain a healthy lifestyle this semester by eating well, exercising, avoiding drugs and alcohol, getting enough sleep and taking some time to relax. This will help you achieve your goals and cope with stress.

If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support. Counseling and Psychological Services (CaPS) is here to help: call 412-268-2922 and visit http://www.cmu.edu/counseling/. Consider reaching out to a friend, faculty or family member you trust for help getting connected to the support that can help.

Accommodations for Students with Disabilities:

If you have a disability and are registered with the Office of Disability Resources, I encourage you to use their online system to notify me of your accommodations and come and see me to discuss your needs with me as early in the semester as possible. Since this is a fast-moving course, we should discuss how to make things work out. I will work with you to ensure that accommodations are provided as appropriate. If you suspect that you may have a disability and would benefit from accommodations but are not yet registered with the Office of Disability Resources, I encourage you to contact them at access@andrew.cmu.edu.

Academic Integrity