Please note: This PhD seminar will take place online.
Kam Chuen Tung, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Lap Chi Lau
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 (eps, delta)-spectral sparsifier with multiplicative error eps and additive error delta that has O(eps^{-2} n log n log r log (1 + eps*W / (delta*n))) hyperedges with high probability, where 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.