Advanced Graph Algorithms and Optimization, Spring 2026


Lecturers: Rasmus Kyng and Maximilian Probst, with guest lectures by Shunhua Jiang
Teaching Assistants: Simon Meierhans, Gernot Zöcklein, Yu-Cheng Yeh, Vasileios Vasilakis, Lorenzo Battini, Tim Rieder
Time and Place: Mondays 10:00-12:00 at ML F 39 (always) and Tuesdays 16:00-18:00 at CAB G 61 (every other week, see schedule)
Exercise Session Time and Place: Fridays 14:00-16:00 at CAB G 51
ECTS credits: 10 credits
Final deregistration date: April 10th

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 second-order optimization, convex duality, multiplicative weights and dual-based methods, acceleration, preconditioning, and non-Euclidean 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.

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

Performance Assessment

Graded Homework 1 (out approx. March 31st, due April 14th): 15% of the grade. The homework consists of exercises.

Graded Homework 2 (out approx. May 5th, due May 19th): 15% of the grade. The homework consists of exercises.

Oral Exam (May 26th, 27th & 28th): 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.

Bonus points (weekly exercises): Bonus up to 5% of the grade. A subset of the weekly exercises are marked with bonus points. Answering all these correctly will add points corresponding to 5 % of the total points in the course, but not answering them will not give a penalty. This bonus may increase your grade by up to 0.25. You can still get a 6 without getting any bonus points. In total, there will be 10 exercise sheets. If you hand in more than 8 exercise sheets, we consider the best 8 submissions to determine the bonus.

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!

Bonus points from weekly exercises: To get bonus points from weekly exercises, you have to solve the particular exercises marked with bonus points. These are always clearly labelled. To get points, you must turn in your exercise sheet on time, as per the deadline above.

Tentative Schedule of Lectures and Exercises

Date

Lecture

Topic

Problem Sets and Graded Homework

02/16 Mon

1

Introduction


02/17 Tue

2

Basic Optimization and Linear Algebra


02/23 Mon

3

Convexity, Second Derivatives, Gradient Descent


02/24 Tue

no lecture



03/02 Mon

4

Acceleration


03/03 Tue

5

Spectral Graph Theory


03/09 Mon

6

Effective Resistances, Gaussian Elimination as Optimization


03/10 Tue

no lecture



03/16 Mon

7

Cheeger's Inequality and Introduction to Expanders


03/17 Tue

8

Random walks


03/23 Mon

9

Introduction to Random Matrices


03/24 Tue

no lecture



03/30 Mon

10

Additive Gaussian Elimination and Introduction to Random Matrices


03/31 Tue

11

Solving Laplacian Linear Systems


04/06 Mon

EASTER



04/07 Tue

EASTER



04/13 Mon

12

Classical Maxflow 1


04/14 Tue

13

Classical Maxflow 2


04/20 Mon

SECHSELÄUTEN



04/21 Tue

no lecture



04/27 Mon

13

Expander’s & Sparsest Cuts via the Cut-Matching Framework


04/28 Tue

14

Fenchel Conjugates, Newton's Method


05/04 Mon

15

IPM for Maximum Flow 1


05/05 Tue

16

IPM for Maximum Flow 2


05/11 Mon

17

Low Diameter Decompositions


05/12 Tue

no lecture



05/18 Mon

18

Negative SSSP


05/19 Tue

19

Graph Matchings


05/22 Fri

20

Course Review


05/26 Tue

EXAMS



05/27 Wed

EXAMS



05/28 Thu

EXAMS