4 citations · 4 across the 1 of their papers we have counts for
5 papers
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…
Beyond -Approximation for Submodular Maximization on Massive Data Streams
Ashkan Norouzi-Fard, Jakub Tarnawski, Slobodan Mitrović +3
Many tasks in machine learning and data mining, such as data diversification, non-parametric learning, kernel machines, clustering etc., require extracting a small but representati…
A Model for Information Networks: Efficiency, Stability and Dynamics
L. Elisa Celis, Aida S. Mousavifar
We introduce a simple network model that is inspired by social information networks such as twitter. Agents are nodes, connecting to another agent by building a directed edge has a…