82 citations · 187 across the 27 of their papers we have counts for
30 papers · 1 filter
Towards Tight Bounds for Streaming Attention
Justin Y. Chen, Ying Feng, Piotr Indyk +3
The attention mechanism is a cornerstone of modern transformer architectures. However, its expressive power comes at the cost of quadratic runtime and linear space usage. In partic…
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…
Streaming Algorithms for Connectivity Augmentation
Ce Jin, Michael Kapralov, Sepideh Mahabadi +1
We study the -connectivity augmentation problem (-CAP) in the single-pass streaming model. Given a -edge connected graph that is stored in memory, and a stre…
A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
Moses Charikar, Michael Kapralov, Erik Waingarten
In the kernel density estimation (KDE) problem one is given a kernel and a dataset of points in a Euclidean space, and must prepare a data structure that can quickly…
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…
Simulating Random Walks in Random Streams
John Kallaugher, Michael Kapralov, Eric Price
The random order graph streaming model has received significant attention recently, with problems such as matching size estimation, component counting, and the evaluation of bounde…
Noisy Boolean Hidden Matching with Applications
Michael Kapralov, Amulya Musipatla, Jakab Tardos +2
The Boolean Hidden Matching (BHM) problem, introduced in a seminal paper of Gavinsky et. al. [STOC'07], has played an important role in the streaming lower bounds for graph problem…
Spectral Hypergraph Sparsifiers of Nearly Linear Size
Michael Kapralov, Robert Krauthgamer, Jakab Tardos +1
Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph spars…
Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model
Michael Kapralov
The bipartite matching problem in the online and streaming settings has received a lot of attention recently. The classical vertex arrival setting, for which the celebrated Karp, V…
Kernel Density Estimation through Density Constrained Near Neighbor Search
Moses Charikar, Michael Kapralov, Navid Nouri +1
In this paper we revisit the kernel density estimation problem: given a kernel and a dataset of points in high dimensional Euclidean space, prepare a data structure t…
Towards Tight Bounds for Spectral Sparsification of Hypergraphs
Michael Kapralov, Robert Krauthgamer, Jakab Tardos +1
Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently bee…
Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model
Arnold Filtser, Michael Kapralov, Navid Nouri
Graph sketching is a powerful technique introduced by the seminal work of Ahn, Guha and McGregor'12 on connectivity in dynamic graph streams that has enjoyed considerable attention…
Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
Michael Kapralov, Slobodan Mitrović, Ashkan Norouzi-Fard +1
Given a source of iid samples of edges of an input graph with vertices and edges, how many samples does one need to compute a constant factor approximation to the maxim…
Online Matching with General Arrivals
Buddhima Gamlath, Michael Kapralov, Andreas Maggiori +2
The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertice…
Faster Spectral Sparsification in Dynamic Streams
Michael Kapralov, Aida Mousavifar, Cameron Musco +2
Graph sketching has emerged as a powerful technique for processing massive graphs that change over time (i.e., are presented as a dynamic stream of edge updates) over the past few…
Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space
Michael Kapralov, Navid Nouri, Aaron Sidford +1
In this paper we consider the problem of computing spectral approximations to graphs in the single pass dynamic streaming model. We provide a linear sketching based solution that g…
Dimension-independent Sparse Fourier Transform
Michael Kapralov, Ameya Velingker, Amir Zandieh
The Discrete Fourier Transform (DFT) is a fundamental computational primitive, and the fastest known algorithm for computing the DFT is the FFT (Fast Fourier Transform) algorithm.…
An Optimal Space Lower Bound for Approximating MAX-CUT
Michael Kapralov, Dmitry Krachun
We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. At one extreme, there is a trivial -approximation for this problem t…
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
Sepehr Assadi, Michael Kapralov, Sanjeev Khanna
In the subgraph counting problem, we are given a input graph and a target graph ; the goal is to estimate the number of occurrences of in . Our focus here is on…
Testing Graph Clusterability: Algorithms and Lower Bounds
Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna +2
We consider the problem of testing graph cluster structure: given access to a graph , can we quickly determine whether the graph can be partitioned into a few clusters wi…
The Sketching Complexity of Graph and Hypergraph Counting
John Kallaugher, Michael Kapralov, Eric Price
Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database pr…
Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average
Michael Kapralov
The problem of computing the Fourier Transform of a signal whose spectrum is dominated by a small number of frequencies quickly and using a small number of samples of the signa…
How to Fake Multiply by a Gaussian Matrix
Michael Kapralov, Vamsi K. Potluru, David P. Woodruff
Have you ever wanted to multiply an matrix , with , on the left by an matrix of i.i.d. Gaussian random variables, but could not aff…
Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time
Michael Kapralov
We consider the problem of computing a -sparse approximation to the Fourier transform of a length signal. Our main result is a randomized algorithm for computing such an app…