Open Collections

Dmitry Sokolov: (Semi)Algebraic Proofs over $\{\pm 1\}$ Variables

Banff International Research Station for Mathematical Innovation and Discovery

One of the major open problem 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 talk 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.

Mathematics; Computer science; Mathematical logic and foundations; Theoretical computer science

video/mp4

Author affiliation: Lund University

2020-07-19

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/75208

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/