Spectral Clustering Oracles in Sublinear Time

Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi +2

Given a graph $G$ that can be partitioned into $k$ disjoint expanders with outer conductance upper bounded by $\epsilon \ll 1$, can we efficiently construct a small space data structure th…