ECCC-Report TR13-039https://eccc.weizmann.ac.il/report/2013/039Comments and Revisions published for TR13-039en-usMon, 14 Apr 2014 19:02:34 +0300
Revision 2
| On the sum of $L1$ influences |
Arturs Backurs,
Mohammad Bavarian
https://eccc.weizmann.ac.il/report/2013/039#revision2For 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.
We give an application for this theorem for maximal deviation of cut-value of graphs. We also present the connection between the sum of $L1$ influences and quantum query complexity which was the original context where Aaronson and Ambainis encountered this question.Mon, 14 Apr 2014 19:02:34 +0300https://eccc.weizmann.ac.il/report/2013/039#revision2
Revision 1
| On the sum of $L1$ influences |
Arturs Backurs,
Mohammad Bavarian
https://eccc.weizmann.ac.il/report/2013/039#revision1For a real-valued function $p$ over the Boolean hypercube the $L1$-influence of $p$ is defined to be $\sum_{i=1}^n\E_{x\in \{-1,1\}^n}\left[\frac{|p(x)-p(x^i)|}{2} \right]$, where the string $x^i$ 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 $\sum_{i=1}^n\E_{x\in\{-1,1\}^n}\left[\frac{|p(x)-p(x^i)|^2}{4} \right]$. For general $[-1,1]$-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 $[-1,1]$-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. Sat, 24 Aug 2013 16:58:34 +0300https://eccc.weizmann.ac.il/report/2013/039#revision1
Paper TR13-039
| On the sum of $L1$ influences |
Arturs Backurs,
Mohammad Bavarian
https://eccc.weizmann.ac.il/report/2013/039For a multilinear polynomial $p(x_1,...x_n)$, over the reals, the $L1$-influence is defined to be $\sum_{i=1}^n E_x\left[\frac{|p(x)-p(x^i)|}{2} \right]$, where $x^i$ is $x$ with $i$-th bit swapped. If $p$ maps $\{-1,1\}^n$ to $[-1,1]$, we prove that the $L1$-influence of $p$ is upper bounded by a function of its degree (and independent of $n$). This resolves affirmatively a question of Aaronson and Ambainis (Proc. Innovations in Comp. Sc., 2011).
We give an application for this theorem for maximal deviation of cut-value of graphs. We also present the connection between the sum of $L1$ influences and quantum query complexity which was the original context where Aaronson and Ambainis encountered this question.Tue, 19 Mar 2013 00:07:51 +0200https://eccc.weizmann.ac.il/report/2013/039