@inproceedings{8292285b0a0f4cc89492a413a3c14a37,
title = "A candidate for a strong separation of information and communication",
abstract = "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).",
keywords = "Amortized communication complexity, Communication complexity, Communication compression, Direct sum, Information complexity",
author = "Mark Braverman and Anat Ganor and Gillat Kol and Ran Raz",
note = "Publisher Copyright: {\textcopyright} Mark Braverman Anat Ganor Gillat Kol and Ran Raz.; 9th Innovations in Theoretical Computer Science, ITCS 2018 ; Conference date: 11-01-2018 Through 14-01-2018",
year = "2018",
month = jan,
day = "1",
doi = "10.4230/LIPIcs.ITCS.2018.11",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Karlin, {Anna R.}",
booktitle = "9th Innovations in Theoretical Computer Science, ITCS 2018",
address = "Germany",
}