research
∙
07/14/2023
Fast Algorithms for a New Relaxation of Optimal Transport
We introduce a new class of objectives for optimal transport computation...
share
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
∙
12/13/2022
Streaming Euclidean MST to a Constant Factor
We study streaming algorithms for the fundamental geometric problem of c...
research
∙
05/19/2022
Estimation of Entropy in Constant Space with Improved Sample Complexity
Recent work of Acharya et al. (NeurIPS 2019) showed how to estimate the ...
research
∙
05/01/2022
The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction
We study the effect of Johnson-Lindenstrauss transforms in various Eucli...
research
∙
04/26/2022
Polylogarithmic Sketches for Clustering
Given n points in ℓ_p^d, we consider the problem of partitioning points ...
research
∙
11/05/2021
New Streaming Algorithms for High Dimensional EMD and MST
We study streaming algorithms for two fundamental geometric problems: co...
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
∙
11/17/2019
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning
We give a nearly-optimal algorithm for testing uniformity of distributio...
research
∙
11/16/2019
Approximating the Distance to Monotonicity of Boolean Functions
We design a nonadaptive algorithm that, given a Boolean function f{0,1}^...
research
∙
11/04/2019
Optimal Adaptive Detection of Monotone Patterns
We investigate adaptive sublinear algorithms for detecting monotone patt...
research
∙
10/03/2019
Finding monotone patterns in sublinear time
We study the problem of finding monotone subsequences in an array from t...
research
∙
07/09/2019
Nearly optimal edge estimation with independent set queries
We study the problem of estimating the number of edges of an unknown, un...
research
∙
04/10/2019
Testing Unateness Nearly Optimally
We present an Õ(n^2/3/ϵ^2)-query algorithm that tests whether an unknown...
research
∙
02/07/2019
On Mean Estimation for General Norms with Statistical Queries
We study the problem of mean estimation for high-dimensional distributio...
research
∙
05/03/2018
Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs
We introduce a new model for testing graph properties which we call the ...
research
∙
08/19/2017