3 papers
cs.DS2022
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…
cs.DS2022
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…
cs.DS2020
Communication Efficient Coresets for Maximum Matching
Michael Kapralov, Gilbert Maystre, Jakab Tardos
In this paper we revisit the problem of constructing randomized composable coresets for bipartite matching. In this problem the input graph is randomly partitioned across playe…