Title: Introduction to communication complexity
Speaker: Nikos Leonardos, Rutgers University
Date: Wednesday, April 28, 2010 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
There are two parties, Alice and Bob. Each receives an n-bit string; Alice gets x, Bob gets y. Their goal is to compute a (boolean) function f(x,y). Since they can only see their own input, they need to communicate by sending bits to each other, until they both know f(x,y). We are interested in the amount of communication they need (say worst case over all x,y). We'll see some basic properties and simple lower-bounds for this model.
Another interesting model is one where there are more players, say 3, and while they can see the input of any other player, they cannot see their own. Proving lower-bounds in this model seems to be hard. It also allows for some clever protocols, and we'll see one.