A discrepancy lower bound for information complexity

This paper provides the first general technique for proving information lower bounds on two-party unbounded-rounds communication problems. We show that the discrepancy lower bound, which applies to randomized communication complexity, also applies to information complexity. More precisely, if the discrepancy of a two-party function $f$ with respect to a distribution $\mu$ is $Dis{c}_{\mu }f$, then any two party randomized protocol computing $f$ must reveal at least $\mathrm{\Omega }(\log (1\mathrm{/}Dis{c}_{\mu }f))$ bits of information to the participants. As a corollary, we obtain that any two-party protocol for computing a random function on $\{0,1{\}}^n\times \{0,1{\}}^n$ must reveal $\mathrm{\Omega }(n)$ bits of information to the participants. In addition, we prove that the discrepancy of the Greater-Than function is $\mathrm{\Omega }(1\mathrm{/}\sqrt{n})$, which provides an alternative proof to the recent proof of Viola \cite{Viola11} of the $\mathrm{\Omega }(\log n)$ lower bound on the communication complexity of this well-studied function and, combined with our main result, proves the tight $\mathrm{\Omega }(\log n)$ lower bound on its information complexity. The proof of our main result develops a new simulation procedure that may be of an independent interest. In a very recent breakthrough work of Kerenidis et al. \cite{kerenidis2012lower}, this simulation procedure was the main building block for proving that almost all known lower bound techniques for communication complexity (and not just discrepancy) apply to information complexity.