Exponential Separation of Information and Communication for Boolean Functions
Anat Ganor, Gillat Kol, Ran Raz · Journal of the ACM · 2016
We show an exponential gap between communication complexity and information complexity by giving an explicit example of a partial boolean function with information complexity ≤ O ( 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.