1

Online Algorithms for Spectral Hypergraph Sparsification

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.

Oct 1, 2023
Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues

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

Jun 15, 2023
Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues

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

Nov 1, 2022
Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues

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.

Apr 1, 2022