On the power of circuits with gates of low L1 norms

✍ Scribed by Vince Grolmusz

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 764 KB
• Volume: 188
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(96)00290-3

✦ Synopsis

We examine the power of Boolean functions with low L, norms in several settings. In a large part of the recent literature, the degree of a polynomial which represents a Boolean function in some way was chosen to be the measure of the complexity of the Boolean function. However, some functions with low communicational complexity (AND, OR, PARITY, ID) have high degree, but small LI norms. So, in conjunction with communication complexity, instead of the degree, the LI norm can be an important measure of hardness. We conjecture that the randomized communication complexity of any Boolean function is bounded by the polylogarithm of its L1 norm.

We can prove only a weaker statement: we present a two-party, randomized, common-coin communication protocol for computing functions with O(Lf6) bits of communication, with errorprobability of exp(-cb) (even with large degree or exponential number of terms). Then we present several applications of this theorem for circuit lower bounds (both for bounded-and unbounded depth), and a decision-tree lower bound.