On the sum of the L₁ influences of bounded functions

Publication date 15 September 2016

Abstract: Let

f c o l o n {- 1, 1}^{n} o [- 1, 1]

have degree

d

as a multilinear polynomial. It is well-known that the total influence of

f

is at most

d

. Aaronson and Ambainis asked whether the total

L_{1}

influence of

f

can also be bounded as a function of

d

. Bav{c}kurs and Bavarian answered this question in the affirmative, providing a bound of

O (d^{3})

for general functions and

O (d^{2})

for homogeneous functions. We improve on their results by providing a bound of

d^{2}

for general functions and

O (d l o g d)

for homogeneous functions. In addition, we prove a bound of

d / (2 p i) + o (d)

for monotone functions, and provide a matching example.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: On the sum of the \(L_1\) influences of bounded functions