Meta-mathematics of complexity theory
Embedded Files
Talk at the Workshop "Frontiers in Complexity Lower Bounds".
Isaac Newton Institute of Mathematical Sciences (Cambridge, UK), 2026.
Tutorial at the Workshop "Randomness, Information, and Complexity" (CIRM, 2024)
Part I
Part I
Probabilistic notions of Kolmogorov complexity
Part II
Part II
Complexity theory through the lens of Kolmogorov complexity
Part III
Part III
Pseudodeterministic constructions and rK
Meta-mathematics of complexity theory
Talk at the Workshop "Proof Complexity and Beyond".
Oberwolfach Research Institute for Mathematics (MFO), 2024.
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.
Probabilistic Kolmogorov complexity
Talk at the Workshop "Meta-Complexity Boot Camp".
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.
Page updated
Google Sites
Report abuse