research
∙
08/01/2023
Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree
We study the classic Euclidean Minimum Spanning Tree (MST) problem in th...
share
research
∙
07/25/2023
Fully Dynamic Consistent k-Center Clustering
We study the consistent k-center clustering problem. In this problem, th...
research
∙
07/06/2023
A Near-Linear Time Algorithm for the Chamfer Distance
For any two point sets A,B ⊂ℝ^d of size up to n, the Chamfer distance fr...
research
∙
03/21/2023
Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries
In fully dynamic clustering problems, a clustering of a given data set i...
research
∙
12/13/2022
Streaming Euclidean MST to a Constant Factor
We study streaming algorithms for the fundamental geometric problem of c...
research
∙
12/10/2022
Adore: Differentially Oblivious Relational Database Operators
There has been a recent effort in applying differential privacy on memor...
research
∙
12/05/2022
Stars: Tera-Scale Graph Building for Clustering and Graph Learning
A fundamental procedure in the analysis of massive datasets is the const...
research
∙
12/13/2021
Optimal Fully Dynamic k-Centers Clustering
We present the first algorithm for fully dynamic k-centers clustering in...
research
∙
11/05/2021
New Streaming Algorithms for High Dimensional EMD and MST
We study streaming algorithms for two fundamental geometric problems: co...
research
∙
08/26/2021
Truly Perfect Samplers for Data Streams and Sliding Windows
In the G-sampling problem, the goal is to output an index i of a vector ...
research
∙
07/12/2021
In-Database Regression in Input Sparsity Time
Sketching is a powerful dimensionality reduction technique for accelerat...
research
∙
05/04/2021
An Optimal Algorithm for Triangle Counting
We present a new algorithm for approximating the number of triangles in ...
research
∙
05/20/2020
An FPRAS and Polynomial-Time Uniform Sampler for Tree Automata
In this work, we introduce the first fully polynomial time randomized ap...
research
∙
05/13/2020
Testing Positive Semi-Definiteness via Random Submatrices
We study the problem of testing whether a matrix A ∈R^n × n with bounded...
research
∙
04/26/2020
Learning and Testing Junta Distributions with Subcube Conditioning
We study the problems of learning and testing junta distributions on {-1...
research
∙
03/31/2020
A Framework for Adversarially Robust Streaming Algorithms
We investigate the adversarial robustness of streaming algorithms. In th...
research
∙
02/19/2020
Span Recovery for Deep Neural Networks with Applications to Input Obfuscation
The tremendous success of deep neural networks has motivated the need to...
research
∙
09/29/2019
Optimal Sketching for Kronecker Product Regression and Low Rank Approximation
We study the Kronecker product regression problem, in which the design m...
research
∙
07/12/2019
Towards Optimal Moment Estimation in Streaming and Distributed Models
One of the oldest problems in the data stream model is to approximate th...
research
∙
06/21/2019
Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation
In this work, we study two simple yet general complexity classes, based ...
research
∙
04/08/2019
Weighted Reservoir Sampling from Distributed Streams
We consider message-efficient continuous random sampling from a distribu...
research
∙
11/05/2018
Learning Two Layer Rectified Neural Networks in Polynomial Time
Consider the following fundamental learning problem: given input example...
research
∙
08/16/2018
Perfect L_p Sampling in a Data Stream
In this paper, we resolve the one-pass space complexity of L_p sampling ...
research
∙
03/23/2018