On the power of circuits with gates of low L1 norms

AbstractWe examine the power of Boolean functions with low L1 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 L1 norms. So, in conjunction with communication complexity, instead of the degree, the L1 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(L21δ) bits of communication, with error-probability of exp(−c°) (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