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.