On the Sum of L1 Influences
Artūrs Bačkursa b c, Mohammad Bavariana b c
- aMassachusetts Institute of Technology, Cambridge, MA, USA
- bMassachusetts Institute of Technology
- cCambridge MA USA
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
For a function f over the discrete cube, the total L1 influence of f is defined as the sum of the L1 norm of the discrete derivatives of f in all n directions. In this work, we show that in the case of bounded functions this quantity can be upper bounded by a polynomial in the degree of f (independently of dimension n), resolving affirmatively an open problem of Aaronson and Ambainis (ITCS 2011). We also give an application of our 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.
TL;DRIt is shown that in the case of bounded functions this quantity can be upper bounded by a polynomial in the degree of f (independently of dimension n), resolving affirmatively an open problem of Aaronson and Ambainis (ITCS 2011). (Semantic Scholar)