Surya Teja Gavva, Rutgers University

Abstract

The solution to the Kadison-Singer problem proves the existence of a subgraph that acts as a spectral sparsifier for a given graph. In this talk, we explore the question of finding such a subgraph efficiently. We provide explicit signings on some classes of graphs and show some algorithms to find the subgraphs in special graphs like circulant graphs and random regular graphs. Particularly interesting is the variety of ideas from Fourier analysis, discrepancy theory, random matrices, and the contiguity of random graph models needed to analyze the problem.

Based on joint work with Peng Zhang.

See: https://theory.cs.rutgers.edu/theory_seminar