### Thursday, December 8, 2016 - 10:00am to 11:00am

### Location:

8102 Gates & Hillman Centers### Speaker:

SHEN CHEN XU, Ph.D. Student http://www.cs.cmu.edu/~shenchex/Recent progresses on a number of combinatorial and numerical problemsvbenefited 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 symmetric and diagonally dominant (SDD) linear systems. In this thesis proposal we focus on a number of combinatorial building blocks of spectral graph theory as well as their applications in solving SDD linear systems. We give new (and often parallel) algorithms for low diameter decompositions, low stretch tree embeddings, graph spanners, and combinatorial sparsifiers. We propose to improve our techniques developed in solving the above problems to data sensitive metrics, in particular the nearest neighbor metric or equivalently the edge squared metric, when vertices are samples from some probability distribution. Wealso propose to investigate spectral methods for partitioning probability distributions in Euclidean domains from random samples. Thesis Committee:Gary Miller (Chair)Bernhard HaeuplerDaniel SleatorNoel J. WalkingtonIoannis Koutis (University of Puerto Rico) Copy of Proposal Document