Fall 2018

A Survey on MCSP

Thursday, Sep. 13, 2018 10:00 am11:00 am PDT

Add to Calendar


Rahul Santhanam (University of Oxford)

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.