Пятница 25.10. Дмитрий Соколов: "(Semi)Algebraic proofs over $\{\pm 1\}$ variables"
PDMI seminars
Тема: (Semi)Algebraic proofs over $\{\pm 1\}$ variables
Место: ауд. 106
Время: 25.10.2019, 17:00
Докладчик: Дмитрий Соколов
Abstract:
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].