  For a function $f$ over the discrete cube, the total $L_1$ influence of $f$
is defined as $\sum_{i=1}^n \|\partial_i f\|_1$, where $\partial_i f$ denotes
the discrete derivative of $f$ in the direction $i$. In this work, we show that
the total $L_1$ influence of a $[-1,1]$-valued function $f$ can be upper
bounded by a polynomial in the degree of $f$, resolving affirmatively an open
problem of Aaronson and Ambainis (ITCS 2011). The main challenge here is that
the $L_1$ influences do not admit an easy Fourier analytic representation. In
our proof, we overcome this problem by introducing a new analytic quantity
$\mathcal I_p(f)$, relating this new quantity to the total $L_1$ influence of
$f$. This new quantity, which roughly corresponds to an average of the total
$L_1$ influences of some ensemble of functions related to $f$, has the benefit
of being much easier to analyze, allowing us to resolve the problem of Aaronson
and Ambainis. We also give an application of the theorem to graph theory, and
discuss the connection between the study of bounded functions over the cube and
the quantum query complexity of partial functions where Aaronson and Ambainis
encountered this question.
