1 citations · 2 across the 4 of their papers we have counts for
Showing 2022Show all
3 papers · 1 filter
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
Expander Decomposition in Dynamic Streams
Arnold Filtser, Michael Kapralov, Mikhail Makarov
In this paper we initiate the study of expander decompositions of a graph in the streaming model of computation. The goal is to find a partitioning of vert…
cs.DS2022
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,…