ECCC-Report TR23-010https://eccc.weizmann.ac.il/report/2023/010Comments and Revisions published for TR23-010en-usTue, 14 Feb 2023 21:22:46 +0200
Paper TR23-010
| Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem |
Per Austrin,
Kilian Risse
https://eccc.weizmann.ac.il/report/2023/010We prove lower bounds for the Minimum Circuit Size Problem (MCSP) in the Sum-of-Squares (SoS) proof system. Our main result is that for every Boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$, SoS requires degree $\Omega(s^{1-\epsilon})$ to prove that $f$ does not have circuits of size $s$ (for any $s > \text{poly}(n)$). As a corollary we obtain that there are no low degree SoS proofs of the statement $\text{NP} \not \subseteq \text{P/poly}$.
We also show that for any $0 < \alpha < 1$ there are Boolean functions with circuit complexity larger than $2^{n^{\alpha}}$ but SoS requires size $2^{2^{\Omega(n^{\alpha})}}$ to prove this. In addition we prove analogous results on the minimum monotone circuit size for monotone Boolean slice functions.
Our approach is quite general. Namely, we show that if a proof system $Q$ has strong enough constraint satisfaction problem lower bounds that only depend on good expansion of the constraint-variable incidence graph and, furthermore, $Q$ is expressive enough that variables can be substituted by local Boolean functions, then the MCSP problem is hard for $Q$.Tue, 14 Feb 2023 21:22:46 +0200https://eccc.weizmann.ac.il/report/2023/010