Abstract
Sparsification is an important and natural algorithmic task in theoretical computer science. In its most general form, we are given a large collection of objects (matrices, norms, convex functions). Our goal is to find a small reweighted subset of the norms which approximately preserves some property of the original set (for example, the sum evaluated at any input point).
In this talk, I will discuss some recent work on constructing small sparsifiers in more general settings. We provide efficient algorithms for constructing near-linear sized spectral sparsifiers for hypergraphs and sums of arbitrary norms using a chaining technique. Additionally, we provide a framework which gives state-of-the art algorithms for linear-size graph sparsification.