ECCC-Report TR97-015https://eccc.weizmann.ac.il/report/1997/015Comments and Revisions published for TR97-015en-usFri, 25 Apr 1997 17:32:09 +0300
Paper TR97-015
| Interpolation by a game |
Jan Krajicek
https://eccc.weizmann.ac.il/report/1997/015
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.).
Fri, 25 Apr 1997 17:32:09 +0300https://eccc.weizmann.ac.il/report/1997/015