Lower Bounds on Communication Complexity
Stasys P. Jukna · 1987
A notion of communication is used to formally measure the degree to which a Boolean function is global. An explicit combinatorial lower bound for this complexity measure is presented. In particular, this leads to an exp(( p n)) lower bound on the complexity of depth-restricted contact schemes computing some natural Boolean functions in NP.