Natarajan Ramamoorthy, Sivaramakrishnan ;
Rao, Anup
How to Compress Asymmetric Communication
Abstract
We study the relationship between communication and information in 2party communication protocols when the information is asymmetric. If I^A denotes the number of bits of information revealed by the first party, I^B denotes the information revealed by the second party, and C is the number of bits of communication in the protocol, we show that i) one can simulate the protocol using order I^A + (C^3 * I^B)^(1/4) * log(C) + (C * I^B)^(1/2) * log(C) bits of communication, ii) one can simulate the protocol using order I^A * 2^(O(I^B)) bits of communication The first result gives the best known bound on the complexity of a simulation when I^A >> I^B,C^(3/4). The second gives the best known bound when I^B << log C. In addition we show that if a function is computed by a protocol with asymmetric information complexity, then the inputs must have a large, nearly monochromatic rectangle of the right dimensions, a fact that is useful for proving lower bounds on lopsided communication problems.
BibTeX  Entry
@InProceedings{natarajanramamoorthy_et_al:LIPIcs:2015:5067,
author = {Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao},
title = {{How to Compress Asymmetric Communication}},
booktitle = {30th Conference on Computational Complexity (CCC 2015)},
pages = {102123},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897811},
ISSN = {18688969},
year = {2015},
volume = {33},
editor = {David Zuckerman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5067},
URN = {urn:nbn:de:0030drops50679},
doi = {10.4230/LIPIcs.CCC.2015.102},
annote = {Keywords: Communication Complexity, Interactive Compression, Information Complexity}
}
2015
Keywords: 

Communication Complexity, Interactive Compression, Information Complexity 
Seminar: 

30th Conference on Computational Complexity (CCC 2015)

Issue date: 

2015 
Date of publication: 

2015 