1st Semester 2023/24: Meta-Complexity

Instructors

Ronald de Haan, Noel Arteche

ECTS

6

Description

In this project, we will study recent developments in the field of meta-complexity. As phrased in the description of a recent Simons Institute Program on the topic (https://simons.berkeley.edu/programs/Meta-Complexity2023): meta-complexity is a branch of computational complexity theory that studies the complexity of computational problems and tasks that are themselves about computations and their complexity. An example of this is the Minimum Circuit Size Problem (given the truth table of a Boolean function F, compute the minimum circuit size of F). Meta-complexity provides a unifying framework for a variety of important tasks in several important areas of computer science, including computational complexity, proof complexity, cryptography, and learning theory. In the past decade or so, there have been multiple new results in this field, and there remain plenty of open problems.

Organisation

In the first week, we will have some introductory lectures, as well as some self-study of video recordings of lectures at the recent Simons Institute program, followed by a session where students can ask about and discuss the material in the video recordings.

Starting from the second week, students get to read their assigned research paper, and prepare their presentation on it. The lecturers are available for help with this reading and the preparations. Presentations will be at the end of the third week, and in the fourth week, students write their final report (see 'Assessment').

Prerequisites

Basic knowledge of computational complexity theory is required to follow this project. This means that students ideally either should have taken the course Computational Complexity (in the MSc Logic), or have followed a similar course on computational complexity theory elsewhere.

Assessment

(Small groups of) students get assigned a research paper to read and present. In addition, students will write a short report at the end describing the main result(s) of their assigned paper, its context in the literature, and the main proof ideas used to show the result. The final (pass/fail) assessment will be based on the presentation and the report.

References

We will use video lectures from the recent Simons Institute program on meta complexity (https://simons.berkeley.edu/programs/Meta-Complexity2023), as well as use research papers from the literature. (The exact list of research papers that we will use will follow.) This recent Quanta Magazine article provides a useful introduction and some pointers to the literature (https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/).