Speaker: |
Ajesh Babu School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road |

Date: |
Friday, 3 Jul 2009 (all day) |

Venue: |
A-212 (STCS Seminar Room) |

(Scan to add to calendar)

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.)