Information lower bounds via self-reducibility

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 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 [15], and answering an open problem from [10]. In our second result we prove that the information cost of IP n 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 [9]. 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 [13,2,3] 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)
Title of host publicationComputer Science - Theory and Applications - 8th International Computer Science Symposium in Russia, CSR 2013
Pages183-194
Number of pages12
DOIs
StatePublished - Nov 29 2013
Event8th International Computer Science Symposium in Russia, CSR 2013 - Ekaterinburg, Russian Federation
Duration: Jun 25 2013Jun 29 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7913 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other8th International Computer Science Symposium in Russia, CSR 2013
CountryRussian Federation
CityEkaterinburg
Period6/25/136/29/13

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Information lower bounds via self-reducibility'. Together they form a unique fingerprint.

Cite this