Speaker: Omri Weinstein, Princeton University
Title: Direct Products in Communication Complexity
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(\mu,f,C) denote the maximum success probability of a 2party communication protocol for computing f(x,y) with C bits of communication, when the inputs (x,y) are drawn from the distribution \mu. Let \mu^n be the product distribution on n inputs and f^n denote the function that computes n copies of f on these inputs. We prove that if T << C\sqrt{n} and suc(\mu,f,C)<0.9, then suc(\mu^n,f^n,T)<exp(\Omega(n)). When \mu is a product distribution, we prove a nearly optimal result: as long as T << Cn, we must have suc(\mu^n,f^n,T) < exp(\Omega(n)).
This is joint work with Mark Braverman, Anup Rao and Amir Yehudayoff.
