For a real-valued function p over the Boolean hypercube the L1 -influence of p is defined to be ni=1\Ex−11n2p(x)−p(xi) , where the string xi is defined by flipping the i-th bit of x. For Boolean functions the notion of L1 influence will coincide with the usual notion of influences defined as ni=1\Ex−11n4p(x)−p(xi)2 . For general [−11] -valued functions, however, the L1 -influence can be much larger than its L2 counterpart.

In this work, we show that the L1 -influence of a bounded [−11] -valued function p can be controlled in terms of the degree of p's Fourier expansion, resolving affirmatively a question of Aaronson and Ambainis (Proc. Innovations in Comp. Sc., 2011). We give an application of this theorem to the maximal deviation of cut-value of graphs. We also discuss the relationship between the study of bounded functions over the hypercube and the quantum query complexity of partial functions which was the original context in which Aaronson and Ambainis encountered this question