  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 $\epsilon$
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 \in (0,1)$, $n$ is the number of nodes, and $W$ is the sum of edge
weights. The space complexity of our algorithm is $O(n^2)$, while previous
algorithms require the space complexity of $\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$.
