Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

On semi-algebraic proofs and algorithms

Fleming, Noah LU orcid ; Göös, Mika ; Grosser, Stefan and Robere, Robert (2022) In LIPIcs 215. p.1-69
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
; ; and
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
series title
LIPIcs
editor
Braverman, Mark
volume
215
article number
69
pages
25 pages
publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
external identifiers
  • scopus:85124035599
DOI
10.4230/LIPICS.ITCS.2022.69
language
English
LU publication?
no
id
8f10fe9c-4b51-4c68-826c-a27404a5373a
date added to LUP
2025-11-05 16:02:40
date last changed
2026-08-09 04:00:54
@inproceedings{8f10fe9c-4b51-4c68-826c-a27404a5373a,
  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 ε &gt; 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.<br/><br/>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 ε &gt; 0. Finally, by applying lifting theorems, we translate this lower bound into new separation results between extension complexity and monotone circuit complexity.}},
  author       = {{Fleming, Noah and Göös, Mika and Grosser, Stefan and Robere, Robert}},
  booktitle    = {{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}},
  editor       = {{Braverman, Mark}},
  language     = {{eng}},
  pages        = {{1--69}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
  series       = {{LIPIcs}},
  title        = {{On semi-algebraic proofs and algorithms}},
  url          = {{http://dx.doi.org/10.4230/LIPICS.ITCS.2022.69}},
  doi          = {{10.4230/LIPICS.ITCS.2022.69}},
  volume       = {{215}},
  year         = {{2022}},
}