2026-07-20T11:57:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8332 2024-03-06T10:42:03Z ddc:004 open_access

A Candidate for a Strong Separation of Information and Communication Braverman, Mark Ganor, Anat Kol, Gillat Raz, Ran communication complexity amortized communication complexity communication compression direct sum information complexity The weak interactive compression conjecture asserts that any two-party communication protocol with communication complexity C and information complexity I can be compressed to a protocol with communication complexity poly(I)polylog(C). We describe a communication problem that is a candidate for refuting that conjecture. Specifically, while we show that the problem can be solved by a protocol with communication complexity C and information complexity I=polylog(C), the problem seems to be hard for protocols with communication complexity poly(I)polylog(C)=polylog(C). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mark Braverman and Anat Ganor and Gillat Kol and Ran Raz 2018 Is Part Of LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2018.11 urn:nbn:de:0030-drops-83322 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.11 eng https://creativecommons.org/licenses/by/3.0/legalcode