Abstract
The Minimum Circuit Size Problem (MCSP) asks whether a given Boolean function, represented by its truth table, has small circuits. MCSP is in NP, and is in a sense the inverse problem to SAT. Unlike SAT, its complexity remains poorly understood. I will make the case that MCSP is as fundamental as SAT, and will survey work on different aspects of the problem, including connections to learning, pseudorandomness and natural proofs.