Tutorial at the Workshop "Randomness, Information, and Complexity" (CIRM, 2024)

## Part I

Probabilistic Notions of Kolmogorov Complexity

## Part II

Complexity Theory Through the Lens of Kolmogorov Complexity

## Part III

Pseudodeterministic Constructions and rK

Unprovability of strong complexity lower bounds in bounded arithmetic

Talk at the Workshop "Proof Complexity and Meta-Mathematics".

Simons Institute for the Theory of Computing (UC Berkeley), 2023.

Learning from equivalence queries and unprovability of circuit upper bounds

Talk at the Workshop "Mathematical Approaches to Lower Bounds".

International Centre for Mathematical Sciences (ICMS, Edinburgh), 2022.

Extracting computational hardness from learning algorithms

Talk at the Workshop "Meta-Complexity, Barriers, and Derandomization".

DIMACS Workshop (Rutgers University), 2022.

Quantum learning algorithms imply circuit lower bounds

Talk at the Symposium on Foundations of Computer Science (FOCS), 2022.

Kolmogorov complexity, prime numbers, and complexity lower bounds

Talk at the LMS Computer Science Colloquium.

London Mathematical Society, 2020.

Consistency of circuit lower bounds with bounded theories

Talk at the Workshop "Proof Complexity".

Banff International Research Station (Canada), 2020.

Hardness magnification

Talk at the Workshop "MCSP and Hardness Magnification".

Symposium on Theory of Computing (STOC), 2020.

Towards a theory of probabilistic data representation (in Portuguese)

Talk at the "Seminários online de Grafos, Algoritmos e Combinatória".

Online Talk, 2020.

Hardness magnification

Talk at the Workshop "Boolean Devices".

Simons Institute for the Theory of Computing (UC Berkeley), 2018.

Addition is exponentially harder than counting for shallow monotone circuits

Talk at the Workshop "Connections Between Algorithm Design and Complexity Theory".

Simons Institute for the Theory of Computing (UC Berkeley), 2015.