Maximum influence
The largest single-coordinate influence.
Definition
$\max_{i}\mathrm{Inf}_i(f)$. The quantity in the Aaronson-Ambainis conjecture and in OSSS-type inequalities.
Why this is not a query complexity measure
Taken at face value, $\mathrm{MaxInf}$ is a poor query complexity measure -- it is not a measure of complexity at all. It is a probability, so it lives in $[0,1]$ no matter how large $n$ is. Nothing that counts queries can be bounded by a power of it, and it cannot be polynomially bounded by anything that grows, so every cell it would occupy in the matrix is empty for a reason that has nothing to do with what is known. Worse, it moves the wrong way: harder functions tend to have smaller max influence, and it collapses under bias, since $\mathrm{MaxInf}(\mathrm{OR}_n) = 2^{1-n}$ says nothing about $\mathrm{OR}_n$ being evasive.
What the literature actually uses is the ratio $$\mathrm{osss}(f) \;=\; \frac{\mathrm{Var}(f)}{\mathrm{MaxInf}(f)},$$ the quantity the OSSS inequality bounds by the average depth of a decision tree. Dividing by \(\mathrm{Var}(f)\) cancels the bias, and the ratio is a genuine query count: it is at least $1$, at most $O(n/\log n)$ by KKL, and at most $\mathrm{D}(f)$. That is the entry that appears in the matrix -- see \(\mathrm{osss}(f)\) -- and this page is where its numerator and denominator live. The general recipe is described in Dimensionless quantities and how to normalize them.
Basic facts
- $\mathrm{D}(f)\ge \mathrm{Var}(f)/\mathrm{MaxInf}(f)$ (OSSS). Recorded as the measure \(\mathrm{osss}(f)\).
- $\mathrm{MaxInf}(f)\le\mathrm{Var}(f)$ always, so the ratio above is never below $1$; equality for $\oplus_n$ and for a dictator.
- KKL: $\mathrm{MaxInf}(f)\ge\Omega(\mathrm{Var}(f)\log n/n)$, so the ratio never exceeds $O(n/\log n)$; \(\mathrm{Tribes}_{w,s}\) attains it.
- 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{MaxInf}(f)\). “\(\mathrm{MaxInf}(f)\) in terms of it” is the pair with \(\mathrm{MaxInf}(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 | \(2^{1-n}\) | By symmetry every coordinate has influence $\mathrm{I}(f)/n = 2^{1-n}$. |
| AND total | \(2^{1-n}\) | |
| PARITY total | \(1\) | Every coordinate is always sensitive. |
| MAJORITY total | \(\binom{n-1}{(n-1)/2}2^{1-n} = \Theta(1/\sqrt n)\) | Every coordinate is pivotal exactly when the other $n-1$ split evenly. ODonnell14 |
| Threshold total | \(\binom{n-1}{k-1}2^{1-n}\) putative | The family is transitive, so every coordinate carries the same influence: $\mathrm{Inf}(f)/n$. |
| Symmetric functions (general) total | \(2^{1-n}\sum_{k \,:\, f_k \ne f_{k+1}}\binom{n-1}{k}\) putative | The family is transitive, so every coordinate carries the same influence $\mathrm{I}(f)/n$; divide the \(\mathrm{I}(f)\) line by $n$. |
| EXACT-HALF total | \(\binom{n}{n/2}2^{1-n}\) putative | The family is transitive, so every coordinate carries $\mathrm{I}(f)/n = \Theta(1/\sqrt n)$. |
| ODD-MAX-BIT total | \(\Theta(1)\) putative | The top bit $x_n$ is the most influential and carries essentially all of the influence: it is pivotal exactly when the highest $1$ below it has the opposite parity, probability $\to 2/3$. Influence is concentrated on one coordinate -- the exact opposite of the \(\mathrm{Tribes}_{w,s}\) shape. |
| ADDRESS / multiplexer total | \(1/2\) putative | Attained by any address bit (for $k \ge 1$); each table bit has influence only $2^{-k}$. |
| Binary tree navigation total | \(1/2\) putative | The root is the most influential coordinate: flipping $x_0$ swaps the two subtrees, and the two bits they deliver differ with probability $1/2$ under the uniform input. A node at level $j$ is on the walk only with probability $2^{-j}$, so its influence is $2^{-j-1}$. Note this is $\Theta(1)$ while $\mathrm{MaxInf}$ is $O(\log n/n)$ for \(\mathrm{Tribes}_{w,s}\) -- navigation is as far from the KKL extremal shape as a balanced function can be. |
| TRIBES total | \(\Theta(\log n / n)\) | Extremal for the KKL theorem: no variable has influence more than $O(\log n/n)$. KKL88 |
| AND-OR tree (depth 2) total | \(\Theta(2^{-n})\) putative | The function is transitive (permute the blocks, permute inside each block), so every coordinate has the same influence and $\max_i \mathrm{Inf}_i = \mathrm{I}(f)/N = 2^{1-n}(1-2^{-n})^{n-1}$ exactly, from the \(\mathrm{I}(f)\) entry. |
| NAND tree (balanced AND-OR formula) total | \(2^{-\Theta(\sqrt N)}\) putative | The tree automorphisms act transitively on the leaves, so every coordinate has influence $\mathrm{I}(f)/N$; dividing the doubly exponentially small $\mathrm{I}(f) = 2^{-\Theta(\sqrt N)}$ of the \(\mathrm{I}(f)\) entry by $N$ does not change the exponent. |
| Recursive MAJORITY-of-3 total | \(2^{-d} = N^{-0.6309}\) putative | Recursive majority is transitive, so every coordinate has the same influence $\mathrm{I}(f)/N = (3/2)^d/3^d = 2^{-d}$. Note this is exactly $1/\mathrm{s}$: the maximum influence is the reciprocal of the sensitivity. |
| Kushilevitz's function (iterated) total | \((3/8)^k = N^{-0.5474}\) putative | The automorphism group of the base is $\mathrm{PSL}(2,5)$, transitive on the six coordinates, so $K^{\circ k}$ is transitive and every coordinate has influence $\mathrm{I}(f)/N = (9/4)^k/6^k$. Maximum influence therefore decays even though $\mathrm{s} = N$: the fully sensitive inputs form a vanishing fraction of the cube. |
| Rubinstein's function total | \(\Theta(n2^{-n})\) putative | The automorphism group -- permute the blocks, permute the $n/2$ pairs inside a block, swap the two coordinates of a pair -- is transitive on all $N$ coordinates, so every coordinate carries influence $\mathrm{I}(f)/N = n\,2^{-n}(1-p)^{n-1}$ exactly, from the \(\mathrm{I}(f)\) entry. |
| Ambainis-Sun function total | \(\Theta(k\,2^{-3k})\) putative | The $3k+2$ blocks are interchangeable and the gadget is invariant under the rotation $y_i \mapsto y_{i+2}$, whose two orbits (odd and even positions) carry $k+1$ and $2k+1$ of each firing pattern's $3k+2$ pinned coordinates. So single-coordinate influences vary by a factor $\le 2$ and $\max_i \mathrm{Inf}_i = \Theta(\mathrm{I}(f)/N) = \Theta(k^3 2^{-3k}/k^2)$. Exactly: an even position is pinned by all $2k+1$ patterns, giving $\mathrm{MaxInf} = 2(2k+1)2^{-(3k+2)}(1-p)^{3k+1}$. Well below the Aaronson-Ambainis threshold, as for every function here whose uniform measure is lopsided. |
| AND composed with NOT-EXACT-HALF total | \(2^{-\Theta(\sqrt n)} = 2^{-\Theta(N^{1/4})}\) putative | The function is transitive (permute blocks, permute inside a block, since $\overline{\mathrm{EH}}_n$ is symmetric), so every coordinate has influence exactly $\mathrm{I}(f)/N = 2c(1-c)^{n-1}$ with $c = \binom{n}{n/2}2^{-n}$; dividing by the polynomial factor $N$ does not touch the $e^{-\Theta(\sqrt n)}$ of the \(\mathrm{I}(f)\) entry. |
| Pointer functions total | \(\widetilde O(n^{1/4})\) | Variant $\tilde h_{1,m,m}$: a maximum is at most a sum, so $\mathrm{MaxInf}\le\mathrm{I}=\widetilde O(n^{1/4})$. OSSS gives no useful floor here because the function is very unbalanced under the uniform measure, so $\mathrm{Var}=o(1)$. |
| Cheat-sheet functions total | \(\widetilde O(\sqrt n)\) | A maximum is at most a sum, so $\mathrm{MaxInf}\le\mathrm{I}=\widetilde O(\sqrt n)$. OSSS ($\mathrm{D}\ge\mathrm{Var}/\mathrm{MaxInf}$) gives nothing here because $\mathrm{BKK}_{\mathrm{CS}}$ is essentially never satisfied under the uniform measure. |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde O(n)\) | A maximum is at most a sum, so $\mathrm{MaxInf}\le\mathrm{I}=\widetilde O(n)$; equally $\mathrm{MaxInf}\le\mathrm{s}$. Against $\mathrm{D}=\widetilde\Omega(n^3)$ this is a cubic gap, i.e. the same record the $\mathrm{s}$ column records. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde O(n^{2/3})\) | A maximum is at most a sum, so $\mathrm{MaxInf}\le\mathrm{I}\le\mathrm{s}=\widetilde\Theta(n^{2/3})$. Against $\mathrm{C}=\widetilde\Theta(n^2)$ this is a cubic $\mathrm{C}$-vs-$\mathrm{MaxInf}$ gap. |
| Gilmer-Saks-Srinivasan functions total | \(2^{-\Theta(n)}\) | Squeeze: $\mathrm{MaxInf}\le\mathrm{I}=2^{-\Theta(n)}$, and $\mathrm{MaxInf}\ge\mathrm{I}/n^2$, which changes only the constant in the exponent. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde O(\sqrt n)\) | A maximum is at most a sum, so $\mathrm{MaxInf}\le\mathrm{I}\le\mathrm{s}=\widetilde\Theta(\sqrt n)$. Against $\mathrm{D}=\widetilde\Theta(n)$ this is a quadratic gap. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde O(n^{1/3})\) | A maximum is at most a sum, so $\mathrm{MaxInf}\le\mathrm{I}\le\mathrm{s}=\widetilde\Theta(n^{1/3})$; against $\mathrm{R}=\widetilde\Theta(n^{2/3})$ this is a quadratic gap. |
| Ambainis' exact-quantum function total | \(\Omega((5/9)^d)\) | $\mathrm{NE}^d$ is transitive -- the automorphism group permuting the three children at every node acts transitively on the $3^d$ leaves -- so every coordinate has the same influence and $\mathrm{MaxInf}=\mathrm{I}/3^d=\Omega((5/9)^d)$. Individual influences are exponentially small even though $\mathrm{D}$ is maximal. |
| Surjectivity total | \(2^{-\Theta(n/\log n)}\) | Between $\mathrm{I}(f)/n$ and $\mathrm{I}(f)$, both $2^{-\Theta(n/\log n)}$ since the factor $n$ is swallowed by the exponent. |
| Triangle finding total | \(2^{-\Theta(m^2)}\) | Exactly $\mathrm{I}(f)/\binom m2$: $\mathrm{TRI}_m$ is edge-transitive, so every coordinate has the same influence. The $\binom m2$ is swallowed by the exponent. |
| Inner product mod 2 total | \(1/2\) | Every coordinate has $\mathrm{Inf}_i = \sum_{S \ni i}\hat f(S)^2 = 2^{-n}2^{n-1} = 1/2$; the spectrum is flat, so no coordinate is special. |
| Minsky-Papert one-in-a-box total | \(\Theta(2^{-m^2})\) putative | All $N$ coordinates are equivalent under the symmetry group, so $\mathrm{MaxInf} = \mathrm{I}(f)/N = 2^{1-m^2}(1-2^{-m^2})^{m-1}$. Exponentially small, yet $\mathrm{D} = N$ -- MP is a stress test for OSSS-type bounds, which only give $\mathrm{D} \ge \mathrm{Var}/\mathrm{MaxInf}$ with $\mathrm{Var}$ itself exponentially small. |
| Sink of a tournament total | \(\Theta(2^{-m})\) putative | Relabelling vertices acts transitively on edges, so every coordinate has the same influence and $\mathrm{MaxInf} = \mathrm{I}(f)/N = 2^{3-m}(1-2^{2-m})$. |
| Scorpion graphs total | \(12(m-2)^2\,2^{6-3m}\) putative | The property is invariant under relabelling vertices and the symmetric group is transitive on pairs, so every coordinate has the same influence and $\mathrm{MaxInf} = \mathrm{I}(f)/N = 6m(m-1)(m-2)^2 2^{6-3m}/\binom m2 = \Theta(m^2 2^{-3m})$. |
| Graph connectivity total | \((1+o(1))\,2^{3-m}\) putative | Connectivity is invariant under relabelling vertices and the symmetric group is transitive on pairs, so every coordinate carries the same influence and $\mathrm{MaxInf} = \mathrm{I}(f)/N = (1+o(1))2^{3-m}$. Exact computation gives $\mathrm{I}(f)/N = 0.0608$ at $m = 7$ against $2^{3-m} = 0.0625$. |