Total L1 influence
Sum over i of E_x |D_i f(x)|; differs from total influence for bounded real-valued f.
also written:
sum of L1 influences, Inf^{L1}
Definition
$$\mathrm{I}^1(f) \;=\; \sum_{i=1}^n \mathbb{E}_x\big|\,f(x) - f(x^{\oplus i})\,\big|\ \big/\ 2 .$$ For $f:\{0,1\}^n\to\{-1,1\}$ this equals $\mathrm{I}(f)$. For bounded $p:\{0,1\}^n\to[-1,1]$ (e.g. the acceptance probability of a quantum algorithm) it can be much larger than the $L_2$ version, and bounding it in terms of degree alone was a question of Aaronson-Ambainis motivated by quantum query complexity.
Basic facts
- $\mathrm{I}^1(p) = O(\deg(p)^3)$ for bounded $p$; $O(\deg(p)^2)$ for homogeneous $p$ [Backurs-Bavarian].
- Improved to $O(\deg(p)^2)$ in general and $O(d\log d)$ for homogeneous $p$ [FHKL16], with a matching example for monotone functions.
- A quantum algorithm making $T$ queries has acceptance probability $p$ with $\deg(p)\le 2T$, so these bounds transfer directly to query complexity.
- The Aaronson–Ambainis conjecture is proved: bounded degree-$d$ polynomials have $\max_i\mathrm{Inf}_i(p)\ge c\,\mathrm{Var}(p)^{5/2}/d^6$ [PSI26AaronsonAmbainis, Turturean26]. This gives classical simulation of quantum query algorithms on most uniformly random inputs. Cleaner expositions: [BDST26AA] and [HMP26AA].
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{I}^{1}(f)\). “\(\mathrm{I}^{1}(f)\) in terms of it” is the pair with \(\mathrm{I}^{1}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.
The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(n\,2^{1-n}\) | Boolean-valued, so the $L_1$ and $L_2$ total influences coincide: this is the $\mathrm{I}(f)$ recorded above. |
| AND total | \(n\,2^{1-n}\) | Boolean-valued, so the $L_1$ and $L_2$ total influences coincide: this is the $\mathrm{I}(f)$ recorded above. |
| PARITY total | \(n\) | Boolean-valued, so the $L_1$ and $L_2$ influences agree. |
| MAJORITY total | \(\Theta(\sqrt n)\) | Boolean-valued, so equal to $\mathrm{I}(f)$. |
| Threshold total | \(n\binom{n-1}{k-1}2^{1-n}\) putative | For a Boolean-valued $f$ the $L_1$ and $L_2$ notions of total influence coincide, so this is the recorded $\mathrm{I}(f)$ verbatim. |
| Symmetric functions (general) total | \(n\,2^{1-n}\sum_{k \,:\, f_k \ne f_{k+1}}\binom{n-1}{k}\) | Boolean-valued, so the $L_1$ and $L_2$ total influences coincide: this is the $\mathrm{I}(f)$ recorded above. |
| EXACT-HALF total | \(\Theta(\sqrt n)\) | Boolean-valued, so equal to $\mathrm{I}(f)$. |
| ODD-MAX-BIT total | \(\Theta(1)\) | Boolean-valued, so equal to $\mathrm{I}(f)$. |
| ADDRESS / multiplexer total | \((k+2)/2\) | Boolean-valued, so equal to $\mathrm{I}(f)$. |
| Binary tree navigation total | \((k+1)/2\) | Boolean-valued, so equal to $\mathrm{I}(f)$. |
| TRIBES total | \(\Theta(\log n)\) | Boolean-valued, so equal to $\mathrm{I}(f)$. |
| AND-OR tree (depth 2) total | \(\Theta(n^2 2^{-n})\) putative | For Boolean-valued $f$ the $L_1$ and $L_2$ notions of total influence agree, $\mathrm{I}^1(f) = \mathrm{I}(f)$; they can differ only for bounded real-valued $p$. So this is the \(\mathrm{I}(f)\) entry verbatim. |
| NAND tree (balanced AND-OR formula) total | \(2^{-\Theta(\sqrt N)}\) putative | For Boolean-valued $f$ the $L_1$ and $L_2$ notions of total influence coincide, $\mathrm{I}^1(f) = \mathrm{I}(f)$; see \(\mathrm{I}(f)\). |
| Recursive MAJORITY-of-3 total | \((3/2)^d = N^{0.3691}\) putative | For Boolean-valued $f$ the $L_1$ and $L_2$ notions of total influence coincide, $\mathrm{I}^1(f) = \mathrm{I}(f)$; they differ only for bounded real-valued $p$. See \(\mathrm{I}(f)\). |
| Kushilevitz's function (iterated) total | \((9/4)^k = N^{0.4526}\) putative | For Boolean-valued $f$ the $L_1$ and $L_2$ notions of total influence coincide, $\mathrm{I}^1(f) = \mathrm{I}(f)$; see \(\mathrm{I}(f)\). |
| Rubinstein's function total | \(\Theta(n^3 2^{-n})\) putative | For Boolean-valued $f$ the $L_1$ and $L_2$ notions of total influence coincide, $\mathrm{I}^1(f) = \mathrm{I}(f)$; see \(\mathrm{I}(f)\). |
| Ambainis-Sun function total | \(\Theta(k^3 2^{-3k})\) putative | For a Boolean-valued $f$ the $L_1$ and $L_2$ notions of total influence coincide, $\mathrm{I}^1(f) = \mathrm{I}(f)$ -- the two differ only for bounded real-valued $p$. So this is the \(\mathrm{I}(f)\) entry verbatim. |
| AND composed with NOT-EXACT-HALF total | \(2^{-\Theta(\sqrt n)} = 2^{-\Theta(N^{1/4})}\) putative | For Boolean-valued $f$ the $L_1$ and $L_2$ notions of total influence coincide, $\mathrm{I}^1(f) = \mathrm{I}(f)$; see \(\mathrm{I}(f)\). |
| Pointer functions total | \(\widetilde O(n^{1/4})\) | For a Boolean-valued function the $L_1$ and $L_2$ influences coincide coordinate by coordinate, so $\mathrm{I}^{1}=\mathrm{I}=\widetilde O(n^{1/4})$ on variant $\tilde h_{1,m,m}$. |
| Cheat-sheet functions total | \(\widetilde O(\sqrt n)\) | For a Boolean-valued function the $L_1$ and $L_2$ influences coincide coordinate by coordinate, so $\mathrm{I}^{1}=\mathrm{I}=\widetilde O(\sqrt n)$. |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde O(n)\) | For a Boolean-valued function the $L_1$ and $L_2$ influences coincide coordinate by coordinate, so $\mathrm{I}^{1}=\mathrm{I}=\widetilde O(n)$. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde O(n^{2/3})\) | For a Boolean-valued function the $L_1$ and $L_2$ influences coincide coordinate by coordinate, so $\mathrm{I}^{1}=\mathrm{I}=\widetilde O(n^{2/3})$. |
| Gilmer-Saks-Srinivasan functions total | \(2^{-\Theta(n)}\) | For a Boolean-valued function the $L_1$ and $L_2$ influences coincide coordinate by coordinate, so $\mathrm{I}^{1}=\mathrm{I}=2^{-\Theta(n)}$. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde O(\sqrt n)\) | For a Boolean-valued function the $L_1$ and $L_2$ influences coincide coordinate by coordinate, so $\mathrm{I}^{1}=\mathrm{I}=\widetilde O(\sqrt n)$. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde O(n^{1/3})\) | For a Boolean-valued function the $L_1$ and $L_2$ influences coincide coordinate by coordinate, so $\mathrm{I}^{1}=\mathrm{I}=\widetilde O(n^{1/3})$. |
| Ambainis' exact-quantum function total | \(\Omega((5/3)^d)\) | For a Boolean-valued function the $L_1$ and $L_2$ influences coincide coordinate by coordinate, so $\mathrm{I}^{1}=\mathrm{I}$. |
| Surjectivity total | \(2^{-\Theta(n/\log n)}\) | For Boolean-valued $f$ the $L_1$ and $L_2$ influences coincide (\(\mathrm{I}^{1}(f)\)), so this is the $\mathrm{I}(f)$ row verbatim. |
| Triangle finding total | \(2^{-\Theta(m^2)}\) | For Boolean-valued $f$ the $L_1$ and $L_2$ influences coincide (\(\mathrm{I}^{1}(f)\)), so this is the $\mathrm{I}(f)$ row verbatim. |
| Inner product mod 2 total | \(n/2\) | For a Boolean-valued function the $L_1$ and $L_2$ influences coincide term by term, so $\mathrm{I}^{1}(f) = \mathrm{I}(f) = n/2$. |
| Minsky-Papert one-in-a-box total | \(\Theta(m^3 2^{-m^2})\) | For a Boolean-valued function the $L_1$ and $L_2$ influences coincide term by term, so $\mathrm{I}^{1}(f) = \mathrm{I}(f)$. |
| Sink of a tournament total | \(\Theta(m^2 2^{-m})\) | For a Boolean-valued function the $L_1$ and $L_2$ influences coincide term by term, so $\mathrm{I}^{1}(f) = \mathrm{I}(f)$. |
| Scorpion graphs total | \(\Theta(m^4 2^{-3m})\) | For a Boolean-valued function the $L_1$ and $L_2$ influences coincide term by term, so $\mathrm{I}^{1}(f) = \mathrm{I}(f) = 6m(m-1)(m-2)^2\,2^{6-3m}$; see \(\mathrm{I}(f)\). |
| Graph connectivity total | \(\Theta(m^2 2^{-m})\) | For a Boolean-valued function the $L_1$ and $L_2$ influences coincide term by term, so $\mathrm{I}^{1}(f) = \mathrm{I}(f) = (1+o(1))\binom m2 2^{3-m}$; see \(\mathrm{I}(f)\). |