The Earth Mover Distance (EMD) between two equal-size sets of points in R^d is defined to be the minimum cost of a bipartite matching between the two pointsets. It is a natural metric for comparing sets of features, and as such, it has received significant interest in computer vision. Motivated ... more >>>

We give an explicit construction of a constant-distortion embedding of an n-dimensional L_2 space into an n^{1+o(1)}-dimensional L_1 space. more >>>

A private approximation of a function f is defined to be another function F that approximates f in the usual sense, but does not reveal any information about the input x other than what can be deduced from f(x). We give the first two-party private approximation of the Euclidean distance ... more >>>

Spielman showed that one can construct error-correcting codes capable of correcting a constant fraction $\delta << 1/2$ of errors, and that are encodable/decodable in linear time. Guruswami and Sudan showed that it is possible to correct more than $50\%$ of errors (and thus exceed the ``half of the minimum distance ... more >>>