- A-212 (STCS Seminar Room)
compute a certain function f(x,y) with the least amount of communication between them. Note that here we are not concerned about the number of computational steps, or the size of the computer memory used. Communication complexity tries to quantify the amount of
communication required for such distributed computations. Of course they can always succeed by having Alice send her whole n-bit string to Bob, who then computes the function, but the idea here is to find clever ways of calculating f with less than n bits of communication.
Reference: Communication complexity By Eyal Kushilevitz, Noam Nisan
(We will try to cover the first chapter of this book.)