Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-010 | 13th February 2023 16:11

Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem


Authors: Per Austrin, Kilian Risse
Publication: 14th February 2023 21:22
Downloads: 407


We 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$.

ISSN 1433-8092 | Imprint