2026-07-21T12:31:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15665 2024-03-06T10:55:53Z ddc:004 open_access

On Semi-Algebraic Proofs and Algorithms Fleming, Noah Göös, Mika Grosser, Stefan Robere, Robert Proof Complexity Extended Formulations Circuit Complexity Sherali-Adams We give a new characterization of the Sherali-Adams proof system, showing that there is a degree-d Sherali-Adams refutation of an unsatisfiable CNF formula C if and only if there is an ε > 0 and a degree-d conical junta J such that viol_C(x) - ε = J, where viol_C(x) counts the number of falsified clauses of C on an input x. Using this result we show that the linear separation complexity, a complexity measure recently studied by Hrubeš (and independently by de Oliveira Oliveira and Pudlák under the name of weak monotone linear programming gates), monotone feasibly interpolates Sherali-Adams proofs. We then investigate separation results for viol_C(x) - ε. In particular, we give a family of unsatisfiable CNF formulas C which have polynomial-size and small-width resolution proofs, but for which any representation of viol_C(x) - 1 by a conical junta requires degree Ω(n); this resolves an open question of Filmus, Mahajan, Sood, and Vinyals. Since Sherali-Adams can simulate resolution, this separates the non-negative degree of viol_C(x) - 1 and viol_C(x) - ε for arbitrarily small ε > 0. Finally, by applying lifting theorems, we translate this lower bound into new separation results between extension complexity and monotone circuit complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noah Fleming and Mika Göös and Stefan Grosser and Robert Robere 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.69 urn:nbn:de:0030-drops-156658 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.69 eng https://creativecommons.org/licenses/by/4.0/legalcode