11 citations · 22 across the 11 of their papers we have counts for
17 papers
Constant-Factor Local Approximation for Bipartite Densest Subgraph
Michael Kapralov, Jakub Łącki, Silvio Lattanzi +1
Given a vertex in a large bipartite graph , can one quickly find a small densely connected region near ? This is the algorithmic core of many fraud detection, community d…
Sublinear Time Low-Rank Approximation of Hankel Matrices
Michael Kapralov, Cameron Musco, Kshiteej Sheth
Hankel matrices are an important class of highly-structured matrices, arising across computational mathematics, engineering, and theoretical computer science. It is well-known that…
Streaming Attention Approximation via Discrepancy Theory
Ekaterina Kochetkova, Kshiteej Sheth, Insu Han +2
Large language models (LLMs) have achieved impressive success, but their high memory requirements present challenges for long-context token generation. In this paper we study the s…
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…
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,…
Factorial Lower Bounds for (Almost) Random Order Streams
Ashish Chiplunkar, John Kallaugher, Michael Kapralov +1
In this paper we introduce and study the \textsc{StreamingCycles} problem, a random order streaming version of the Boolean Hidden Hypermatching problem that has been instrumental i…
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…
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…
Practice of Streaming Processing of Dynamic Graphs: Concepts, Models, and Systems
Maciej Besta, Marc Fischer, Vasiliki Kalavri +2
Graph processing has become an important part of various areas of computing, including machine learning, medical applications, social network analysis, computational sciences, and…
Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams
Michael Kapralov, Jelani Nelson, Jakub Pachocki +3
In the communication problem (universal relation) [KRW95], Alice and Bob respectively receive with the promise that . The last player to…
An Adaptive Sublinear-Time Block Sparse Fourier Transform
Volkan Cevher, Michael Kapralov, Jonathan Scarlett +1
The problem of approximately computing the dominant Fourier coefficients of a vector quickly, and using few samples in time domain, is known as the Sparse Fourier Transform…
Sample-Optimal Fourier Sampling in Any Constant Dimension -- Part I
Piotr Indyk, Michael Kapralov
We give an algorithm for sparse recovery from Fourier measurements using samples, matching the lower bound of \cite{DIPW} for non-adaptive algorithms u…
Prediction strategies without loss
Michael Kapralov, Rina Panigrahy
Consider a sequence of bits where we are trying to predict the next bit from the previous bits. Assume we are allowed to say 'predict 0' or 'predict 1', and our payoff is +1 if the…
Perfect Matchings in O(n \log n) Time in Regular Bipartite Graphs
Ashish Goel, Michael Kapralov, Sanjeev Khanna
In this paper we consider the well-studied problem of finding a perfect matching in a d-regular bipartite graph on 2n nodes with m=nd edges. The best-known algorithm for general bi…