Article Source

• Introduction to Data Structures and Optimization for Fast Algorithms

Introduction to Data Structures and Optimization for Fast Algorithms

• Aaron Sidford (Stanford University)
• Richard M. Karp Distinguished Lecture

Abstract

Over the past decade, there has been a revolution in the theoretical foundations for efficiently solving multiple foundational problems in theoretical computer science. For problems ranging from maximum flow, to global minimum cut, to linear system solving, and beyond, there has been breakthrough after breakthrough in designing algorithms with improved 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.

This suite of algorithmic advances is particularly striking due to the wide range of tools they employ, and the nontrivial interplay between them. These results 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 algorithmic implications have even happened in reverse; for example, optimization techniques have been used in sketching routines and to yield improved dynamic graph algorithms.

This confluence of algorithmic tools is central to the Simons Institute’s Fall 2023 program on Data Structures and Optimization for Fast Algorithms. This talk will introduce this area of research and highlight certain recent advances in bipartite matching, linear programming, and more.

Bio

Aaron Sidford is an assistant professor in the departments of Management Science and Engineering and Computer Science at Stanford University. He received his PhD from the Electrical Engineering and Computer Science Department at MIT, where he was advised by Professor Jonathan Kelner. His research interests lie broadly in the design and analysis of algorithms, optimization theory, and the theory of computation with an emphasis on work at the intersection of continuous optimization, graph theory, numerical linear algebra, and data structures. He is the recipient of a Microsoft Research Faculty Fellowship, a Sloan Research Fellowship, an NSF CAREER award, an ACM Doctoral Dissertation Award honorable mention, and best paper awards in COLT, FOCS, and SODA for work in these areas.

The Richard M. Karp Distinguished Lectures were created in Fall 2019 to celebrate the role of Simons Institute Founding Director Dick Karp in establishing the field of theoretical computer science, formulating its central problems, and contributing stunning results in the areas of computational complexity and algorithms. Formerly known as the Simons Institute Open Lectures, the series features visionary leaders in the field of theoretical computer science, and is geared toward a broad scientific audience.