__
TR20-012 | 14th February 2020 19:13
__

#### (Semi)Algebraic Proofs over $\{\pm 1\}$ Variables

**Abstract:**
One 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.