We construct a small set of explicit linear transformations mapping $R^n$ to $R^{O(\log n)}$, such that the $L_2$ norm of any vector in $R^n$ is distorted by at most $1\pm o(1)$ in at least a fraction of $1 - o(1)$ of the transformations in the set. Albeit the tradeoff between ... more >>>

We study the classification problem {\sc Metric Labeling} and its special case {\sc 0-Extension} in the context of earthmover metrics. Researchers recently proposed using earthmover metrics to get a polynomial time-solvable relaxation of {\sc Metric Labeling}; until now, however, no one knew if the integrality ratio was constant or not, ... more >>>

We give polynomial time approximation schemes for the problem of partitioning an input set of n points into a fixed number k of clusters so as to minimize the sum over all clusters of the total pairwise distances in a cluster. Our algorithms work for arbitrary metric spaces as well ... more >>>