Lecturers: Ronald de Haan, Noel Arteche
In the first week, the course features some introductory lectures. In addition, you are expected to do some self-study of video recordings of lectures at the recent Simons Institute program on Meta Complexity. We will also have a Q&A session in the first week, where you can ask about and discuss the material in the video recordings.
In the second week, you will read and study a research paper on the topic of meta complexity. There will be opportunity to ask questions about the paper in the case that you get stuck or would like some help and/or guidance. You can indicate your preferences for which paper to study, and we will have a session where we agree on an (injective) assignment of (pairs of) students to papers, in order to make sure that the presentations provide us all with a varied and coherent view on the research field.
In the third or fourth week, we will have one or more sessions where all (pairs of) students present their paper. This will provide us all with a sort of workshop on recent developments in the research field. The main aim of the presentation is to educate your fellow students (and the lecturers) on the results and message of the paper that you're presenting.
(The remainder of) the final week is dedicated to writing a final report. This could be a summary of the paper, for example, where you describe the main results of the paper, their context, their impact on the field, and where you describe the main (technical) elements involved in the main proofs.
The course is graded on a pass/fail basis. Your grade will be based on your participation, on your presentation of one of the research papers, and on the final written report that you hand in.
The following list contains readings and video lectures that are intended for self-study for all students of the course. You can use these to get a good overview of the overall research area.
The following is a (preliminary) list of good candidates for research papers to present.
Papers indicated with an asterisk (*) are most central to the topic, and we aim to get all those assigned to students.
| When? | Where? | What? |
|---|---|---|
| Week 1 | ||
| Mon 8 Jan. 10–12 | SP107 F1.15 | Lecture 1: MCSP, Kolmogorov complexity, basic results (slides) |
| Mon 8 Jan. 13–15 | SP107 F1.15 | Lecture 2: Cryptography, one-way functions,
average-case complexity (slides) |
| Tue 9 Jan. 14–16 | SP107 F1.15 | Lecture 3: Circuit complexity & natural proofs (slides) |
| Thu 11 Jan. 13–15 | SP107 F1.15 | Lecture 4: Pseudorandomness, the Nisan-Wigderson generator, derandomization (slides) |
| Fri 12 Jan. 10–12 | SP107 F1.15 | Q&A session 1 |
| Fri 12 Jan. 13–15 | SP107 F1.15 | Q&A session 2 |
| Week 2 | ||
| - | ||
| Week 3 | ||
| Thu 25 Jan. 13:30–14:15 | SP107 F1.15 | Paper presentations |
| Week 4 | ||
| Mon 29 Jan. 10–16 | SP107 F1.15 | Paper presentations |