|
SEMINARS |
General Mathematics Seminar of the St. Petersburg Division of Steklov Institute of Mathematics, Russian Academy of Sciences
|
|||
|
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 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. |