ECCC
Electronic Colloquium on Computational Complexity
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 solving the monotone ... more >>>



ISSN 1433-8092 | Imprint