Complexity Theory Through Play, by Prof. Mika Göös

Inaugural Lecture - Complexity Theory Through Play, by Prof. Mika Göös Abstract Computational complexity theory addresses the question: What are the fundamental limitations of efficient computation? The foundational question of the field – the P ≠ NP conjecture – is the principal motivator for the research conducted in our Theory of Computation Lab at EPFL. I discuss recent results from our lab, highlighting several surprising interconnections between seemingly different areas of computer science and math: playing the Hex board game, a resolution of a 30-year-old conjecture in graph theory, as well as applications to automata theory and computational learning theory. About the speaker Mika Göös is an Assistant Professor in the Theory of Computation Lab at EPFL since 2020. He is fascinated by impossibility phenomena in mathematics and theoretical computer science: Gödel’s incompleteness theorem, Turing’s uncomputability of the halting problem, the P ≠ NP conjecture. Previously, he was a post-doc at Stanford, Princeton IAS, and Harvard. He completed his PhD in 2016 at the University of Toronto under the supervision of Toniann Pitassi.