42 citations · 50 across the 6 of their papers we have counts for
7 papers
Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
Michael Kapralov, Akash Kumar, Silvio Lattanzi +2
Testing graph cluster structure has been a central object of study in property testing since the foundational work of Goldreich and Ron [STOC'96] on expansion testing, i.e. the pro…
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…
A Model for Social Network Formation: Efficiency, Stability and Dynamics
L. Elisa Celis, Aida Sadat Mousavifar
We introduce a simple network formation model for social networks. Agents are nodes, connecting to another agent by building a directed edge (or accepting a connection from another…