1 citations · 2 across the 4 of their papers we have counts for
7 papers
On the Streaming Complexity of Expander Decomposition
Yu Chen, Michael Kapralov, Mikhail Makarov +1
In this paper we study the problem of finding -expander decompositions of a graph in the streaming model, in particular for dynamic streams of edge insertions and deletions…
On the adversarial robustness of Locality-Sensitive Hashing in Hamming space
Michael Kapralov, Mikhail Makarov, Christian Sohler
Locality-sensitive hashing~[Indyk,Motwani'98] is a classical data structure for approximate nearest neighbor search. It allows, after a close to linear time preprocessing of the in…
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…
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…
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,…
Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms
Karl Bringmann, Michael Kapralov, Mikhail Makarov +3
We consider the well-studied Sparse Fourier transform problem, where one aims to quickly recover an approximately Fourier -sparse vector from…
Logical complexity of induced subgraph isomorphism for certain graph families
E. D. Kudryavtsev, M. V. Makarov, A. S. Shlychkova +1
We prove that, for every , there exists an -vertex graph and a first order sentence having a quantifier depth at most defining the property of having an…