[Proof Complexity] Seminar Thu Apr 8 14:00 CET with Dmitry Sokolov: (Semi)Algebraic proofs over {±1} variables

[Jakob Nordström]

Dear all,

On Thursday April 8 at 14:00 CET we will have a seminar with Dmitry Sokolov from  St.Petersburg State University titled "(Semi)Algebraic proofs over {±1} variables". See below for the abstract.

We will meet virtually at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners an overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No excuses needed; no questions asked.)

More information about upcoming video seminars is posted (from time to time) at http://www.csc.kth.se/~jakobn/videoseminars/. If you do not wish to receive these announcements, or receive several copies of them, please send a message to jakob.nordstrom at cs.lth.se.

Best regards,
Jakob Nordström

**********

Thursday Apr 8 at 14:00
(Semi)Algebraic proofs over {±1} variables
(Dmitry Sokolov, St.Petersburg State University)

One of the major open problems in proof complexity is to prove lower bounds on AC0[p]-Frege proof systems. As a step toward this goal Impagliazzo, Mouli and Pitassi in a recent paper suggested proving lower bounds on the size for Polynomial Calculus over the {±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 {±1} basis.

We discuss the difference between {0, 1} and {+1, -1} cases and problems in further generalizations of the lower bounds.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98
http://www.csc.kth.se/~jakobn/ (webpages still in transit)