Total influence (L2 influence)
Expected number of sensitive coordinates on a uniformly random input; equals sum_S |S| fhat(S)^2.
also written:
average sensitivity, as(f), Inf(f), sum of L2 influences
Definition
For $f:\{0,1\}^n\to\{-1,1\}$ define $$\mathrm{Inf}_i(f) = \Pr_x[f(x)\ne f(x^{\oplus i})],\qquad \mathrm{I}(f) = \sum_{i=1}^n \mathrm{Inf}_i(f) = \sum_{S}|S|\,\hat f(S)^2 .$$ This is the "$L_2$" notion of influence: $\mathrm{Inf}_i(f) = \|D_i f\|_2^2$ where $D_i f = \tfrac{1}{2}(f(x^{i\to 1}) - f(x^{i\to 0}))$. For Boolean-valued $f$ the $L_1$ and $L_2$ notions coincide up to a factor; they diverge for bounded real-valued $f$ (see \(\mathrm{I}^{1}(f)\)).
Basic facts
- $\mathrm{I}(f)\le \mathrm{s}(f)$ (average $\le$ max) and $\mathrm{I}(f)\le\mathrm{D}(f)$.
- $\mathrm{I}(f)\le\deg(f)$ for Boolean $f$ (each level contributes $|S|\hat f(S)^2$ and $\sum_S\hat f(S)^2=1$).
- OSSS: $\mathrm{Var}(f)\le\sum_i \delta_i(T)\mathrm{Inf}_i(f)$ for any decision tree $T$; hence a balanced $f$ has a variable of influence $\ge \mathrm{Var}(f)/\mathrm{D}(f)$.
- KKL: some $\mathrm{Inf}_i(f)\ge\Omega(\mathrm{Var}(f)\log n/n)$.
- In the noisy model $\mathrm{N}_p$, high total influence forces $\Omega(n\log n)$ queries.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{I}(f)\). “\(\mathrm{I}(f)\) in terms of it” is the pair with \(\mathrm{I}(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 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(n\,2^{1-n}\) | Vanishingly small: OR is very noise-stable. |
| AND total | \(n\,2^{1-n}\) | |
| PARITY total | \(n\) | |
| MAJORITY total | \(\Theta(\sqrt{n})\) | |
| Threshold total | \(n\binom{n-1}{k-1}2^{1-n}\) putative | Coordinate $i$ is pivotal exactly when the other $n-1$ bits have weight $k-1$. At $k = n/2$ this is $\Theta(\sqrt n)$, recovering \(\mathrm{MAJ}_n\); at $k=1$ it is $n2^{1-n}$, recovering \(\mathrm{OR}_n\). |
| Symmetric functions (general) total | \(n\,2^{1-n}\sum_{k \,:\, f_k \ne f_{k+1}}\binom{n-1}{k}\) putative | Exactly. Coordinate $i$ is pivotal at $x$ precisely when the other $n-1$ bits have weight $k$ for some jump $f_k \ne f_{k+1}$, an event of probability $2^{1-n}\binom{n-1}{k}$; sum over jumps and over the $n$ coordinates. Checks: $\vee_n$ (single jump at $k=0$) gives $n2^{1-n}$; $\oplus_n$ (all $n$ jumps) gives $n$; $\mathrm{THR}^n_k$ gives $n\binom{n-1}{k-1}2^{1-n}$; \(\mathrm{EH}_n\) gives $\Theta(\sqrt n)$. Displayed as a formula in the slice pattern rather than in $n$ and $\Gamma$, since $\Gamma$ does not determine it. |
| EXACT-HALF total | \(\Theta(\sqrt n)\) putative | Coordinate $i$ is pivotal exactly when the other $n-1$ bits have weight $n/2$ or $n/2-1$, so $\mathrm{Inf}_i = \binom{n}{n/2}2^{1-n} = \Theta(1/\sqrt n)$ and the total is $\Theta(\sqrt n)$ -- the same order as \(\mathrm{MAJ}_n\), despite $\mathrm{EH}$ being exponentially unbalanced. |
| ODD-MAX-BIT total | \(\Theta(1)\) putative | Coordinate $i$ is pivotal only when every bit above it is $0$, which costs $2^{-(n-i)}$; conditioned on that, flipping $x_i$ moves the maximum to the highest $1$ below $i$, whose index has the opposite parity with probability $\tfrac12+\tfrac18+\tfrac1{32}+\cdots = \tfrac23$. Summing the geometric series, $\mathrm{I}(\mathrm{OMB}_n) \to 4/3$. So $\mathrm{OMB}$ is a balanced function of total influence $O(1)$ and $\mathrm{D} = n$. |
| ADDRESS / multiplexer total | \((k+2)/2\) putative | Flipping an address bit moves the pointer to a uniformly unrelated table entry, flipping the output with probability $1/2$: total $k/2$. Flipping table entry $y_b$ matters exactly when $\mathrm{bin}(a) = b$, probability $2^{-k}$, and there are $2^k$ of them: total $1$. So $\mathrm{Inf} = k/2 + 1$. |
| Binary tree navigation total | \((k+1)/2\) putative | On a uniform input the level-$j$ walk variable is pivotal exactly when the sibling subtree would deliver the opposite bit, which happens with probability $1/2$; the bottom variable is always pivotal. So $\mathrm{I} = 1 + (k-1)/2$ while the function has $2^k-1$ variables -- influence logarithmic in the input length, and a clean instance of $\mathrm{I} \le \mathrm{D}$ being tight up to a factor of $2$. |
| TRIBES total | \(\Theta(\log n)\) | |
| AND-OR tree (depth 2) total | \(\Theta(n^2 2^{-n})\) putative | Exactly $\mathrm{I}(f) = n^2\,2^{1-n}(1-2^{-n})^{n-1}$: bit $i$ of block $j$ is pivotal iff the rest of its block is $0$ and every other block is nonzero. The AND-OR tree is wildly unbalanced under the uniform measure -- $\Pr[f=1] = (1-2^{-n})^n \to 1$ -- so its total influence tends to $0$ even though $\mathrm{D} = N$. (Confirmed against the exact Fourier expansion for $n \le 4$.) |
| NAND tree (balanced AND-OR formula) total | \(2^{-\Theta(\sqrt N)}\) putative | Writing $p_d = \Pr[f_d = 1]$ one has $p_d = 1 - p_{d-1}^2$ and $\mathrm{I}(f_d) = \prod_{j<d} 2p_j$. The map $p \mapsto 1-p^2$ has its fixed point $(\sqrt5-1)/2$ unstable, and from $p_0 = \tfrac12$ the orbit is attracted to the $2$-cycle $\{0,1\}$ with $p_{2k+2}\approx 2p_{2k}^2$, i.e. doubly exponentially. So the balanced NAND tree is, under the uniform measure, an almost constant function whose total influence decays like $2^{-\Theta(2^{d/2})}$. Numerically $\log_2 \mathrm{I}(f_d) \approx -0.145\cdot 2^{d/2}$ along even $d$. A reminder that the uniform measure is the wrong one for this function: the Saks-Wigderson product distribution is the right one. |
| Recursive MAJORITY-of-3 total | \((3/2)^d = N^{0.3691}\) putative | $\mathrm{MAJ}_3$ is balanced, so on a uniform input the three subtree values are uniform and independent and total influence multiplies: $\mathrm{I}(f\circ g^n) = \mathrm{I}(f)\mathrm{I}(g)$. Each coordinate of $\mathrm{MAJ}_3$ is pivotal exactly when the other two disagree, so $\mathrm{I}(\mathrm{MAJ}_3)=\tfrac32$. |
| Kushilevitz's function (iterated) total | \((9/4)^k = N^{0.4526}\) putative | The base is balanced, so under a uniform input the block values of $K\circ g^6$ are uniform and independent and total influence is exactly multiplicative: $\mathrm{I}(f\circ g^n) = \mathrm{I}(f)\,\mathrm{I}(g)$. From the Fourier expansion above, $\mathrm{I}(K) = 1\cdot 6\cdot(\tfrac14)^2 + 3\cdot 10\cdot(\tfrac14)^2 = \tfrac94$. So influence is only $N^{0.45}$ while $\mathrm{s} = N$: sensitivity here is concentrated on a vanishing fraction of the cube. |
| Rubinstein's function total | \(\Theta(n^3 2^{-n})\) putative | Exactly $\mathrm{I}(f) = n^3 2^{-n}(1-p)^{n-1}$ with $p = \tfrac n2 2^{-n} = \Pr[g = 1]$: the gadget has exactly $n^2$ sensitive edges out of $n2^{n}$, so $\mathrm{I}(g) = n^2 2^{-n}$, and a block's influence survives only if the other $n-1$ blocks stay silent. Under the uniform measure Rubinstein's function is almost constant, so its total influence is exponentially small even though $\mathrm{bs} = N/2$. (Checked against the full Fourier expansion at $n = 4$.) |
| Ambainis-Sun function total | \(\Theta(k^3 2^{-3k})\) putative | Exactly $\mathrm{I}(f) = (3k+2)\,\mathrm{I}(g)(1-p)^{3k+1}$ with $p = (2k+1)2^{-(3k+2)}$ and $\mathrm{I}(g) = 2(3k+2)(2k+1)2^{-(3k+2)}$: a $1$-input of $g$ has exactly $3k+2$ sensitive bits and there are $(2k+1)2^{k}$ of them. Both formulas checked by exhaustive Fourier computation for $k \le 3$. Since $p(3k+2) \to 0$, the correction factor is $1-o(1)$ and $\mathrm{I}(f) = 2(3k+2)^2(2k+1)2^{-(3k+2)}(1-o(1)) = 2^{-\Theta(\sqrt N)}$. |
| AND composed with NOT-EXACT-HALF total | \(2^{-\Theta(\sqrt n)} = 2^{-\Theta(N^{1/4})}\) putative | Exactly $\mathrm{I}(f) = 2n^2c\,(1-c)^{n-1}$ with $c = \binom{n}{n/2}2^{-n} = \Theta(n^{-1/2}) = \Pr[\overline{\mathrm{EH}}_n = 0]$: a bit of block $j$ is pivotal iff the other $n-1$ bits of its block are balanced to within one, which has probability $2c$, and every other block must be $1$. Since $cn = \Theta(\sqrt n)$, the factor $(1-c)^{n-1} = e^{-\Theta(\sqrt n)}$ swamps the polynomial $2n^2c = \Theta(n^{3/2})$. (Verified against the full Fourier expansion at $n = 4$: $\mathrm{I} = 2.9296875$.) |
| Pointer functions total | \(\widetilde O(n^{1/4})\) | Variant $\tilde h_{1,m,m}$: $\mathrm{I}(f)=O(\widetilde{\deg}(f))$ [Shi00] applied to $\widetilde{\deg}=\widetilde O(n^{1/4})$. Against $\mathrm{D}=\widetilde\Omega(n)$, valid on the same variant, this is a fourth-power $\mathrm{D}$-vs-$\mathrm{I}$ gap for a function whose sensitivity is still polynomially large. Shi00 |
| Cheat-sheet functions total | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{I}(f)\le\mathrm{s}(f)=\widetilde O(\sqrt n)$ (equally, $\mathrm{I}\le\deg$). Against $\mathrm{Q}=\widetilde\Theta(n)$ this gives $\mathrm{Q}=\widetilde\Omega(\mathrm{I}^2)$ for a total function. |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde O(n)\) | Squeeze: $\mathrm{I}(f)=\mathbf{E}_x[\mathrm{s}(f,x)]\le\mathrm{s}(f)=\widetilde O(n)$. Combined with $\mathrm{D}=\widetilde\Omega(n^3)$ this is a cubic $\mathrm{D}$-vs-$\mathrm{I}$ gap that tracks the record $\mathrm{D}$-vs-$\mathrm{s}$ gap exactly. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde O(n^{2/3})\) | Squeeze: $\mathrm{I}(f)\le\mathrm{s}(f)=\widetilde\Theta(n^{2/3})$. Against $\mathrm{C}=\widetilde\Theta(n^2)$ this makes the family a cubic $\mathrm{C}$-vs-$\mathrm{I}$ example, mirroring its record $\mathrm{C}$-vs-$\mathrm{s}$ gap. |
| Gilmer-Saks-Srinivasan functions total | \(2^{-\Theta(n)}\) putative | Direct computation. The inner $g_n$ is the indicator of $2^{n/50}$ isolated points, so $\mathrm{I}(g_n)=2^{-n}\sum_x \mathrm{s}(g_n,x)=2^{-n}\cdot 2n\cdot 2^{n/50}=2n\,2^{-49n/50}$. In $f=\mathrm{OR}_n\circ g_n$ a bit is influential only if it flips its own copy and the other $n-1$ copies all evaluate to $0$, an event of probability $1-o(1)$, so $\mathrm{I}(f)=(1\pm o(1))\,n\,\mathrm{I}(g_n)=2^{-\Theta(n)}$. Total influence is therefore exponentially small while $\mathrm{D}=\Theta(n^2)$ -- a reminder that no polynomial bound on $\mathrm{D}$ in terms of $\mathrm{I}$ can exist. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{I}(f)\le\mathrm{s}(f)=\widetilde\Theta(\sqrt n)$ (equally, $\mathrm{I}\le\deg$). Against $\mathrm{D}=\widetilde\Theta(n)$ this gives a quadratic $\mathrm{D}$-vs-$\mathrm{I}$ gap. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde O(n^{1/3})\) | Squeeze: $\mathrm{I}(f)\le\mathrm{s}(f)=\widetilde\Theta(n^{1/3})$ (equally, $\mathrm{I}\le\deg$). Against $\mathrm{R}=\widetilde\Theta(n^{2/3})$ this is a quadratic $\mathrm{R}$-vs-$\mathrm{I}$ gap. |
| Ambainis' exact-quantum function total | \(\Omega((5/3)^d)\) putative | Exact recursion. Coordinate $i$ of the top $\mathrm{NE}$ is sensitive at $y$ iff the other two children agree, an event independent of child $i$; hence $\mathrm{I}(\mathrm{NE}^d)=3\big(p_{d-1}^2+(1-p_{d-1})^2\big)\,\mathrm{I}(\mathrm{NE}^{d-1})$ with $p_d=\Pr[\mathrm{NE}^d=1]=3p_{d-1}(1-p_{d-1})$ and $\mathrm{I}(\mathrm{NE}^0)=1$. Since $p_d\to 2/3$, the factor tends to $3(4/9+1/9)=5/3$; the convergence is only neutral ($g'(2/3)=-1$), so the product picks up a $d^{o(1)}$ correction and only the lower bound $\mathrm{I}=\Omega((5/3)^d)$ is recorded (numerically the ratio $\mathrm{I}_d/(5/3)^d$ stays in $[0.9,1.2]$ out to $d=200$). Note $(5/3)^d=n^{0.4650}$, well below $\mathrm{s}=n$: the function is maximally sensitive at one input but only polynomially sensitive on average. |
| Surjectivity total | \(2^{-\Theta(n/\log n)}\) putative | Exponentially small, because surjectivity is exponentially rare: $N = 2R$ uniform draws into $R$ bins cover them all with probability $p = e^{-\Theta(R)} = 2^{-\Theta(n/\log n)}$, and the uniform measure on $\{0,1\}^n$ is the uniform measure on lists since $R$ is a power of two. Upper: $\mathrm{Inf}_i \le \Pr[f(x)=1]+\Pr[f(x^{\oplus i})=1] = 2p$, so $\mathrm{I}(f) \le 2np = 2^{-\Theta(n/\log n)}$. Lower: Poincare, $\mathrm{I}(f) \ge \mathrm{Var}(f) = 4p(1-p) = \Theta(p)$. So $\mathrm{I} = \Theta(1)$ fails badly while $\mathrm{D} = n$: total influence says nothing about query complexity for biased functions. |
| Triangle finding total | \(2^{-\Theta(m^2)}\) putative | Exponentially small, because a uniform graph has a triangle with probability $1 - 2^{-\Theta(m^2)}$: the number of triangle-free graphs on $m$ vertices is $2^{(1/4+o(1))m^2}$ against $2^{\binom m2}$ in all. Write $q = \Pr[\mathrm{TRI}_m = 0]$. Upper: an edge is pivotal only if deleting it destroys every triangle, in particular only on graphs whose $\mathrm{TRI}$ value is $0$ after the flip, so $\mathrm{Inf}_e \le 2q$ and $\mathrm{I} \le 2\binom m2 q = 2^{-\Theta(m^2)}$. Lower: Poincare, $\mathrm{I} \ge \mathrm{Var} = \Theta(q)$. So on the uniform measure the triangle problem is invisible, which is why every lower bound for it argues against a planted distribution instead. |
| Inner product mod 2 total | \(n/2\) | $\mathrm{I}(f) = \sum_S |S|\hat f(S)^2 = 2^{-n}\sum_{S}|S| = 2^{-n}\cdot n2^{n-1}$. |
| Minsky-Papert one-in-a-box total | \(\Theta(m^3/2^{m^2})\) putative | A bit of box $j$ is sensitive exactly when the other $m^2-1$ bits of its box are $0$ and every other box contains a $1$, so $\mathrm{I}(f) = m\cdot m^2\cdot 2^{-(m^2-1)}(1-2^{-m^2})^{m-1}$. Almost all of the cube is a $0$-input with two or more empty boxes, where nothing is sensitive at all, so the average sensitivity is exponentially far below $\mathrm{s} = m^2$. Checked exactly at box size $4$ with $2$ boxes. |
| Sink of a tournament total | \(\Theta(m^2 2^{-m})\) putative | Exactly $\binom m2 2^{3-m}\big(1 - 2^{2-m}\big)$. Every sensitive hypercube edge has a $1$-endpoint, so $\mathrm{I}(f) = 2^{1-N}\sum_{f(x)=1}\mathrm{s}(x)$. At a $1$-input the sink $v$ is unique and only its own $m-1$ edges can matter; flipping $uv$ kills $v$ and creates a sink only if $u$ already loses to all of $V\setminus\{u,v\}$, and at most one such $u$ exists. Counting: $m\,2^{\binom{m-1}2}$ inputs have a sink and $m(m-1)2^{\binom{m-2}2}$ of them also have such a $u$. Verified exhaustively for $m \le 7$. So average sensitivity is exponentially small, while $\mathrm{s} = m-1$. |
| Scorpion graphs total | \(\Theta(m^4 2^{-3m}) = 2^{-\Theta(\sqrt N)}\) putative | Exactly $\mathrm{I} = 6m(m-1)(m-2)^2\,2^{6-3m}$ for $m \ge 5$. Every scorpion has sensitivity exactly $3m-6$ (the proof of $\mathrm{s}^1$ applies to every scorpion, not just the one with independent feet), so the sensitivity graph has $m(m-1)(m-2)2^{\binom{m-3}2}(3m-6)$ edges; divide by $2^{\binom m2}$ and double. Verified exactly against exhaustive computation for $5 \le m \le 7$. The scorpion property is thus vanishingly rare and vanishingly influential, which is why $\mathrm{R}$ cannot be beaten below $\Theta(m)$ by sampling. |
| Graph connectivity total | \(\Theta(m^2 2^{-m})\) putative | A uniformly random graph is connected with probability $1-\Theta(m2^{-m})$, and a pair $uv$ is sensitive only in the two degenerate ways: $uv$ is a bridge with one endpoint pendant, or one endpoint is isolated and $uv$ would attach it. Each has probability $2^{2-m}$, so $\mathrm{I}(f) = (1+o(1))\binom m2 2^{3-m}$. Confirmed numerically: the ratio to $\binom m2 2^{3-m}$ is $0.50,\,0.63,\,0.78,\,0.91,\,0.97$ at $m = 3,\dots,7$. Average sensitivity is thus exponentially below $\mathrm{s} = \lfloor m^2/4\rfloor$ -- connectivity is a wildly unbalanced function. |