Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > YUVAL DAGAN:
All reports by Author Yuval Dagan:

TR16-190 | 21st November 2016
Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li

Trading information complexity for error

We consider the standard two-party communication model. The central problem studied in this article is how much one can save in information complexity by allowing an error of $\epsilon$.
For arbitrary functions, we obtain lower bounds and upper bounds indicating a gain that is of order $\Omega(h(\epsilon))$ and $O(h(\sqrt{\epsilon}))$. ... more >>>




ISSN 1433-8092 | Imprint