Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

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


TR05-063 | 24th June 2005
Bodo Manthey, RĂ¼diger Reischuk

Smoothed Analysis of the Height of Binary Search Trees

Revisions: 2

Binary search trees are one of the most fundamental data structures. While the
height of such a tree may be linear in the worst case, the average height with
respect to the uniform distribution is only logarithmic. The exact value is one
of the best studied problems in average case ... more >>>


TR05-062 | 17th June 2005
A. Pavan, N. V. Vinodchandran

2-Local Random Reductions to 3-Valued Functions

Yao (in a lecture at DIMACS Workshop on structural complexity and
cryptography) showed that if a language L is 2-locally-random
reducible to a Boolean functio, then L is in PSPACE/poly.
Fortnow and Szegedy quantitatively improved Yao's result to show that
such languages are in fact in NP/poly (Information Processing Letters, ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint