Q The Query Complexity Zoo
\(\mathrm{I}^{1}(f)\)

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.

Other measure \(\mathrm{I}^{1}(f)\) in terms of it It in terms of \(\mathrm{I}^{1}(f)\)
\(\mathrm{I}(f)\) Total influence (L2 influence) total1,? derived open pair → total1,? derived open pair →
\(\mathrm{MaxInf}(f)\) Maximum influence total∞ derived open pair → —derived open pair →
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree total1,4 derived open pair → total∞ derived open pair →
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total1,4 derived open pair → total∞ derived open pair →

The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.

Known values

FunctionValueNotes
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)\).