Marc Vinyals: Deterministic communication vs. partition number

PRACTICALITIES

Lunch is served at 12:00 noon (register at this doodle at the latest on Saturday March 19, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.

 

ABSTRACT

Alice is given a clique in a graph and Bob an independent set in the same graph. How much communication do they need to decide if these two sets of vertices intersect? This seemingly innocent question is connected to deep topics in communication complexity and analysis of Boolean functions.

In a breakthrough paper in FOCS 2015, Göös, Pitassi and Watson solved this and other problems by proving lower bounds in query complexity, and then giving an explicit way of amplifying query complexity lower bounds to communication complexity lower bounds. This solved a problem that had been open since 1979, and the paper has already generated a long (and growing) list of follow-up works that have made progress on other long-standing open problems in different areas of communication complexity and query complexity.

In this seminar, we will go over the GPW paper. During the first hour we will review the new results, and after the break we will present a detailed proof of their main theorem.