Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

On Semi-Algebraic Proofs and Algorithms

RSS-Feed




Revision #1
Authors: Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere
Accepted on: 20th January 2022 04:08
Downloads: 556
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


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.



ISSN 1433-8092 | Imprint