TCS+ Talk: Rahul Ilango

Title: The Story of the Minimum Circuit Size Problem (MCSP) So Far, and Hardness for Multi-output Circuits

Abstract: The Minimum Circuit Size Problem (MCSP) roughly asks what the "complexity" of a given string is. Informally, one can think of this as determining the degree of "computational order" a string has.

In the past several years, there has been a resurgence of interest in MCSP. A series of exciting results have begun unraveling what looks to be a fascinating story. This story already reveals deep connections between MCSP and a growing list of fields, including cryptography, learning theory, structural complexity theory, average-case complexity, and circuit complexity. As an example, Santhanam recently proved a conditional equivalence between the complexity of MCSP and the existence of one-way functions.

This talk is split into two parts. The first part is a broad introduction to MCSP, answering the following questions: What is this problem? Why is it interesting? What do we know so far, and where might the story go next? The second part discusses recent joint work with Bruno Loff and Igor Oliveira showing that the "multi-output version" of MCSP is NP-hard.