Over the past decade there has been a revolution in the theoretical foundations for obtaining provably fast algorithms for foundational problems in theoretical computer science. For problems ranging from maximum flow, to global minimum cut, to linear system solving, and beyond there have been breakthrough after breakthrough in improving asymptotic running times. Though classic theory had well-established the polynomial time solvability of these problems, the optimal running time for solving them had remained open; excitingly, recent work has shown that some of these problems can be solved in nearly linear time in broad regimes. 

Beyond the foundational nature of these results and the modern motivations for faster algorithms, this suite of algorithmic advances is particularly exciting due to the wide range of tools they employ and the non-trivial interplay between them. These fast algorithms apply continuous optimization methods to solve combinatorial problems, dynamic data structures to solve static problems, sketching techniques to solve problems without memory limitations, and more. In some cases these faster algorithms have then in turn led to improvements for these tools, e.g. optimization techniques have been used in sketching routines and to yield improved dynamic graph algorithms. There have even been recent instances where a large suite of continuous, combinatorial, dynamic data structures, and sketching techniques are all combined for a faster algorithm for a single problem. 

The central goal of the proposed program is to add further fuel to this budding area of research. The program will bring together experts in dynamic graphs, sketching, and optimization towards the common goal of furthering this confluence of advanced algorithmic techniques for breakthrough results. The bootcamp, workshops, and broader program activities will all be designed with the goal of advancing the foundations of each area, developing new connections between the areas, and making new advances at their intersection. 

Click here to subscribe to our news and events to learn more about this and other events.

Organizers: Alina Ene (Boston University), Monika Henzinger (University of Vienna),Yin-Tat Lee (University of Washington), Jelani Nelson (UC Berkeley), Aaron Sidford (Stanford University)

Long-Term Participants (tentative, including Organizers): Alina Ene (Boston University), Monika Henzinger (University of Vienna),Yin-Tat Lee (University of Washington), Jelani Nelson (UC Berkeley), Aaron Sidford (Stanford University)