TY - GEN
T1 - A candidate for a strong separation of information and communication
AU - Braverman, Mark
AU - Ganor, Anat
AU - Kol, Gillat
AU - Raz, Ran
N1 - Funding Information:
Research supported in part by NSF Awards DMS-1128155, CCF- 1525342, and CCF-1149888, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry. † Research supported by the Israel Science Foundation (grant number 552/16) and the I-CORE Program of the planning and budgeting committee and The Israel Science Foundation (grant number 4/11). ‡ Research supported by the Simons Collaboration on Algorithms and Geometry and by the National Science Foundation grants No. CCF-1714779 and CCF-1412958.
Publisher Copyright:
© Mark Braverman Anat Ganor Gillat Kol and Ran Raz.
PY - 2018/1/1
Y1 - 2018/1/1
N2 - 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).
AB - 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).
KW - Amortized communication complexity
KW - Communication complexity
KW - Communication compression
KW - Direct sum
KW - Information complexity
UR - http://www.scopus.com/inward/record.url?scp=85041685543&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85041685543&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2018.11
DO - 10.4230/LIPIcs.ITCS.2018.11
M3 - Conference contribution
AN - SCOPUS:85041685543
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 9th Innovations in Theoretical Computer Science, ITCS 2018
A2 - Karlin, Anna R.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 9th Innovations in Theoretical Computer Science, ITCS 2018
Y2 - 11 January 2018 through 14 January 2018
ER -