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...
share
research
∙
06/20/2023
Data Structures for Density Estimation
We study statistical/computational tradeoffs for the following density e...
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
∙
12/01/2022
Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation
Kernel matrices, as well as weighted graphs represented by them, are ubi...
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/27/2022
Faster Linear Algebra for Distance Matrices
The distance matrix of a dataset X of n points with respect to a distanc...
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
∙
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
∙
11/19/2021
Embeddings and labeling schemes for A*
A* is a classic and popular method for graphs search and path finding. I...
research
∙
11/06/2021
Frequency Estimation with One-Sided Error
Frequency estimation is one of the most fundamental problems in streamin...
research
∙
10/21/2021
Online Bipartite Matching with Predicted Degrees
We propose a model for online graph problems where algorithms are given ...
research
∙
10/07/2021
Optimal (Euclidean) Metric Compression
We study the problem of representing all distances between n points in ℝ...
research
∙
07/05/2021
Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering
Random dimensionality reduction is a versatile tool for speeding up algo...
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
∙
06/09/2020
Online Page Migration with ML Advice
We consider online algorithms for the page migration problem that use pr...
research
∙
11/18/2019
Estimating Entropy of Distributions in Constant Space
We consider the task of estimating the entropy of k-ary distributions fr...
research
∙
10/30/2019
Learning-Based Low-Rank Approximations
We introduce a "learning-based" algorithm for the low-rank decomposition...
research
∙
10/09/2019
Scalable Nearest Neighbor Search for Optimal Transport
The Optimal Transport (a.k.a. Wasserstein) distance is an increasingly p...
research
∙
08/14/2019
(Learned) Frequency Estimation Algorithms under Zipfian Distribution
The frequencies of the elements in a data stream are an important statis...
research
∙
07/06/2019
Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm
"Composable core-sets" are an efficient framework for solving optimizati...
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
Set Cover in Sub-linear Time
We study the classic set cover problem from the perspective of sub-linea...
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
∙
07/31/2018
Composable Core-sets for Determinant Maximization Problems via Spectral Spanners
We study a spectral generalization of classical combinatorial graph span...
research
∙
06/30/2018
Approximate Nearest Neighbors in Limited Space
We consider the (1+ϵ)-approximate nearest neighbor search problem: given...
research
∙
06/26/2018
Approximate Nearest Neighbor Search in High Dimensions
The nearest neighbor problem is defined as follows: Given a set P of n p...
research
∙
11/05/2017
Practical Data-Dependent Metric Compression with Provable Guarantees
We introduce a new distance-preserving compact representation of multi-d...
research
∙
04/10/2017