Пятница 25.10. Дмитрий Соколов: "(Semi)Algebraic proofs over $\{\pm 1\}$ variables"

Дмитрий Соколов
Friday, October 25, 2019 - 17:00
ауд. 106

In this talk, we study versions of Polynomial Calculus and Sum-of-Squares proof systems. Current techniques for size lower on these proof systems bounds significantly use {0, 1} encoding of variables. More formally, we need to be able to assign any variable by a feasible value in a way to kill a term, that helps us to reduce a question about size to a question about degree.

We know the for ``Fourier'' $\{\pm 1\}$ encoding of boolean variables degree lower bound is not enough to prove size lower bounds [Buss et al. 2001]. In this talk we present show exponential lower bounds on monomial size of proofs in SoS and PCR as well as separation between these systems. It is a solution to an open problem from [Impagliazzo, Mouli, Pitassi 2019].