License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.481
URN: urn:nbn:de:0030-drops-53198
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5319/
Go to the corresponding LIPIcs Volume Portal

Bauer, Balthazar ; Moran, Shay ; Yehudayoff, Amir

Internal Compression of Protocols to Entropy

pdf-format:
29.pdf (0.5 MB)

Abstract

We study internal compression of communication protocols to their internal entropy, which is the entropy of the transcript from the players' perspective. We provide two internal compression schemes with error. One of a protocol of Feige et al. for finding the first difference between two strings. The second and main one is an internal compression with error epsilon > 0 of a protocol with internal entropy H^{int} and communication complexity C to a protocol with communication at most order (H^{int}/epsilon)^2 * log(log(C)).

This immediately implies a similar compression to the internal information of public-coin protocols, which provides an exponential improvement over previously known public-coin compressions in the dependence on C. It further shows that in a recent protocol of Ganor, Kol and Raz, it is impossible to move the private randomness to be public without an exponential cost. To the best of our knowledge, No such example was previously known.

BibTeX - Entry

@InProceedings{bauer_et_al:LIPIcs:2015:5319,
  author =	{Balthazar Bauer and Shay Moran and Amir Yehudayoff},
  title =	{{Internal Compression of Protocols to Entropy}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{481--496},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5319},
  URN =		{urn:nbn:de:0030-drops-53198},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.481},
  annote =	{Keywords: Communication complexity, Information complexity, Compression, Simulation, Entropy}
}

Keywords: Communication complexity, Information complexity, Compression, Simulation, Entropy
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Issue Date: 2015
Date of publication: 13.08.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI