Theory Lunch Seminar

Seminars
OMRI WEINSTEIN
Research Intern
Microsoft Research
Direct Products in Communication Complexity
Wednesday, April 2, 2014 - 12:00pm to 1:00pm
6115 
Gates&Hillman Centers
Abstract:

We prove exponentially small upper bounds on the success probability for computing multiple independent copies of any function over any distribution using a communication protocol. If C bits of communication are required for solving a single copy of f(x,y) over input distribution \mu with probability 2/3, then any protocol attempting to solve n independent copies of f using << \sqrt{n}*C communication, will succeed with probability only exp(-Omega(n)). If \mu is a product distribution, we prove a near optimal result: Any protocol using << n*C communication in order to solve all copies will succeed with probability at most exp(-Omega(n)). This matches the communication and success of the trivial sequential protocol.

Joint work with Mark Braverman, Anup Rao and Amir Yehudayoff.

For More Information, Please Contact:

ggurugan [atsymbol] andrew ~replace-with-a-dot~ cmu ~replace-with-a-dot~ edu