Shen Chen Xu

Exponential Start Time Clustering and its Applications in Spectral Graph Theory Degree Type: Ph.D. in Computer Science
Advisor(s): Gary Miller
Graduated: August 2017

Abstract:

Recent progress 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. This led to the first nearly linear time solvers for graph Laplacians as well as 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

• An improved parallel algorithm for low diameter decomposition via exponential shifts.
• A 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 fast 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 achieve complexities that are nearly linear in the input size in order to be scalable to the ever-growing amount of data and problem sizes in this day and age.

Thesis Committee:
Gary L. Miller (Chair)
Bernhard Haeupler
Daniel D.K. Sleator
Noel J. Walkington
Ioannis Koutsis (University of Puerto Rico)

Frank Pfenning, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

Keywords:
Spectral Graph Theory, Exponential Start Time Clustering, Graph Spanners, Spectral Graph Sparsification, Low Stretch Tree Embeddings, Hopsets