Direct products in communication complexity

Mark Braverman, Omri Weinstein, Anup Rao, Amir Yehudayoff

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

30 Scopus citations

Abstract

We give exponentially small upper bounds on the success probability for computing the direct product of any function over any distribution using a communication protocol. Let suc(μ, f,C) denote the maximum success probability of a 2-party communication protocol for computing the boolean function f(x, y) with C bits of communication, when the inputs (x, y) are drawn from the distribution μ. Let μn be the product distribution on n inputs and fn denote the function that computes n copies of f on these inputs. We prove that if T log3/2T ⋘ (C - 1) √ n and suc(μ, f,C) < 2 3 , then suc(μn, fn, T) ≤ exp(-Ω(n)). When μ is a product distribution, we prove a nearly optimal result: As long as T log 2 T ⋘ Cn, we must have suc(μn, fn, T) ≤ exp(-Ω(n)).

Original languageEnglish (US)
Title of host publicationProceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Pages746-755
Number of pages10
DOIs
StatePublished - Dec 1 2013
Event2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 - Berkeley, CA, United States
Duration: Oct 27 2013Oct 29 2013

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
CountryUnited States
CityBerkeley, CA
Period10/27/1310/29/13

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Direct products in communication complexity'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., Weinstein, O., Rao, A., & Yehudayoff, A. (2013). Direct products in communication complexity. In Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 (pp. 746-755). [6686211] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2013.85