Minimum Circuit Size Problem

The Minimum Circuit Size Problem (MCSP) asks: given the complete truth table of a Boolean function f, and an integer s, does f have a circuit of size at most s? MCSP is a natural and well-studied problem in NP, but we do not yet know if it is NP-hard. Instead, we have formal evidence that resolving the complexity of MCSP is hard:

• “simple” proofs that “MCSP is NP-hard” would imply breakthroughs in circuit complexity, and
• giving an efficient algorithm for MCSP would imply breakthrough derandomization.

Despite (and often because of) this, exciting results have recently emerged that leverage connections between MCSP and fundamental questions in theoretical computer science (including P vs NP, circuit lower bounds, derandomization, learning, and cryptography).

These pages collect events and resources about MCSP.

Upcoming: Workshop about MCSP and Hardness Magnification, at STOC 2020.