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.
Contact us: