In Defence of Communication Complexity

In the basic model of communication complexity (Yao, 1979), Alice holds x, Bob holds y, and their goal is to compute a given function F(x,y) by communicating as few bits as possible. What elevates this model beyond its immediate appearances (communication networks, distributed systems) are several surprising connections to other seemingly unrelated areas of theoretical computer science and mathematics. I will discuss my PhD work in this area, with applications to circuit complexity, proof complexity, combinatorial optimisation (size of linear programming formulations), and graph theory (Alon-Saks-Seymour conjecture). A central theme in my research has been the introduction and application of several new Big Hammers, so-called "query-to-communication lifting" theorems. These new techniques have allowed me and my coauthors to resolve several fundamental open problems in communication complexity, some dating back to Yao's original 1979 paper that started the field.

Bio:
Mika Göös is a postdoctoral fellow in the Theory of Computing group at Harvard. He obtained his PhD from the University of Toronto (2016) under the supervision of Toniann Pitassi. He also holds an MSc from the University of Oxford (2011) and a BSc from Aalto University (2010). His research interests revolve around computational complexity theory.