Speaker: |
Suhail Sherif |

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

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

(Scan to add to calendar)

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.