Time: Wednesday at 13:30-15:00
Location: MB2.23 (Mathematical Sciences Building)
Meta-complexity refers to the complexity of computational problems and tasks that are themselves about computations and their complexity.Â
This research-focused reading group will explore meta-complexity and its connections to circuit complexity, average-case complexity, cryptography, and learning. Time permitting and depending on the background of the participants, we might also cover topics related to the meta-mathematics of complexity theory.
Everyone is welcome to attend the reading group. If you'd like to join us, please send an email to igorcarb@gmail.com to be added to our mailing list.
16/October (Igor Oliveira): Introduction. MCSP and MINKT. Connection to average-case complexity. Reductions from Set Cover to variants of MCSP.
References: [Notes] [ILO20]
23/October (Jinqiao Hu): Randomized Kolmogorov complexity and coding theorems.
References: [LO21] [LO22]
30/October (Dimitrios Tsintsilindas): NP-hardness of MINKT* (Part 1).
References: [Notes] [Hir22]
6/November (Igor Oliveira): NP-hardness of MINKT* (Part 2).
References: [Notes] [Hir22]
13/November (Zhenjian Lu): Connections between cryptography and meta-complexity.
References: [Slides] [LS24]
20/November (Igor Oliveira): Connections between learning and meta-complexity.
References: [CIKK16] [Vad17]
27/November: Complexity Day at Imperial College London
4/December (Erfan Khaniki): Nisan-Wigderson generators in proof complexity.
References: [Kha22]
11/December (Dimitrios Tsintsilindas): Meta-mathematics of proof complexity.
References: [KP89], [Oli24]
Useful References:
[1] Rahul Ilango's Tutorial on Meta-Complexity (DIMACS Workshop "Frontiers in Complexity Theory: A Graduate Workshop"), 2024.
[2] Tutorial on Probabilistic Kolmogorov Complexity and Its Applications (CIRM Workshop "Randomness, Information, and Complexity"), 2024.
[3] Survey: Meta-Mathematics of Computational Complexity Theory, 2024.
[4] Videos from the Bootcamp Workshop of the Meta-Complexity Program at the Simons Institute for the Theory of Computing, 2023.
[5] Survey: Theory and Applications of Probabilistic Kolmogorov Complexity, 2022.
[6] Shuichi Hirahara's Survey: Meta-Computational Average-Case Complexity: A New Paradigm Toward Excluding Heuristica, 2022.