Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification

2022/09/21 by Jambulapati, Arun, Liu, Yang P., Sidford, Aaron · 5 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2209.10539

Abstract

We present an algorithm that given any n-vertex, m-edge, rank r hypergraph constructs a spectral sparsifier with O(n ε^-2 log n log r) hyperedges in nearly-linear \widetildeO(mr) time. This improves in both size and efficiency over a line of work (Bansal-Svensson-Trevisan 2019, Kapralov-Krauthgamer-Tardos-Yoshida 2021) for which the previous best size was O(min\n ε^-4 log³ n,nr³ ε^-2 log n\) and runtime was \widetildeO(mr + n^O(1)). Independent Result: In an independent work, Lee (Lee 2022) also shows how to compute a spectral hypergraph sparsifier with O(n ε^-2 log n log r) hyperedges.

Cited by

• Sparsification of sums with respect to convex cones
• Fully Dynamic Spectral Sparsification for Directed Hypergraphs
• Hedgegraph Polymatroids
• Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
• Sparsifying Cayley Graphs on Every Group

Related

• Spectral hypergraph sparsification via chaining
• Online Algorithms for Spectral Hypergraph Sparsification
• Spectral Hypergraph Sparsifiers of Nearly Linear Size
• Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
• Towards Tight Bounds for Spectral Sparsification of Hypergraphs