Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > EFFECTIVE INTERPOLATION THEOREMS:
Reports tagged with effective interpolation theorems:
TR97-015 | 21st April 1997
Jan Krajicek

Interpolation by a game

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




ISSN 1433-8092 | Imprint