Spectral hypergraph sparsification via chaining

James R. Lee

In a hypergraph on $n$ vertices where $D$ is the maximum size of a hyperedge, there is a weighted hypergraph spectral $\epsilon$-sparsifier with at most $O(\varepsilon^{-2} \log…