Information Lower Bounds via Self-Reducibility

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

We use self-reduction methods to prove strong information lower bounds on two of the most studied functions in the communication complexity literature: Gap Hamming Distance (GHD) and Inner Product (IP). In our first result we affirm the conjecture that the information cost of GHD is linear even under the uniform distribution, which strengthens the Ω(n) bound recently shown by Kerenidis et al. (2012), and answers an open problem from Chakrabarti et al. (2012). In our second result we prove that the information cost of IPn is arbitrarily close to the trivial upper bound n as the permitted error tends to zero, again strengthening the Ω(n) lower bound recently proved by Braverman and Weinstein (Electronic Colloquium on Computational Complexity (ECCC) 18, 164 2011). Our proofs demonstrate that self-reducibility makes the connection between information complexity and communication complexity lower bounds a two-way connection. Whereas numerous results in the past (Chakrabarti et al. 2001; Bar-Yossef et al. J. Comput. Syst. Sci. 68(4), 702–732 2004; Barak et al. 2010) used information complexity techniques to derive new communication complexity lower bounds, we explore a generic way in which communication complexity lower bounds imply information complexity lower bounds in a black-box manner.

Original languageEnglish (US)
Pages (from-to)377-396
Number of pages20
JournalTheory of Computing Systems
Volume59
Issue number2
DOIs
StatePublished - Aug 1 2016

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Keywords

  • Communication complexity
  • Gap-hamming distance
  • Information complexity
  • Inner product
  • Self-reducibility

Fingerprint Dive into the research topics of 'Information Lower Bounds via Self-Reducibility'. Together they form a unique fingerprint.

  • Cite this