The Computer Science Department at Sapienza University of Rome is promoting a series of Distinguished Lectures held by renowned speakers on fundamental research topics in computer science. The goal of each lecture (approx. 45 minutes) is to explain why the theme is indeed fundamental, and to summarize the state of the art up to cutting edge research.
Supported by MIUR under grant "Dipartimenti di eccellenza 2018-2022", of the Computer Science Department at Sapienza University.
Lecturer: Luca Trevisan
Title: P versus NP
Location: Aula Seminari, Via Salaria 113, 3rd Floor.
Date: February 6, 2020.
Luca's research is focused on computational complexity, on analysis of algorithms, and on problems at the intersection of pure mathematics and theoretical computer science.
Luca received the ACM STOC'97 Danny Lewin (best student paper) award, the 2000 Oberwolfach Prize, and the 2000 Sloan Fellowship. He was an invited speaker at the 2006 International Congress of Mathematicians. He is a recipient of a 2019 ERC Advanced Grant.
We will trace the origin of this question, and its conceptual implications about the nature of mathematical proofs and the notions of expertise and creativity. We will see why certain proof strategies cannot possibly resolve this problem, and why fundamentally different ideas are needed to make progress. Finally, we will discuss "average-case analysis" extensions of the P versus NP problems, which are needed to reason about the security of cryptographic protocols and blockchains and about the complexity of problems arising in machine learning.