Towards tight bounds for spectral sparsification of hypergraphs
Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida · 2021
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.