SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle

In this talk, I will discuss progress on showing hardness of the Minimum Circuit Size Problem (MCSP). Understanding the complexity of MCSP is a longstanding open question (since at least Levin's seminal work on NP-completeness). Over the past several years, researchers have utilized seemingly special properties of MCSP (not known for SAT) to show important connections between MCSP and other areas of theoretical computer science, including learning theory, cryptography, average-case complexity, and proof complexity.

We give, in our view, the strongest evidence yet that MCSP is in fact NP-complete (and thus that SAT does indeed have these special properties). Specifically, we show that, with probability one, there is a P/poly reduction from the NP-hard problem of approximating vertex cover on hypergraphs to MCSP on circuits that have access to a uniformly random oracle O. Building on this, we give the first candidate reduction from SAT to MCSP, and conclude that the existence of sufficiently "unstructured" functions implies a problem with a known (non-black-box) worst-case to average-case reduction is NP-complete. Curiously, a key part of our reduction is computing a cryptographic proof of work.