School of Technology and Computer Science Seminars

On Protocols and Partitions

by Suhail Sherif (STCS, TIFR)

Friday, May 24, 2019 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
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.