Access Restriction

Author Ganor, Anat ♦ Kol, Gillat ♦ Raz, Ran
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Amortized communication complexity ♦ Communication complexity ♦ Communication compression ♦ Direct sum ♦ Information complexity
Abstract We show an exponential gap between communication complexity and information complexity by giving an explicit example of a partial boolean function with information complexity ≤ $\textit{O}(\textit{k}),$ and distributional communication complexity ≥ $2^{k}.$ This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman [2015], our gap is the largest possible. By a result of Braverman and Rao [2014], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity cannot hold, answering a long-standing open problem. Another (conceptual) contribution of our work is the relative discrepancy method, a new rectangle-based method for proving communication complexity lower bounds for boolean functions, powerful enough to separate information complexity and communication complexity.
Description Author Affiliation: Weizmann Institute of Science, Rehovot, Israel (Ganor, Anat); Institute for Advanced Study (Kol, Gillat); Weizmann Institute of Science and the Institute for Advanced Study (Raz, Ran)
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-11-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 63
Issue Number 5
Page Count 31
Starting Page 1
Ending Page 31

Open content in new tab

   Open content in new tab
Source: ACM Digital Library