Super-logarithmic depth lower bounds via direct sum in communication complexity

10 December 2002

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 299-304
https://doi.org/10.1109/sct.1991.160273

Abstract

The question of whether it is easier to solve two communication problems together rather than separately is related to the complexity of the composition of Boolean functions. Based on this relationship, an approach to separating NC/sup 1 /from P is outlined. Furthermore, it is shown that the approach provides a new proof of the separation of monotone NC/sup 1/ from monotone P.

Keywords

This publication has 11 references indexed in Scilit:

Communication complexity towards lower bounds on circuit depth
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2002
Applications of matrix methods to the theory of lower bounds in computational complexity
Combinatorica, 1990
On the extended direct sum conjecture
Published by Association for Computing Machinery (ACM) ,1989
Monotone circuits for connectivity require super-logarithmic depth
Published by Association for Computing Machinery (ACM) ,1988
Expressing combinatorial optimization problems by linear programs
Published by Association for Computing Machinery (ACM) ,1988
On notions of information transfer in VLSI circuits
Published by Association for Computing Machinery (ACM) ,1983
On the complexity of 2-output Boolean networks
Theoretical Computer Science, 1981
Some complexity questions related to distributive computing(Preliminary Report)
Published by Association for Computing Machinery (ACM) ,1979
On incidence matrices of finite projective and affine spaces
Mathematische Zeitschrift, 1972
Method of determining lower bounds for the complexity of P-schemes
Mathematical Notes, 1971