Exponential Start Time Clustering and its Applications in Spectral Graph Theory
Recent progresses on a number of combinatorial and numerical problems benefited from combining ideas and techniques from both fields to design faster and more powerful algorithms. A prime example is the field of spectral graph theory, which involves the interplay between combinatorial graph algorithms with numerical linear algebra, and this led to the first nearly linear time solvers for graph Laplacians and symmetric and diagonally dominant (SDD) linear systems.
In this thesis we present several combinatorial algorithms that allow us to tap into spectral properties of graphs. In particular we present:
- Improved parallel algorithm for low diameter decomposition via exponential shifts. - Parallel algorithm for graph spanners with near optimal stretch trade-offs and its application to spectral graph sparsification. - Improved low stretch tree embeddings that are suitable for nearly linear time graph Laplacian solvers. - Work efficient parallel algorithms for hopset and approximate shortest path.
A common goal we strive for in the design of these algorithms is to have complexity nearly linear in the input size and to be work efficient, in order to be scalable to the evergrowing amount of data and problem sizes in this day and age.
Thesis Committee: Gary Miller (Chair) Bernhard Haeupler Daniel Sleator Noel J. Walkington (Math) Ioannis Koutis (University of Puerto Rico)