Graphs, Optimization, Geometry, and Fast Algorithms
Yang Liu (Stanford University)
Colloquium
Monday, February 27, 2023, 3:30 pm
Abstract
Discrete combinatorial structures such as graphs and Boolean matrices are prevalent in modern computation. The massive size of modern data motivates the design of efficient algorithms for processing these combinatorial datasets. In this talk, I will describe how to use techniques from continuous optimization and geometry to gain insights into the structure of problems in these combinatorial settings. Using these insights, I will present new efficient algorithms for several fundamental problems at the intersection of combinatorial algorithms, continuous optimization, and high-dimensional geometry, including maximum flows in almost linear time, discrepancy minimization, and linear regression. We conclude by discussing the exciting new lines of research and open problems that these techniques have opened up.
Bio
Yang P. Liu is a fifth year PhD student at Stanford advised by Aaron Sidford. He completed his undergraduate studies at MIT in 2018. He has broad interests in computer science, and his research focuses on the design of efficient algorithms based on graph theory, convex optimization, and high-dimensional geometry. His work has been recognized by ITCS and STOC best student paper awards, and a FOCS best paper award.