(Semi)Algebraic proofs over ±1 variables

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 {± 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 {± 1} basis. We show lower bounds on random Δ-CNF formulas and formulas composed with a gadget. As a byproduct, we establish a separation between Polynomial Calculus and Sum-of-Squares over the {± 1} basis by proving a lower bound on the Pigeonhole Principle.

Authors

• Dmitry Sokolov 0001

Keywords

• lower bounds
• polynomial calculus
• proof complexity
• random formulas
• sum-of-squares