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
∙
04/14/2023
Robust Algorithms on Adaptive Inputs from Bounded Adversaries
We study dynamic algorithms robust to adaptive input generated from sour...
research
∙
03/02/2023
Improved Space Bounds for Learning with Experts
We give improved tradeoffs between space and regret for the online learn...
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/18/2022
Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
We study fundamental problems in linear algebra, such as finding a maxim...
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
∙
09/21/2022
Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
Semidefinite programming (SDP) is a unifying framework that generalizes ...
research
∙
06/29/2022
Hardness and Algorithms for Robust and Sparse Optimization
We explore algorithms and limitations for sparse optimization problems s...
research
∙
04/26/2022
Faster Fundamental Graph Algorithms via Learned Predictions
We consider the question of speeding up classic graph algorithms with ma...
research
∙
04/21/2022
Motif Cut Sparsifiers
A motif is a frequently occurring subgraph of a given directed or undire...
research
∙
04/19/2022
The White-Box Adversarial Data Stream Model
We study streaming algorithms in the white-box adversarial model, where ...
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/27/2021
Learning-Augmented k-means Clustering
k-means clustering is a well-studied problem due to its wide applicabili...
research
∙
10/18/2021
Dimensionality Reduction for Wasserstein Barycenter
The Wasserstein barycenter is a geometric construct which captures the n...
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/28/2021
Adversarial Robustness of Streaming Algorithms through Importance Sampling
In this paper, we introduce adversarially robust streaming algorithms fo...
research
∙
06/15/2021
Learning-based Support Estimation in Sublinear Time
We consider the problem of estimating the number of distinct elements in...
research
∙
12/08/2020
A Concentration Inequality for the Facility Location Problem
We give a concentration inequality for a stochastic version of the facil...
research
∙
09/04/2020
Smoothed analysis of the condition number under low-rank perturbations
Let M be an arbitrary n by n matrix of rank n-k. We study the condition ...
research
∙
12/02/2019
Using Dimensionality Reduction to Optimize t-SNE
t-SNE is a popular tool for embedding multi-dimensional datasets into tw...
research
∙
11/19/2019
Property Testing of LP-Type Problems
Given query access to a set of constraints S, we wish to quickly check i...
research
∙
11/17/2019
Testing Properties of Multiple Distributions with Few Samples
We propose a new setting for testing properties of distributions while r...
research
∙
12/30/2018