ECCC-Report TR20-012https://eccc.weizmann.ac.il/report/2020/012Comments and Revisions published for TR20-012en-usSun, 16 Feb 2020 08:22:49 +0200
Paper TR20-012
| (Semi)Algebraic Proofs over $\{\pm 1\}$ Variables |
Dmitry Sokolov
https://eccc.weizmann.ac.il/report/2020/012One of the major open problems in proof complexity is to prove lower bounds on $AC_0[p]$-Frege proof
systems. As a step toward this goal Impagliazzo, Mouli and Pitassi in a recent paper suggested to prove
lower bounds on the size for Polynomial Calculus over the $\{\pm 1\}$ basis. In this paper we show a
technique for proving such lower bounds and moreover we also give lower bounds on the size for
Sum-of-Squares over the $\{\pm 1\}$ basis.
We show lower bounds on random $\Delta$-CNF formulas and formulas composed with a gadget. As a byproduct,
we establish a separation between Polynomial Calculus and Sum-of-Squares over the $\{\pm 1\}$ basis by
proving a lower bound on the Pigeonhole Principle.Sun, 16 Feb 2020 08:22:49 +0200https://eccc.weizmann.ac.il/report/2020/012