Rahul Ilango: Metacomplexity - Part 1

Rahul Ilango, Massachusetts Institute of Technology, presents a three-part tutorial on metacomplexity at the Frontiers in Complexity Theory workshop for graduate students held at DIMACS July 29 - August 1, 2024. This is Part 1.
Description: In this tutorial we will give an introduction to the area of metacomplexity. No prior background is assumed, and we will start with an overview of the major themes in metacomplexity. Our main goal is to build towards Hirahara's recent breakthrough showing that "Partial-MCSP is NP-hard" (you do not need to know what this means yet). Along the way, we will encounter important tools from the various areas of theoretical computer science that should be of broad interest (e.g. secret sharing, reconstructive extractors, the PCP theorem, and more!).
Link to workshop webpage: dimacs.rutgers....