Prof. Rahul Santhanam, University of Oxford
The Minimum Circuit Size Problem: A Survey and Recent Results
Departmental Seminar: a talk for everyone giving a good introduction to a topic.
In the Minimum Circuit Size Problem (MCSP), the input is the truth table of a Boolean function F, and a parameter s, and the output is YES iff F has circuits of size at most s. Intuitively speaking, MCSP is a problem that asks about the compressibility of strings.
MCSP is a fundamental problem that has been studied since the 1950s, and yet remains mysterious. It is easy to see that MCSP is in NP, but there is no strong evidence for MCSP being solvable in polynomial time or MCSP being NP-complete. While MCSP is hard to classify in complexity-theoretic terms, it has deep connections to many areas of computer science, including circuit complexity, learning theory, cryptography and proof theory.
I will informally survey work on MCSP, and sketch some recent results. I will try to make the talk accessible to a broad audience.