文章基本信息

标题：Internal Compression of Protocols to Entropy
本地全文：下载
作者：Balthazar Bauer ; Shay Moran ; Amir Yehudayoff 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：40
页码：481-496
DOI：10.4230/LIPIcs.APPROX-RANDOM.2015.481
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Communication complexity; Information complexity; Compression; Simulation; Entropy