BARC talk by Timothy Chu

Friday, January 25th, Timothy Chu, graduate research assistant, School of Computer Science, Carnegie Mellon University, Pittsburgh, will give a talk in BARC "Graph Sparsification via Short Cycle Decomposition"

Titel

Graph Sparsification via Short Cycle Decomposition

Abstract

We introduce short cycle decompositions -- a decomposition of a graph into edge-disjoint cycles of nearly constant length, plus a small number of extra edges, and give fast algorithms for computing such a decomposition. We utilize these decompositions to prove several new results in graph sparsification, including:

- Finding sparse spectral sparsifiers of a graph, with the same degrees as the original graphs.
- Finding very sparse graphs whose effective resistances are similar to the effective resistance of the original graph.
- Computing effective resistances of all edges in a graph, in the fastest known time.
And more.

This is joint work with Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, and Junxing Wang, and appeared in FOCS 2018.

Bio

Timothy Chu is a PhD student at Carnegie Mellon, advised by Dr. Gary Miller. His interests include spectral graph theory, linear system solving, computational geometry, and data structures. Outside of academics, he’s very interested in different cultures and world history, and always welcomes a chat about topics like those!