Schedule (tentative):Flow and cut problems on graphs are among the most fundamental and extensively studied problems in Operations Research and Optimization, playing a foundational role in both the theory and practice of algorithm design. While the classical algorithms for these problems were largely based on combinatorial approaches, the past several years have witnessed the emergence of a powerful collection of new techniques based on geometry, spectral graph theory, numerical linear algebra, randomization, and iterative methods from continuous optimization. These have allowed researchers to provide better provable algorithms for a wide range of graph problems, in some cases breaking algorithmic barriers that had stood for several decades.
The aim of this workshop will be provide a coherent picture of these new algorithmic techniques and their recent applications, along with some of their connections to other fields, such as geometry, numerical analysis, and machine learning. The hope is that exposing the core ideas that have enabled these developments will both lead to further advances in graph algorithms and facilitate their application in other settings.
Time Speaker Title 9:50-10:50 Jonathan Kelner Bridging the Numerical and the Combinatorial:
Emerging Tools, Techniques, and Design Principles for Graph Algorithms11:00-12:00 Aaron Sidford Efficient Oblivious Routing:
Computing Crude Approximations for Flow and Cut Problems in Almost-Linear Time12:00-2:00 Lunch break (on your own) 2:00-3:00 Yin Tat Lee Smooth Convex Optimization and its Applications to Graph Algorithms 3:00-3:20 Break 3:20-4:20 Aleksander Madry Electrical Flows, Interior-Point Methods, and the Maximum Flow Problem 4:30-5:30 Lorenzo Orecchia Iterative Methods and Regularization in the Design of Graph Algorithms:
a Unified Framework for Optimization and Online Learning Beyond Multiplicative Weight Updates