Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR22-003 | 20th January 2022 04:08

#### On Semi-Algebraic Proofs and Algorithms

Revision #1
Authors: Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere
Accepted on: 20th January 2022 04:08
Keywords:

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 $\varepsilon > 0$ and a degree-$d$ conical junta $J$ such that $viol_C(x) - \varepsilon = 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; this sharpens a recent feasible interpolation result due to Hakoniemi.

We then investigate separation results for $viol_C(x) - \varepsilon$. 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 $\Omega(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) - \varepsilon$ for arbitrarily small $\varepsilon > 0$. Finally, by applying lifting theorems, we translate this lower bound into new separation results between extension complexity and monotone circuit complexity.

Changes to previous version:

small typos fixed

### Paper:

TR22-003 | 4th January 2022 20:43

#### On Semi-Algebraic Proofs and Algorithms

TR22-003
Authors: Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere
Publication: 4th January 2022 20:55
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 $\varepsilon > 0$ and a degree-$d$ conical junta $J$ such that $viol_C(x) - \varepsilon = 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; this sharpens a recent feasible interpolation result due to Hakoniemi.
We then investigate separation results for $viol_C(x) - \varepsilon$. 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 $\Omega(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) - \varepsilon$ for arbitrarily small $\varepsilon > 0$. Finally, by applying lifting theorems, we translate this lower bound into new separation results between extension complexity and monotone circuit complexity.