TY - GEN

T1 - Direct products in communication complexity

AU - Braverman, Mark

AU - Weinstein, Omri

AU - Rao, Anup

AU - Yehudayoff, Amir

PY - 2013/12/1

Y1 - 2013/12/1

N2 - 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)).

AB - 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)).

UR - http://www.scopus.com/inward/record.url?scp=84893432219&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893432219&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2013.85

DO - 10.1109/FOCS.2013.85

M3 - Conference contribution

AN - SCOPUS:84893432219

SN - 9780769551357

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 746

EP - 755

BT - Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013

T2 - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013

Y2 - 27 October 2013 through 29 October 2013

ER -