1

We study spectral sparsification of hypergraphs when the hyperedges arrive one by one, using chaining to obtain a bound on the number of hyperedges using only $O(n^2)$ space.

We obtain almost linear-time algorithms for partitioning directed graphs and hypergraphs using the reweighted eigenvalues SDP relaxation plus $\ell_2^2$ triangle inequalities.

We further extend the concept of reweighted eigenvalues to derive Cheeger’s inequalities for directed graphs and hypergraphs.

We develop the theory of reweighted eigenvalues, from which we derive optimal Cheeger’s inequalities for vertex expansion and obtain vertex analogues of Cheeger generalizations.