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:

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.