We study the problem of \emph{reconstructing a low-rank matrix}, where the input is an $n\times m$ matrix $M$ over a field $\mathbb{F}$ and the goal is to reconstruct a (near-optimal) matrix $M'$ that is low-rank and close to $M$ under some distance function $\Delta$.
Furthermore, the reconstruction must be local, ... 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 >>>

In the {\sc $k$-center} problem, the input is a bound $k$
and $n$ points with the distance between every two of them,
such that the distances obey the triangle inequality.
The goal is to choose a set of $k$ points to serve as centers,
so that the maximum distance ... more >>>