82 citations · 187 across the 27 of their papers we have counts for
5 papers · 1 filter
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.…