RUS  ENG
Full version
SEMINARS

General Mathematics Seminar of the St. Petersburg Division of Steklov Institute of Mathematics, Russian Academy of Sciences
November 22, 2021 13:00, St. Petersburg, POMI, room 311 (27 Fontanka). Also it is possible to watch this talk in Zoom, see https://logic.pdmi.ras.ru/GeneralSeminar/index.html


Proof complexity lower bounds via communication arguments

D. M. Itsykson

St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences



Abstract: Consider the following game: each of two players has a subset of the same $n$-element set. They have to determine, whether their sets are disjoint or not transmitting a minimal number of bits. In 1992 Kalyanasundaram and Schnitger proved that even if the participants have access to common randomness and they have to compute the correct answer with probability $0.9$, then in the worst case they have to transmit at least $Cn$ bits, where $C$ is a constant.
In the talk, we learn how this result can be used for proving lower bounds on the size of derivations in propositional proof systems. First, we demonstrate this method on an elementary example for a particular proof system (in this system unsatisfiability of the propositional formula is proved by considering different cases of parity of linear combinations of variables). Then we overview how this technique can be extended for many other proof systems.
No specific knowledge is required from the participants.


© Steklov Math. Inst. of RAS, 2024