@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}},
}