Abstract: The first observation that one makes when analyzing communication protocols between Alice and Bob is that a cost c protocol partitions the input space into 2^c combinatorial rectangles. An immediate consequence of this is that if a function cannot be partitioned into 2^c combinatorial rectangles, then it cannot be computed with c bits of communication.
But if a function CAN be partitioned into 2^c combinatorial rectangles, can it be computed with c bits of communication? In this talk, we will look at known results on this question:
- If the 0s/1s of a function can be partitioned into 2^c combinatorial rectangles, it can be computed with c^2 bits of computation. [Aho Ullman Yannakakis, 1981]
- There is a function with a partition into 2^c combinatorial rectangles that requires (almost) c^2 bits of communication. [Göös Pitassi Watson, 2015]
The latter result goes through the analogous questions and answers in the simpler world of query complexity, in which "combinatorial rectangles" is replaced with "width-c subcubes".
This talk does not assume any prior knowledge of communication complexity.
