__
TR95-046 | 4th August 1995 00:00
__

#### On the Power of Circuits with Gates of Low L_1 Norms

**Abstract:**
We examine the power of Boolean functions with low L_1 norms in several

settings. In 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 L_1 norms. So, in conjunction with

communication complexity, instead of the degree, the L_1 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 L_1 norm. We can

prove only a weaker statement: we present a two-party, randomized, common-coin

communication protocol for computing functions with O(L^2_1\delta) bits of

communication, with error-probability of exp(-c\delta), (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.