SUPER-LOGARITHMIC DEPTH LOWER BOUNDS VIA THE DIRECT SUM IN COMMUNICATION COMPLEXITY

Authors
KARCHMER M RAZ R WIGDERSON A
Citation
M. Karchmer et al., SUPER-LOGARITHMIC DEPTH LOWER BOUNDS VIA THE DIRECT SUM IN COMMUNICATION COMPLEXITY, Computational complexity, 5(3-4), 1995, pp. 191-204
Citations number
22
Categorie Soggetti
Mathematics, General","Computer Sciences",Mathematics,"Computer Science Theory & Methods
Journal title
Computational complexity → ACNP
ISSN journal
10163328
Volume
5
Issue
3-4
Year of publication
1995
Pages
191 - 204
Database
ISI
SICI code
1016-3328(1995)5:3-4<191:SDLBVT>2.0.ZU;2-T
Abstract
Is it easier to solve two communication problems together than separat ely? This question is related to the complexity of the composition of boolean functions. Based on this relationship, an approach to separati ng NC1 from P is outlined. Furthermore, it is shown that the approach provides a new proof of the separation of monotone NC1 from monotone P .