Por Bruno Loff (University of Porto).

The 2021 Abel prize in Mathematics was awarded to Avi Wigderson, a researcher in Computational Complexity. But why was he even eligible? Isn't Computational Complexity part of computer science?

In the talk, I will make the argument that Computational Complexity is a foundational mathematical discipline. For this purpose, I will give a survey of its history, starting with Hilbert's address to the World Congress of Mathematics in 1900, through Alan Turing's invention of the computer and the discovery and eventual formalization of the P vs NP problem. I will try to convince you that this is one of the most interesting unsolved mathematical problems of our time. I will then give a brief introduction to communication complexity and Karchmer-Wigderson games, as an approach to solving the area's fundamental problems, co-invented by Avi Wigderson.

Time permitting, I may sketch the state of the art and describe known barriers to solving the P vs NP problem, I may enumerate some broad applications of the field, I may describe an algebraic-geometric variant of the P vs NP problem, or we can do a back-and-forth in ask-me-anything style.

The talk will be very broad-scope, light-touch, and is directed at a general mathematical audience.

Transmissão via Zoom.