IC Colloquium: Communication Lower Bounds from Query Complexity
Event details
| Date | 13.03.2019 |
| Hour | 10:15 › 11:15 |
| Location | |
| Category | Conferences - Seminars |
By: Mika Göös - IAS School of Mathematics
IC Faculty candidate
Abstract:
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 Goos is a postdoctoral member at IAS. Prior to IAS he was the Michael O. Rabin postdoctoral fellow 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.
More information
IC Faculty candidate
Abstract:
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 Goos is a postdoctoral member at IAS. Prior to IAS he was the Michael O. Rabin postdoctoral fellow 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.
More information
Practical information
- General public
- Free
- This event is internal
Contact
- Host: Ola Svensoon