On the influences of low degree bounded functions

The influence of the $k$-th coordinate on a Boolean function $f$ measures how likely is $f(x)$ to change when the $k$-th coordinate of $x$ is flipped while the other coordinates remain unchanged. Influences were studied extensively in the last 25 years, and they have  applications to theoretical computer science, mathematical physics, and various other fields.

In this talk we consider bounded functions on the discrete cube, i.e., $f:{-1,1}^n -> [-1,1]$. In this case, one of the natural definitions of influence is the $L_1$ influence, defined as $I_k(f)=E[ |f(x)-f(x+e_k)| ]$. We study the following question, raised by Aaronson and Ambainis in the context of quantum computation. Assume that $f$ has degree $d$ as a multilinear polynomial. Is it true that  the sum of $L_1$ influences of $f$ can be bounded as a function of $d$ (independent of $n$)?

In a recent paper, Backurs and Bavarian showed an upper bound of $O(d^3)$ for general  functions and $O(d^2)$ for homogeneous functions. We improve the upper bounds to $d^2$ for  general functions and $O(d \log d)$ for homogeneous functions. Furthermore, we present an  upper bound of $d / 2\pi$ for monotone functions and show that it is tight. Our proofs use tools  from approximation theory, such as Bernstein-Markov type inequalities.

Joint work with Yuval Filmus (IAS), Hamed Hatami (McGill), and Nathan Keller.