An interactive information odometer and applications

Mark Braverman, Omri Weinstein

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

14 Scopus citations

Abstract

We introduce a novel technique which enables two players to maintain an estimate of the internal information cost of their conversation in an online fashion without revealing much extra information. We use this construction to obtain new results about communication complexity and information-theoretic privacy. As a first corollary, we prove a strong direct product theorem for communication complexity in terms of information complexity: If I bits of information are required for solving a single copy of f under μ with probability 2/3, then any protocol attempting to solve n independent copies of f under μn using o(n · I) communication, will succeed with probability 2Ω(n). This is tight, as Braverman and Rao [BR11] previously showed that O(n · I) communication suffice to succeed with probability ~ (2/3)n. We then show how the information odometer can be used to achieve the best possible information-theoretic privacy between two untrusted parties: If the players' goal is to compute a function f(x,y), and f admits a protocol with information cost is I and communication cost C, then our odometer can be used to produce a "robust" protocol which: (i) Assuming both players are honest, computes f with high probability, and (ii) Even if one party is malicious, then for any k ∈ N, the probability that the honest player reveals more than O(k· (I + log C)) bits of information to the other player is at most 2-Ω(k). Finally, we outline an approach which uses the odometer as a proxy for breaking state of the art interactive compression results: We show that our odometer allows to reduce interactive compression to the regime where I = O(logC), thereby opening a potential avenue for improving the compression result of [BBCR10] and to new direct sum and product theorems in communication complexity.

Original languageEnglish (US)
Title of host publicationSTOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages341-350
Number of pages10
ISBN (Electronic)9781450335362
DOIs
StatePublished - Jun 14 2015
Event47th Annual ACM Symposium on Theory of Computing, STOC 2015 - Portland, United States
Duration: Jun 14 2015Jun 17 2015

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume14-17-June-2015
ISSN (Print)0737-8017

Other

Other47th Annual ACM Symposium on Theory of Computing, STOC 2015
CountryUnited States
CityPortland
Period6/14/156/17/15

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Direct product theorems
  • Information Complexity
  • Interactive compression
  • Secure Computation

Fingerprint Dive into the research topics of 'An interactive information odometer and applications'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., & Weinstein, O. (2015). An interactive information odometer and applications. In STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing (pp. 341-350). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 14-17-June-2015). Association for Computing Machinery. https://doi.org/10.1145/2746539.2746548