On Protocols and Partitions

Speaker: 

Time: 

Friday, 24 May 2019, 17:15 to 18:15

Venue: 

  • A-201 (STCS Seminar Room)

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.