ECCC-Report TR22-003https://eccc.weizmann.ac.il/report/2022/003Comments and Revisions published for TR22-003en-usThu, 20 Jan 2022 04:08:30 +0200
Revision 1
| On Semi-Algebraic Proofs and Algorithms |
Robert Robere,
Noah Fleming,
Mika Göös,
Stefan Grosser
https://eccc.weizmann.ac.il/report/2022/003#revision1We 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.
Thu, 20 Jan 2022 04:08:30 +0200https://eccc.weizmann.ac.il/report/2022/003#revision1
Paper TR22-003
| On Semi-Algebraic Proofs and Algorithms |
Robert Robere,
Noah Fleming,
Mika Göös,
Stefan Grosser
https://eccc.weizmann.ac.il/report/2022/003We 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.
Tue, 04 Jan 2022 20:55:39 +0200https://eccc.weizmann.ac.il/report/2022/003