The Minimum Circuit Size Problem through the Ages

Eric Allender (Rutgers University)

The Minimum Circuit Size Problem (MCSP) asks for the size of the smallest circuit that computes a given function. MCSP has played a significant role in the history of computational complexity theory, while somehow managing to avoid having its complexity be classified in the usual collection of complexity classes. This lecture will discuss some of this long history, present several connections between MCSP and central complexity-theoretic notions, and survey some of the recent developments where MCSP has played a crucial part.