Zoë Bell

Thesis Advisor: Dr. Nicholas Pippenger (Harvey Mudd College - Department of Mathematics)

Second Reader: Dr. Ran Libeskind-Hadas (Harvey Mudd College - Department of Computer Science)

Contact: zbell@hmc.edu

The Story of MCSP: How Hard Is It to Show How Hard Showing Hardness Is?

The Minimum Circuit Size Problem (MCSP) is a problem with a long history in computational complexity theory that has recently experienced a resurgence in interest. MCSP takes as input the description of a Boolean function f as a truth table as well as a size parameter s, and outputs whether there is a circuit that computes f of size ≤ s. Thus in a certain sense MCSP captures how hard it is to determine the circuit complexity of functions.

MCSP was initially a subject of interest in the USSR starting in the 1950's as a potential problem that had no better algorithm than brute force. It caused Leonid Levin to delay publishing his seminal 1973 paper introducing the idea of NP-completeness (Stephen Cook independently did the same around the same time) because he wanted to establish whether MCSP was NP-complete. MCSP is not in P unless cryptography breaks and it is easy to see that MCSP is in NP, but whether MCSP is NP-complete is still open to this day. However, researchers in the area widely believe it to be. In 2000, a paper by Kabanets and Cai proved that if MCSP was shown to be NP-complete under "natural" reductions like those that had shown the NP-completeness of virtually every such problem thus far, then this would lead to dramatic results in complexity theory that seemed well beyond current techniques (such as showing that E ⊄ P/poly). This resparked interest in the problem and since then MCSP has been shown to have connections to many areas, such as circuit complexity, Kolmogorov complexity, average case complexity, proof complexity, pseudorandomness, cryptography, learning and more.

One line of work has continued to explore the implications of various kinds of reductions being used to show the NP-hardness of MCSP, which are often so strong and beyond current techniques that they are widely interpreted as showing that these kind of reductions are not tractable and that it is "hard" to show the hardness of MCSP (which itself shows how hard Boolean functions are). This meta flavor is part of what makes the problem so appealing and leads to its interesting connections. This thesis project will seek to continue to better understand under which kinds of reductions it might be more or less possible to show that MCSP is NP-complete, as well as important variants on MCSP. So far, I have used the approach of Saks and Santhanam (2020) to prove that if, when given a truth table of size 2ⁿ, approximating MCSP within a factor superpolynomial in n is NP-complete under general polynomial-time Turing reductions, then E ⊄ P/poly. This provides a barrier to Hirahara (2018)'s suggested program of using the NP-completeness of a 2^(1-c)n-approximation version of MCSP to show that if NP is hard in the worst case, it is also hard on average (i.e., to rule out Heuristica), though randomized reductions remain potentially tractable.