Given two point sets A and B in ℝ d of size n each, for some constant dimension d≥ 1, and a
parameter ε> 0, we present a deterministic algorithm that computes, in n·(ε− 1 log n) O (d) …

Energy distance is a statistical distance between the distributions of random vectors, which
characterizes equality of distributions. The name energy derives from Newton's gravitational …

We consider the problem of political redistricting: given the locations of people in a
geographical area (eg a US state), the goal is to decompose the area into subareas, called …

In the geometric transportation problem, we are given a collection of points $ P $ in $ d $-
dimensional Euclidean space, and each point is given a supply of $\mu (p) $ units of mass …

We give new data-dependent locality sensitive hashing schemes (LSH) for the Earth Mover's
Distance (EMD), and as a result, improve the best approximation for nearest neighbor …

For point sets A, B⊂ R d, 0X2223 A 0X2223= 0X2223 B 0X2223= n, and for a parameter ε>
0, we present a Monte Carlo algorithm that computes, in O (n poly (log n, 1/ε)) time, an ε …

We consider the problem of computing the 1-Wasserstein distance W (µ, ν) between two d-
dimensional discrete distributions µ and ν whose support lie within the unit hypercube …

The geometric transportation problem takes as input a set of points $ P $ in $ d $-
dimensional Euclidean space and a supply function $\mu: P\to\mathbb {R} $. The goal is to …

The FOCS'19 paper of Le and Solomon, culminating a long line of research on Euclidean
spanners, proves that the lightness (normalized weight) of the greedy $(1+\epsilon) …

Optimal Transport (OT, also known as the Wasserstein distance) is a popular metric for
comparing probability distributions and has been successfully used in many machine …