Super-logarithmic depth lower bounds via the direct sum in communication complexity
M Karchmer, R Raz, A Wigderson - Computational Complexity, 1995 - Springer
M Karchmer, R Raz, A Wigderson
Computational Complexity, 1995•SpringerIs it easier to solve two communication problems together than separately? This question is
related to the complexity of the composition of boolean functions. Based on this relationship,
an approach to separating NC 1 from P is outlined. Furthermore, it is shown that the
approach provides a new proof of the separation of monotone NC 1 from monotone P.
related to the complexity of the composition of boolean functions. Based on this relationship,
an approach to separating NC 1 from P is outlined. Furthermore, it is shown that the
approach provides a new proof of the separation of monotone NC 1 from monotone P.
Abstract
Is it easier to solve two communication problems together than separately? This question is related to the complexity of the composition of boolean functions. Based on this relationship, an approach to separatingNC 1 fromP is outlined. Furthermore, it is shown that the approach provides a new proof of the separation of monotoneNC 1 from monotoneP.
Springer