influence]

2026-09-03

For a Boolean-valued function $𝑓 : {\pm 1}^{𝑛} \to {- 1, 1}$ , the influence of coordinate $𝑖$ on $𝑓$ is the probability that flipping the $𝑖$ th bit changes the output of $𝑓$ ;

{𝐈𝐧𝐟}_{𝑖} [𝑓] = \underset{𝑥 \sim {\pm 1}^{𝑛}}{𝐏𝐫} [𝑓 (𝑥) \neq 𝑓 (𝑥^{\oplus 𝑖})],

where

𝑥^{\oplus 𝑖} = (𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑖 - 1}, - 𝒙_{𝒊}, 𝑥_{𝑖 + 1}, \dots, 𝑥_{𝑛}) .

When flipping the bit changes the output, $𝑓 (𝑥) \neq 𝑓 (𝑥^{\oplus 𝑖})$ , we say coordinate $𝑖$ is pivotal for $𝑥$ .

Using the (discrete) derivative operator, we may generalize the definition of influence to any Boolean function. For $𝑓 : {\pm 1}^{𝑛} \to ℝ$ , the influence of coordinate $𝑖$ on $𝑓$ is defined to be

{𝐈𝐧𝐟}_{𝑖} [𝑓] = \underset{𝑥 \sim {\pm 1}^{𝑛}}{𝐄} [𝐷_{𝑖} {𝑓 (𝑥)}^{2}] = {‖ 𝐷_{𝑖} 𝑓 ‖}_{2}^{2} .

Note. [#]

Note that for $𝑓 : {\pm 1}^{𝑛} \to {- 1, 1}$ ,

𝐷_{𝑖} 𝑓 (𝑥) = {\begin{cases} 0 & coordinate 𝑖 is not pivotal for 𝑥 \\ \pm 1 & coordinate 𝑖 is pivotal for 𝑥 \end{cases} .

This means $𝐷_{𝑖} {𝑓 (𝑥)}^{2}$ is a 0–1 indicator for whether $𝑖$ is pivotal for a given $𝑥$ , and so

{𝐈𝐧𝐟}_{𝑖} [𝑓] = \underset{𝑥 \sim {\pm 1}^{𝑛}}{𝐏𝐫} [𝑓 (𝑥) \neq 𝑓 (𝑥^{\oplus 𝑖})] = \underset{𝑥 \sim {\pm 1}^{𝑛}}{𝐄} 𝐷_{𝑖} {𝑓 (𝑥)}^{2},

the right-hand side of which we simply take to be the definition in the real-valued case.