4 citations · 4 across the 1 of their papers we have counts for
3 papers · 1 filter
Spectral Clustering Oracles in Sublinear Time
Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi +2
Given a graph that can be partitioned into disjoint expanders with outer conductance upper bounded by , can we efficiently construct a small space data structure th…
Faster Spectral Sparsification in Dynamic Streams
Michael Kapralov, Aida Mousavifar, Cameron Musco +2
Graph sketching has emerged as a powerful technique for processing massive graphs that change over time (i.e., are presented as a dynamic stream of edge updates) over the past few…
Testing Graph Clusterability: Algorithms and Lower Bounds
Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna +2
We consider the problem of testing graph cluster structure: given access to a graph , can we quickly determine whether the graph can be partitioned into a few clusters wi…