Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Howard Karloff:

TR05-064 | 26th June 2005
Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani

On earthmover distance, metric labeling, and 0-extension

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

TR01-080 | 14th November 2001
Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan

Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval

Revisions: 3

We prove that if a linear error correcting code
$\C:\{0,1\}^n\to\{0,1\}^m$ is such that a bit of the message can
be probabilistically reconstructed by looking at two entries of a
corrupted codeword, then $m = 2^{\Omega(n)}$. We also present
several extensions of this result.

We show a reduction from the ... more >>>

ISSN 1433-8092 | Imprint