Online Algorithms for Spectral Hypergraph Sparsification

We provide the first online algorithm for spectral hypergraph sparsification. In the online setting, hyperedges with positive weights are arriving in a stream, and upon the arrival of each hyperedge, we must irrevocably decide whether or not to include it in the sparsifier. Our algorithm produces an (epsilon, delta)-spectral sparsifier with multiplicative error e and additive error delta that has O(epsilon(-2) n log n log r log(1+ epsilon W/delta n)) hyperedges with high probability, where epsilon, delta is an element of (0, 1), n is the number of nodes, r is the rank of the hypergraph, and W is the sum of edge weights. The space complexity of our algorithm is O(n(2)), while previous algorithms required space complexity Omega(m), where m is the number of hyperedges. This provides an exponential improvement in the space complexity since m can be exponential in n.