ECCC-Report TR20-183https://eccc.weizmann.ac.il/report/2020/183Comments and Revisions published for TR20-183en-usSun, 06 Dec 2020 04:49:15 +0200
Paper TR20-183
| Constant Depth Formula and Partial Function Versions of MCSP are Hard |
Rahul Ilango
https://eccc.weizmann.ac.il/report/2020/183Attempts to prove the intractability of the Minimum Circuit Size Problem (MCSP) date as far back as the 1950s and are well-motivated by connections to cryptography, learning theory, and average-case complexity. In this work, we make progress, on two fronts, towards showing MCSP is intractable under worst-case assumptions.
While Masek showed in the late 1970s that the version of MCSP for DNF formulas is NP-hard, extending this result to the case of depth-$3$ AND/OR formulas was open. We show that determining the minimum size of a depth-$d$ formula computing a given Boolean function is NP-hard under quasipolynomial-time randomized reductions for all constant $d \geq 2$. Our approach is based on a method to "lift" depth-$d$ formula lower bounds to depth-$(d+1)$. This method also implies the existence of a function with a $2^{\Omega_d(n)}$ additive gap between its depth-$d$ and depth-$(d+1)$ formula complexity.
We also make progress in the case of general, unrestricted circuits. We show that the version of MCSP where the input is a partial function (represented by a string in $\{0,1,\star\}^*$) is not in P under the Exponential Time Hypothesis (ETH).
Intriguingly, we formulate a notion of lower bound statements being $(P/poly)$-recognizable that is closely related to Razborov and Rudich's definition of being $(P/poly)$-constructive. We show that unless there are subexponential-sized circuits computing SAT, the collection of lower bound statements used to prove the correctness of our reductions cannot be $(P/poly)$-recognizable.Sun, 06 Dec 2020 04:49:15 +0200https://eccc.weizmann.ac.il/report/2020/183