License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.69
URN: urn:nbn:de:0030-drops-156658
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15665/
Fleming, Noah ;
Göös, Mika ;
Grosser, Stefan ;
Robere, Robert
On Semi-Algebraic Proofs and Algorithms
Abstract
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.
BibTeX - Entry
@InProceedings{fleming_et_al:LIPIcs.ITCS.2022.69,
author = {Fleming, Noah and G\"{o}\"{o}s, Mika and Grosser, Stefan and Robere, Robert},
title = {{On Semi-Algebraic Proofs and Algorithms}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {69:1--69:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15665},
URN = {urn:nbn:de:0030-drops-156658},
doi = {10.4230/LIPIcs.ITCS.2022.69},
annote = {Keywords: Proof Complexity, Extended Formulations, Circuit Complexity, Sherali-Adams}
}
|
Keywords: |
|
Proof Complexity, Extended Formulations, Circuit Complexity, Sherali-Adams |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
