November 22, 2021. D. M. Itsykson. Proof complexity lower bounds via communication arguments.

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.

List of talks at previous sessions of the seminar.