Skip to content Search
Search our website:

The Minimum Circuit Size Problem: A Survey and Recent Results

  • Speaker: Professor Rahul Santhanam, Department of Computer Science, Oxford
  • Date: Tuesday, 6 February 2018 from 17:00 to 18:00
  • Location: Room 151

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.