For every fixed constant \alpha > 0, we design an algorithm for computing the k-sparse Walsh-Hadamard transform of an N-dimensional vector x \in \mathbb{R}^N in time k^{1+\alpha} (\log N)^{O(1)}. Specifically, the algorithm is given query access to x and computes a k-sparse \tilde{x} \in \mathbb{R}^N satisfying $\|\tilde{x} - \hat{x}\|_1 \leq ... more >>>

A discrete distribution p, over [n], is a k-histogram if its probability distribution function can be
represented as a piece-wise constant function with k pieces. Such a function
is
represented by a list of k intervals and k corresponding values. We consider
the following problem: given a collection of samples ... more >>>

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.

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 ... more >>>