Michael Kapralov

research

∙ 11/21/2022

Expander Decomposition in Dynamic Streams

In this paper we initiate the study of expander decompositions of a grap...

0 Arnold Filtser, et al. ∙

research

∙ 11/21/2022

Toeplitz Low-Rank Approximation with Sublinear Query Complexity

We present a sublinear query algorithm for outputting a near-optimal low...

0 Michael Kapralov, et al. ∙

research

∙ 09/29/2022

On Constructing Spanners from Random Gaussian Projections

Graph sketching is a powerful paradigm for analyzing graph structure via...

0 Sepehr Assadi, et al. ∙

research

∙ 04/21/2022

Motif Cut Sparsifiers

A motif is a frequently occurring subgraph of a given directed or undire...

0 Michael Kapralov, et al. ∙

research

∙ 12/14/2021

Simulating Random Walks in Random Streams

The random order graph streaming model has received significant attentio...

0 John Kallaugher, et al. ∙

research

∙ 12/01/2021

Efficient and Local Parallel Random Walks

Random walks are a fundamental primitive used in many machine learning a...

0 Michael Kapralov, et al. ∙

research

∙ 10/19/2021

Factorial Lower Bounds for (Almost) Random Order Streams

In this paper we introduce and study the StreamingCycles problem, a rand...

0 Ashish Chiplunkar, et al. ∙

research

∙ 07/15/2021

Sparse Fourier Transform by traversing Cooley-Tukey FFT computation graphs

Computing the dominant Fourier coefficients of a vector is a common task...

0 Karl Bringmann, et al. ∙

research

∙ 07/06/2021

Noisy Boolean Hidden Matching with Applications

The Boolean Hidden Matching (BHM) problem, introduced in a seminal paper...

0 Michael Kapralov, et al. ∙

research

∙ 06/04/2021

Spectral Hypergraph Sparsifiers of Nearly Linear Size

Graph sparsification has been studied extensively over the past two deca...

0 Michael Kapralov, et al. ∙

research

∙ 03/22/2021

Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model

The bipartite matching problem in the online and streaming settings has ...

0 Michael Kapralov, et al. ∙

research

∙ 01/14/2021

Spectral Clustering Oracles in Sublinear Time

Given a graph G that can be partitioned into k disjoint expanders with o...

0 Grzegorz Głuch, et al. ∙

research

∙ 11/13/2020

Kernel Density Estimation through Density Constrained Near Neighbor Search

In this paper we revisit the kernel density estimation problem: given a ...

0 Moses Charikar, et al. ∙

research

∙ 11/12/2020

Towards Tight Bounds for Spectral Sparsification of Hypergraphs

Cut and spectral sparsification of graphs have numerous applications, in...

0 Michael Kapralov, et al. ∙

research

∙ 11/12/2020

Communication Efficient Coresets for Maximum Matching

In this paper we revisit the problem of constructing randomized composab...

0 Michael Kapralov, et al. ∙

research

∙ 07/28/2020

Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model

Graph sketching is a powerful technique introduced by the seminal work o...

0 Arnold Filtser, et al. ∙

research

∙ 03/21/2020

Scaling up Kernel Ridge Regression via Locality Sensitive Hashing

Random binning features, introduced in the seminal paper of Rahimi and R...

0 Michael Kapralov, et al. ∙

research

∙ 12/29/2019

Practice of Streaming and Dynamic Graphs: Concepts, Models, Systems, and Parallelism

Graph processing has become an important part of various areas of comput...

0 Maciej Besta, et al. ∙

research

∙ 09/03/2019

Oblivious Sketching of High-Degree Polynomial Kernels

Kernel methods are fundamental tools in machine learning that allow dete...

0 Michael Kapralov, et al. ∙

research

∙ 07/12/2019

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Given a source of iid samples of edges of an input graph G with n vertic...

0 Michael Kapralov, et al. ∙

research

∙ 04/17/2019

Online Matching with General Arrivals

The online matching problem was introduced by Karp, Vazirani and Vaziran...

0 Buddhima Gamlath, et al. ∙

research

∙ 03/28/2019

Faster Spectral Sparsification in Dynamic Streams

Graph sketching has emerged as a powerful technique for processing massi...

0 Michael Kapralov, et al. ∙

research

∙ 03/28/2019

Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space

In this paper we consider the problem of computing spectral approximatio...

0 Michael Kapralov, et al. ∙

research

∙ 02/27/2019

Dimension-independent Sparse Fourier Transform

The Discrete Fourier Transform (DFT) is a fundamental computational prim...

0 Michael Kapralov, et al. ∙

research

∙ 12/20/2018

A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms

Reconstructing continuous signals from a small number of discrete sample...

0 Haim Avron, et al. ∙

research

∙ 11/27/2018

An Optimal Space Lower Bound for Approximating MAX-CUT

We consider the problem of estimating the value of MAX-CUT in a graph in...

0 Michael Kapralov, et al. ∙

research

∙ 11/19/2018

A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling

In the subgraph counting problem, we are given a input graph G(V, E) and...

0 Sepehr Assadi, et al. ∙

research

∙ 08/15/2018

The Sketching Complexity of Graph and Hypergraph Counting

Subgraph counting is a fundamental primitive in graph processing, with a...

0 John Kallaugher, et al. ∙

research

∙ 08/14/2018

Testing Graph Clusterability: Algorithms and Lower Bounds

We consider the problem of testing graph cluster structure: given access...

0 Ashish Chiplunkar, et al. ∙

research

∙ 04/26/2018

Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees

Random Fourier features is one of the most popular techniques for scalin...

0 Haim Avron, et al. ∙

Michael Kapralov

Featured Co-authors