Skip to main content

A Discrepancy Lower Bound for Information Complexity

Author(s): Braverman, Mark; Weinstein, Omri

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1025j
Abstract: 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 μ is Disc μ f, then any two party randomized protocol computing f must reveal at least Ω(log(1/Disc μ 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 ×{0,1} n must reveal Ω(n) bits of information to the participants. In addition, we prove that the discrepancy of the Greater-Than function is Ω(1/𝑛√) , which provides an alternative proof to the recent proof of Viola [Vio11] of the Ω(logn) lower bound on the communication complexity of this well-studied function and, combined with our main result, proves the tight Ω(logn) 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. [KLL+12], this simulation procedure was a building block towards a proof that almost all known lower bound techniques for communication complexity (and not just discrepancy) apply to information complexity.
Publication Date: 2012
Citation: Braverman, Mark, and Omri Weinstein. "A Discrepancy Lower Bound for Information Complexity." Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (2012): 459-470. doi:10.1007/978-3-642-32512-0_39
DOI: 10.1007/978-3-642-32512-0_39
ISSN: 0302-9743
Pages: 459 - 470
Type of Material: Conference Article
Series/Report no.: Lecture Notes in Computer Science;
Journal/Proceeding Title: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques.
Version: Author's manuscript



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.