research
∙
07/04/2023
Fast Private Kernel Density Estimation via Locality Sensitive Quantization
We study efficient mechanisms for differentially private kernel density ...
share
research
∙
04/15/2023
Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees
An ε-approximate quantile sketch over a stream of n inputs approximates ...
research
∙
11/06/2022
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks
Recent work shows that the expressive power of Graph Neural Networks (GN...
research
∙
10/24/2022
Budget-Constrained Bounds for Mini-Batch Estimation of Optimal Transport
Optimal Transport (OT) is a fundamental tool for comparing probability d...
research
∙
07/18/2022
Streaming Algorithms for Support-Aware Histograms
Histograms, i.e., piece-wise constant approximations, are a popular tool...
research
∙
06/16/2022
Generalization Bounds for Data-Driven Numerical Linear Algebra
Data-driven algorithms can adapt their internal structure or parameters ...
research
∙
06/09/2022
Unveiling Transformers with LEGO: a synthetic reasoning task
We propose a synthetic task, LEGO (Learning Equality and Group Operation...
research
∙
03/17/2022
Triangle and Four Cycle Counting with Predictions in Graph Streams
We propose data-driven one-pass streaming algorithms for estimating the ...
research
∙
10/07/2021
Optimal (Euclidean) Metric Compression
We study the problem of representing all distances between n points in ℝ...
research
∙
06/15/2021
Learning-based Support Estimation in Sublinear Time
We consider the problem of estimating the number of distinct elements in...
research
∙
02/16/2021
Faster Kernel Matrix Algebra via Density Estimation
We study fast algorithms for computing fundamental properties of a posit...
research
∙
10/09/2019
Scalable Nearest Neighbor Search for Optimal Transport
The Optimal Transport (a.k.a. Wasserstein) distance is an increasingly p...
research
∙
06/02/2019
Sample-Optimal Low-Rank Approximation of Distance Matrices
A distance matrix A ∈ R^n × m represents all pairwise distances, A_ij=d(...
research
∙
02/10/2019
Scalable Fair Clustering
We study the fair variant of the classic k-median problem introduced by ...
research
∙
01/24/2019
Learning Sublinear-Time Indexing for Nearest Neighbor Search
Most of the efficient sublinear-time indexing algorithms for the high-di...
research
∙
01/24/2019
Learning Space Partitions for Nearest Neighbor Search
Space partitions of R^d underlie a vast and important class of fast near...
research
∙
09/08/2018
Multitasking Capacity: Hardness Results and Improved Constructions
We consider the problem of determining the maximal α∈ (0,1] such that ev...
research
∙
06/30/2018
Approximate Nearest Neighbors in Limited Space
We consider the (1+ϵ)-approximate nearest neighbor search problem: given...
research
∙
11/05/2017