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 (ϵ,δ)-spectral sparsifier with multiplicative error ϵ and additive error δ that has O(ϵ^{-2} n log n log r log(1+ϵW/δn)) hyperedges with high probability, where ϵ,δ ∈ (0,1), n is the number of nodes, and W is the sum of edge weights. The space complexity of our algorithm is O(n2), while previous algorithms require the space complexity of Ω(m), where m is the number of hyperedges. This provides an exponential improvement in the space complexity since m can be exponential in n. Based on a joint work with Tasuku Soma and Kam Chuen Tung.