TY - GEN

T1 - Exponential separation of information and communication for boolean functions

AU - Ganor, Anat

AU - Kol, Gillat

AU - Raz, Ran

PY - 2015/6/14

Y1 - 2015/6/14

N2 - We show an exponential gap between communication complexity and information complexity for boolean functions, by giving an explicit example of a partial function with information complexity ≤ O(k), and distributional communication complexity ≥ 2k. This shows that a communication protocol for a partial boolean function cannot always be compressed to its internal information. By a result of Braverman [3], our gap is the largest possible. By a result of Braverman and Rao [4], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity of boolean functions cannot hold, answering a long standing open problem. Our techniques build on [13], that proved a similar result for relations with very long outputs (double exponentially long in k). In addition to the stronger result, the current work gives a simpler proof, benefiting from the short output length of boolean functions. 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.

AB - We show an exponential gap between communication complexity and information complexity for boolean functions, by giving an explicit example of a partial function with information complexity ≤ O(k), and distributional communication complexity ≥ 2k. This shows that a communication protocol for a partial boolean function cannot always be compressed to its internal information. By a result of Braverman [3], our gap is the largest possible. By a result of Braverman and Rao [4], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity of boolean functions cannot hold, answering a long standing open problem. Our techniques build on [13], that proved a similar result for relations with very long outputs (double exponentially long in k). In addition to the stronger result, the current work gives a simpler proof, benefiting from the short output length of boolean functions. 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.

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=84958774397&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958774397&partnerID=8YFLogxK

U2 - 10.1145/2746539.2746572

DO - 10.1145/2746539.2746572

M3 - Conference contribution

AN - SCOPUS:84958774397

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 557

EP - 566

BT - STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 47th Annual ACM Symposium on Theory of Computing, STOC 2015

Y2 - 14 June 2015 through 17 June 2015

ER -