STOC2021

Towards tight bounds for spectral sparsification of hypergraphs

Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida

18 citations

Abstract

Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently been extended to hypergraphs, which are much richer and may offer new applications. However, the current bounds on the size of hypergraph sparsifiers are not as tight as the corresponding bounds for graphs.