2026-07-22T14:10:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5067 2024-03-06T10:35:46Z ddc:004 open_access

How to Compress Asymmetric Communication Natarajan Ramamoorthy, Sivaramakrishnan Rao, Anup Communication Complexity Interactive Compression Information Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao 2015 Is Part Of LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2015.102 urn:nbn:de:0030-drops-50679 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.102 eng https://creativecommons.org/licenses/by/3.0/legalcode