Number of the records: 1
Communication complexity towards lower bounds on circuit depth
- 1.0175225 - MU-W 20020113 RIV CH eng J - Journal Article
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
R&D Projects: GA AV ČR IAA1019602; GA AV ČR IAA1019901; GA ČR GA201/97/P038; GA ČR GA201/01/1195; GA MŠMT ME 103
Keywords : communication complexity%lower bounds
Subject RIV: BA - General Mathematics
Impact factor: 0.448, year: 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
Permanent Link: http://hdl.handle.net/11104/0072210
File Download Size Commentary Version Access Sgall1.pdf 1 556.3 KB Publisher’s postprint require
Number of the records: 1