Abstract: Alice and Bob want to compute jointly/collaboratively a function. They are both super-computers. However, part of the input is with Alice and the other part is with Bob. How many bits do they *need* to communicate with each other, in the worst case, so that they can compute the function?
It turns out that the above puzzle and some of its variants have deep connection with all sorts of important questions: can we process large data using small memory? can we have efficient data-structures for a variety of problems? does there exist parallel algorithms for factoring?... and many others...
We will introduce the basic model of communication and briefly go through some of these exciting connections.
