Abstract:
We introduce a notion of a "real game" (a generalization of the Karchmer - Wigderson game), and "real communication complexity", and relate them to the size of monotone real formulas and circuits. We give an exponential lower bound for tree-like monotone protocols of small real communication complexity solving the monotone communication complexity problem associated with the bipartite perfect matching problem. This work is motivated by a research in interpolation theorems for propositional logic. Our main objective is to extend the communication complexity approach of our earlier papers to a wider class of proof systems. In this direction we obtain an effective (monotone) interpolation in a form of a protocol of small real communication complexity. Together with the above mentioned lower bound for tree - like protocols this yields as a corollary a lower bound on the number of steps for particular semantic derivations of Hall's theorem (these include tree - like cutting planes proofs for which an exponential lower bound was demonstrated by Impagliazzo et. al.).