Communication complexity towards lower bounds on circuit depth

0175225 - MU-W 20020113 RIV CH eng J - Článek v odborném periodiku
Edmonds, J. - Impagliazzo, R. - Rudich, S. - Sgall, Jiří
Communication complexity towards lower bounds on circuit depth.
Computational Complexity. Roč. 10, č. 3 (2001), s. 210-246. ISSN 1016-3328. E-ISSN 1420-8954
Grant CEP: GA AV ČR IAA1019602; GA AV ČR IAA1019901; GA ČR GA201/97/P038; GA ČR GA201/01/1195; GA MŠMT ME 103
Klíčová slova: communication complexity%lower bounds
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.448, rok: 2001

Karchmer, Raz, and Wigderson, 1995, discuss the circuit depth complexity of $n$ bit Boolean functions constructed by composing up to $d = log n /log log n$ levels of $k = log n$ bit Boolean functions. In order to develop techniques for using communication complexity to prove circuit lower bounds, they suggest an intermediate communication complexity problem which they call the Universal Composition Relation. We give an almost optimal lower bound of $dk - 0 (d
Trvalý link: http://hdl.handle.net/11104/0072210