Direct Products in Communication Complexity
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff · 2013
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 μnbe the product distribution on n inputs and fndenote 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)n, fn, T) ≤ exp(-Ω(n)). When μ is a product distribution, we prove a nearly optimal result: as long as T log2T ≪ Cn, we must have suc(μn, fn, T) ≤ exp(-Ω(n)).