Cover Image

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Beretta, Lorenzo, Cohen-Addad, Vincent, Jayaram, Rajesh, Waingarten, Erik
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Data-Dependent LSH for the Earth Mover's Distance
by: Jayaram, Rajesh, et al.
Published: (2024)

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
by: Gao, Jie, et al.
Published: (2025)

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
by: Bakshi, Ainesh, et al.
Published: (2023)

New Statistical and Computational Results for Learning Junta Distributions
by: Beretta, Lorenzo
Published: (2025)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
by: Azarmehr, Amir, et al.
Published: (2025)

Instance-Optimal Uniformity Testing and Tracking
by: Blanc, Guy, et al.
Published: (2025)

Dynamic Correlation Clustering in Sublinear Update Time
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Retriever Portfolios: A Principled Approach to Adaptive RAG
by: Stouras, Miltiadis, et al.
Published: (2026)

A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2024)

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem
by: Cohen-Addad, Vincent, et al.
Published: (2025)

A Scalable Algorithm for Individually Fair K-means Clustering
by: Bateni, MohammadHossein, et al.
Published: (2024)

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
by: Chakrabarty, Deeparnab, et al.
Published: (2025)

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
by: Axiotis, Kyriakos, et al.
Published: (2024)

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
by: Cohen-Addad, Vincent, et al.
Published: (2022)

A Tight VC-Dimension Analysis of Clustering Coresets with Applications
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Streaming and Massively Parallel Algorithms for Euclidean Max-Cut
by: Menand, Nicolas, et al.
Published: (2025)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
by: Cohen-Addad, Vincent, et al.
Published: (2025)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Feature Selection and Junta Testing are Statistically Equivalent
by: Beretta, Lorenzo, et al.
Published: (2025)

Multi-View Stochastic Block Models
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Interpreting the Curse of Dimensionality from Distance Concentration and Manifold Effect
by: Peng, Dehua, et al.
Published: (2023)

An Improved Greedy Approximation for (Metric) $k$-Means
by: Charikar, Moses, et al.
Published: (2026)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
by: Khanna, Sanjeev, et al.
Published: (2025)

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
by: Charikar, Moses, et al.
Published: (2024)

Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
by: Pham, Ninh, et al.
Published: (2025)

Approximating the Total Variation Distance between Gaussians
by: Bhattacharyya, Arnab, et al.
Published: (2025)

Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
by: Alman, Josh, et al.
Published: (2024)

A Strong Linear Programming Relaxation for Weighted Tree Augmentation
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Distributed Algorithms for Euclidean Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Kd-tree Based Wasserstein Distance Approximation for High-Dimensional Data
by: Teshigawara, Kanata, et al.
Published: (2026)

Tight Bounds on the Number of Closest Pairs in Vertical Slabs
by: Biniaz, Ahmad, et al.
Published: (2025)

Correlation Clustering Beyond the Pivot Algorithm
by: Behnezhad, Soheil, et al.
Published: (2024)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
by: Bansal, Nikhil, et al.
Published: (2024)

Nearly Tight Bounds on Testing of Metric Properties
by: Bao, Yiqiao, et al.
Published: (2024)

On the Distance from Calibration in Sequential Prediction
by: Qiao, Mingda, et al.
Published: (2024)

Computational and Statistical Hardness of Calibration Distance
by: Qiao, Mingda
Published: (2026)

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation
by: Greenhut, Daniel, et al.
Published: (2025)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Fast Tensor Completion via Approximate Richardson Iteration
by: Ghadiri, Mehrdad, et al.
Published: (2025)