Advanced Graph Algorithms and Optimization, Spring 2024
 Lecturers: Rasmus Kyng and Max Probst
 Teaching Assistants: Simon Meierhans, Federico Soldà, Gernot Zöcklein, Yves Baumann and Daoyuan Chen
 Time and Place: Mondays 10:0012:00 at ML F 39 (always) and Tuesdays 16:0018:00 at CAB G 51 (every other week, see schedule)
 Exercise Session Time and Place: Fridays 14:0016:00 at LFW B 1
 ECTS credits: 10 credits
 Final deregistration date: April 8th

Course Objective: The course will take students on a deep dive into modern approaches to graph algorithms using convex optimization techniques. By studying convex optimization through the lens of graph algorithms, students should develop a deeper understanding of fundamental phenomena in optimization. The course will cover some traditional discrete approaches to various graph problems, especially flow problems, and then contrast these approaches with modern, asymptotically faster methods based on combining convex optimization with spectral and combinatorial graph theory.

Course Content: Students should leave the course understanding key concepts in optimization such as first and secondorder optimization, convex duality, multiplicative weights and dualbased methods, acceleration, preconditioning, and nonEuclidean optimization. Students will also be familiarized with central techniques in the development of graph algorithms in the past 15 years, including graph decomposition techniques, sparsification, oblivious routing, and spectral and combinatorial preconditioning.

Prerequisites: This course is targeted toward masters and doctoral students with an interest in theoretical computer science. Students should be comfortable with design and analysis of algorithms, probability, and linear algebra. Having passed the course Algorithms, Probability, and Computing (APC) is highly recommended, but not formally required. If you are not sure whether you are ready for this class or not, please consult the lecturer.

Literature:
 Convex Optimization
by Stephen Boyd and Lieven Vandenberghe.
 This book is a helpful reference for convex optimization.
 Differential Calculus by Henri Cartan.
 If you have a powerful urge to learn all about multivariate calculus, you can start here. You shouldn't need it for the course though.

Convex Analysis by Rockafellar.
 This is the classic text on basic convex analysis (not optimization). Again, you shouldn't need this.
 Convex Optimization
by Stephen Boyd and Lieven Vandenberghe.
Course Moodle
You can ask the course TAs and instructors about the course materials, exercises, and any other issues on the course Moodle page (link).
Please make sure you receive Moodle notifications from this course as some announcements will be made exclusively through Moodle.
Notes
The notes are available here (link).
These notes will be updated throughout the course. There may sometimes be a delay between a lecture being held and the corresponding Chpt. being added to the notes.
You can find the notes for an earlier version of the course here: AGAO 2023. Note that some material may change this year.
Performance Assessment
Graded Homework 1 (out approx. March 25th, due April 16th): 15% of grade. The homework consists of exercises.
Graded Homework 2 (out approx. May 13th, due June 10th): 15% of grade. The homework consists of exercises.
Oral Exam (May 27th, 28th & 29th): 70% of the grade. The exam will last 15 minutes. We will mainly discuss topics from the lectures, but may ask questions about problems from the first graded homework assignment.
Graded Homework
Each graded homework assignment accounts for 15% of your grade. You should submit your solutions as a PDF typeset in LaTeX by the listed due date, 23:00 local time in Zurich, by submitting them through the course Moodle page. You must come up with the solutions on your own and write everything yourself.
Exercises
Every week we will publish a problem set consisting of exercises designed to help you understand
the course
material.
The exercises will not count toward your grade, but you are highly encouraged to solve them all.
Exercises will be published on Wednesdays on the course Moodle. You have until Thursday the following week to hand
in you solution.
The TAs will discuss solutions to the exercises one and a half weeks after they were initially published.
Part of the exercise session will be reserved for working on the current exercise sheet (published 2 days before).
The TAs will offer hints and support when needed and you're welcome to form and work in groups.
If you wish to get feedback on your problem set solutions, you must submit solutions either as a PDF typeset in
LaTeX
or in readable handwritten form
by Thursday, 23:59 local time in Zurich, by submitting them through the course Moodle page.
You're welcome to work with your classmates on these problem sets!
Tentative Schedule of Lectures and Exercises
Date  Lecture  Topic  Problem Sets and Graded Homework 

02/19 Mon  1  Introduction  Problem Set 1 
02/20 Tue  2  Basic Optimization and Linear Algebra  Solution 1 
02/26 Mon  3  Convexity, Second Derivatives, Gradient Descent  Problem Set 2 
02/27 Tue  no lecture  Solution 2  
03/04 Mon  4  Spectral Graph Theory  Problem Set 3 
03/05 Tue  5  Cheeger’s Inequality, Sparsest Cut and Expanders  Solution 3 
03/11 Mon  6  Effective Resistances, Gaussian Elimination as Optimization  Problem Set 4 
03/12 Tue  no lecture  Solution 4  
03/18 Mon  7  Intro Random Matrices  Problem Set 5 
03/19 Tue  8  Additive Gaussian Elimination  Solution 5 
03/25 Mon  9  Solving Laplacian Linear Equations  GHW 1 out 
03/26 Tue  no lecture  
04/01 Mon  Easter  
04/02 Tue  Easter  
04/08 Mon  10  Classical Maxflow 1  Problem Set 6 
04/09 Tue  11  Classical Maxflow 2  Solution 6 
04/15 Mon  no lecture (Sechseläuten)  Problem Set 7  
04/16 Tue  12  LinkCut tree for Speeding up Dinic’s algorithm  GHW1 due Solution 7 
04/22 Mon  13  Expander’s & Sparsest Cuts via the CutMatching Framework  Problem Set 8 
04/23 Tue  14  Distance Oracles (+ Routing)  Solution 8 
04/29 Mon  15  The Separating Hyperplane Theorem, Lagrange Multipliers, Convex duality, KKT conditions.  Problem Set 9 
04/30 Tue  no lecture  Solution 9  
05/06 Mon  16  Fenchel Conjugates & Newton’s method  Problem Set 10 
05/07 Tue  17  IPM for Maximum Flow  Solution 10 
05/13 Mon  18  LowDiameter Decompositions  GHW2 out 
05/14 Tue  no lecture  
05/20 Mon  Whitsuntide  
05/21 Tue  19  Negative SSSP  
05/27 Mon  EXAMS  GHW2 due  
05/28 Tue  EXAMS  
05/29 Weds  EXAMS 