Jason Li

Preconditioning and Locality in Algorithm Design Degree Type: Ph.D. in Computer Science
Advisor(s): Anupam Gupta, Bernhard Haeupler
Graduated: August 2021

Abstract:

Algorithms is a broad, rich, and fast-growing field. For the latter half of last century, many branches of algorithms have emerged and grown in popularity, and many different techniques have been invented to solve the central problems in each area. Some of these techniques, such as the push-relabel algorithm for maximum flow, are specially designed to solve a single problem. Other techniques, such as the multiplicative weights update method, are more general and applicable to a wide range of problems. And others, such as dynamic programming, divide and conquer, and linear programming relaxation and rounding, are so fundamental that they have not only pervaded every branch of algorithms, but have ultimately reshaped the way we approach algorithm design.

This thesis is devoted to studying two more modern algorithmic techniques, namely preconditioning and locality, which were pioneered by Spielman and Teng [106] in their ground-breaking work on Laplacian system solvers and have seen countless new applications in the past decade. In this thesis, I successfully apply preconditioning and locality to resolve fundamental open problems from a wide array of algorithmic subfields, from fast, sequential algorithms to deterministic algorithms to parallel algorithms, thereby demonstrating the power and versatility of the two techniques. Taking one step further, I make my case that preconditioning and locality are more than just powerful tools with countless applications: they are new, fundamental ways of thinking about algorithms that have the potential to revolutionize algorithm design just like dynamic programing and divide and conquer had done in the past.

Thesis Committee:
Anupam Gupta (Co-Chair)
Berhard Haeupler (Co-Chair)
Gary L. Miller
Satish Rao (University of California, Berkeley)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Keywords:
Preconditioning, locality, graph algorithms, minimum cut, expander graphs