research
∙
11/21/2022
Expander Decomposition in Dynamic Streams
In this paper we initiate the study of expander decompositions of a grap...
share
research
∙
11/21/2022
Toeplitz Low-Rank Approximation with Sublinear Query Complexity
We present a sublinear query algorithm for outputting a near-optimal low...
research
∙
09/29/2022
On Constructing Spanners from Random Gaussian Projections
Graph sketching is a powerful paradigm for analyzing graph structure via...
research
∙
04/21/2022
Motif Cut Sparsifiers
A motif is a frequently occurring subgraph of a given directed or undire...
research
∙
12/14/2021
Simulating Random Walks in Random Streams
The random order graph streaming model has received significant attentio...
research
∙
12/01/2021
Efficient and Local Parallel Random Walks
Random walks are a fundamental primitive used in many machine learning a...
research
∙
10/19/2021
Factorial Lower Bounds for (Almost) Random Order Streams
In this paper we introduce and study the StreamingCycles problem, a rand...
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...
research
∙
07/06/2021
Noisy Boolean Hidden Matching with Applications
The Boolean Hidden Matching (BHM) problem, introduced in a seminal paper...
research
∙
06/04/2021
Spectral Hypergraph Sparsifiers of Nearly Linear Size
Graph sparsification has been studied extensively over the past two deca...
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 ...
research
∙
01/14/2021
Spectral Clustering Oracles in Sublinear Time
Given a graph G that can be partitioned into k disjoint expanders with o...
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 ...
research
∙
11/12/2020
Towards Tight Bounds for Spectral Sparsification of Hypergraphs
Cut and spectral sparsification of graphs have numerous applications, in...
research
∙
11/12/2020
Communication Efficient Coresets for Maximum Matching
In this paper we revisit the problem of constructing randomized composab...
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...
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...
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...
research
∙
09/03/2019
Oblivious Sketching of High-Degree Polynomial Kernels
Kernel methods are fundamental tools in machine learning that allow dete...
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...
research
∙
04/17/2019
Online Matching with General Arrivals
The online matching problem was introduced by Karp, Vazirani and Vaziran...
research
∙
03/28/2019
Faster Spectral Sparsification in Dynamic Streams
Graph sketching has emerged as a powerful technique for processing massi...
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...
research
∙
02/27/2019
Dimension-independent Sparse Fourier Transform
The Discrete Fourier Transform (DFT) is a fundamental computational prim...
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...
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...
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...
research
∙
08/15/2018
The Sketching Complexity of Graph and Hypergraph Counting
Subgraph counting is a fundamental primitive in graph processing, with a...
research
∙
08/14/2018
Testing Graph Clusterability: Algorithms and Lower Bounds
We consider the problem of testing graph cluster structure: given access...
research
∙
04/26/2018