All reports by Author Robert Krauthgamer :

__
TR15-128
| 10th August 2015
__

Roee David, Elazar Goldenberg, Robert Krauthgamer#### Local Reconstruction of Low-Rank Matrices and Subspaces

Revisions: 2

__
TR07-048
| 3rd April 2007
__

Alexandr Andoni, Piotr Indyk, Robert Krauthgamer#### Earth Mover Distance over High-Dimensional Spaces

__
TR03-035
| 21st May 2003
__

Eran Halperin, Guy Kortsarz, Robert Krauthgamer#### Tight lower bounds for the asymmetric k-center problem

Roee David, Elazar Goldenberg, Robert Krauthgamer

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

Alexandr Andoni, Piotr Indyk, Robert Krauthgamer

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

Eran Halperin, Guy Kortsarz, Robert Krauthgamer

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