Talks
Fall 2018

A Survey on MCSP
Thursday, September 13th, 2018, 10:00 am–11:00 am
Event:
Speaker:
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.