11 citations · 22 across the 11 of their papers we have counts for
4 papers · 1 filter
Toeplitz Low-Rank Approximation with Sublinear Query Complexity
Michael Kapralov, Hannah Lawrence, Mikhail Makarov +2
We present a sublinear query algorithm for outputting a near-optimal low-rank approximation to any positive semidefinite Toeplitz matrix . In particu…
On Constructing Spanners from Random Gaussian Projections
Sepehr Assadi, Michael Kapralov, Huacheng Yu
Graph sketching is a powerful paradigm for analyzing graph structure via linear measurements introduced by Ahn, Guha, and McGregor (SODA'12) that has since found numerous applicati…
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…
Motif Cut Sparsifiers
Michael Kapralov, Mikhail Makarov, Sandeep Silwal +2
A motif is a frequently occurring subgraph of a given directed or undirected graph . Motifs capture higher order organizational structure of beyond edge relationships, and,…