Antonina Kolokolova: Meta-complexity - lecture 1

Meta-complexity is the study of the complexity of computing hardness measures such as time-bounded versions of Kolmogorov complexity and circuit size. Here I will cover some results about complexity of computing these measures, and connections with learning theory and (time permititng) cryptography. Recording during the thematic meeting : « Complexity as a kaleidoscope » the April 03, 2025 at the Centre International de Rencontres Mathématiques (Marseille, France) Filmmaker : Guillaume Hennenfent Find this video and other talks given by worldwide mathematicians on CIRM's Audiovisual Mathematics Library: http://library.cirm-math.fr. And discover all its functionalities: - Chapter markers and keywords to watch the parts of your choice in the video - Videos enriched with abstracts, bibliographies, Mathematics Subject Classification - Multi-criteria search by author, title, tags, mathematical area