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.CCC.2015.102
URN: urn:nbn:de:0030-drops-50679
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5067/
Go to the corresponding LIPIcs Volume Portal

Natarajan Ramamoorthy, Sivaramakrishnan ; Rao, Anup

How to Compress Asymmetric Communication

pdf-format:
19.pdf (0.5 MB)

Abstract

We study the relationship between communication and information in 2-party 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 =	{102--123},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{David Zuckerman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5067},
  URN =		{urn:nbn:de:0030-drops-50679},
  doi =		{10.4230/LIPIcs.CCC.2015.102},
  annote =	{Keywords: Communication Complexity, Interactive Compression, Information Complexity}
}

Keywords: Communication Complexity, Interactive Compression, Information Complexity
Collection: 30th Conference on Computational Complexity (CCC 2015)
Issue Date: 2015
Date of publication: 06.06.2015

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