Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR97-015 | 21st April 1997 00:00

Interpolation by a game


Authors: Jan Krajicek
Publication: 25th April 1997 17:32
Downloads: 1047


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.).

ISSN 1433-8092 | Imprint