Probabilistic Meta-Complexity

Zoom link for remote attendees

Meeting ID: 999 4631 3276 Passcode: 123123

Abstract: Understanding the extent to which data can be compressed is a critical task with implications across numerous areas of computer science, including data transmission, storage, and machine learning. The (in)compressibility of a string serves as a measure of its complexity. But how difficult is it to determine a string’s compressibility? This question lies at the heart of an active research program known as meta-complexity—the study of the computational complexity of complexity itself.

In this talk, I will present various results connecting compression and meta-complexity to fundamental questions in learning theory, cryptography, algorithms, and average-case complexity. Central to many recent advances is a novel notion of compression, where a string is represented *probabilistically* rather than deterministically. I will highlight the impact of this perspective and discuss a recent algorithmic breakthrough that establishes the existence of infinitely many prime numbers with succinct probabilistic representations.

Bio: Igor Oliveira is an Associate Professor at the University of Warwick, UK. He obtained a Ph.D. in Computer Science from Columbia University in 2015, working under the supervision of Prof. Rocco Servedio and Prof. Tal Malkin. After his doctorate, he held postdoctoral positions in Prague and Oxford, and served both as a research fellow and as a program organizer at the Simons Institute for the Theory of Computing at UC Berkeley. He has made extensive contributions to theoretical computer science, covering areas such as complexity lower bounds, pseudodeterministic prime generation, meta-complexity, logical foundations of complexity theory, and interactions between learning, complexity, and cryptography. His achievements have been recognized with a Royal Society University Research Fellowship and an ERC Starting Grant.