2026-07-26T17:22:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18301 2024-03-06T11:01:33Z ddc:004 open_access

Sum-Of-Squares Lower Bounds for the Minimum Circuit Size Problem Austrin, Per Risse, Kilian Proof Complexity Sum of Squares Minimum Circuit Size Problem 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}ⁿ → {0,1}, SoS requires degree Ω(s^{1-ε}) to prove that f does not have circuits of size s (for any s > poly(n)). As a corollary we obtain that there are no low degree SoS proofs of the statement NP ⊈ P/poly. We also show that for any 0 < α < 1 there are Boolean functions with circuit complexity larger than 2^{n^α} but SoS requires size 2^{2^Ω(n^α)} 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Per Austrin and Kilian Risse 2023 Is Part Of LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2023.31 urn:nbn:de:0030-drops-183011 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.31 eng https://creativecommons.org/licenses/by/4.0/legalcode