Graph Structure via Exact Gaussian Elimination

Aaron Schild (UC Berkeley) 14:00 -- 15:00

Graph partitioning has played an important role in theoretical computer science, particularly in the design of approximation algorithms and metric embeddings. In this talk, we revisit some of these applications from the perspective of Gaussian elimination, particularly in the context of random spanning tree generation and oblivious routing. In the process, we will see how fundamental tradeoffs in graph partitioning can be overcome by eliminating vertices from an undirected graph using Gaussian elimination on the associated Laplacian matrix.