OSSS number
Var(f)/MaxInf(f): the query lower bound the OSSS inequality reads off the influences.
also written:
Var/MaxInf, normalized maximum influence, OSSS bound, \(\mathrm{Var}(f)/\mathrm{MaxInf}(f)\)
Definition
$$\mathrm{osss}(f) \;=\; \frac{\mathrm{Var}(f)}{\mathrm{MaxInf}(f)} \;=\; \frac{\mathrm{Var}(f)}{\max_i \mathrm{Inf}_i(f)} .$$ This is \(\mathrm{MaxInf}(f)\) put on the query scale by dividing out the bias (see Dimensionless quantities and how to normalize them). The OSSS inequality [OSSS05] states that for every decision tree $T$ computing $f$, $$\mathrm{Var}(f)\;\le\;\sum_i \delta_i(T)\,\mathrm{Inf}_i(f),$$ where $\delta_i(T) = \Pr_x[T \text{ reads } x_i]$. Bounding each $\mathrm{Inf}_i$ by $\mathrm{MaxInf}$ and summing gives $\mathrm{osss}(f) \le \sum_i\delta_i(T) = \mathbb{E}[\#\text{queries}]$, so $\mathrm{osss}$ is a lower bound on the average depth of a tree for $f$, not merely on $\mathrm{D}(f)$.
Basic facts
- $1\le\mathrm{osss}(f)$, since $\mathrm{MaxInf}\le\mathrm{Var}$ (a single coordinate cannot carry more than all of the variance). Equality for $\oplus_n$ and for a dictator.
- $\mathrm{osss}(f) = O(n/\log n)$ by KKL, and \(\mathrm{Tribes}_{w,s}\) attains it: no measure of this shape can ever be within a $\log$ of $n$.
- $\mathrm{osss}(f)\le \bar{\mathrm{R}}_0(f) = \mathrm{R}_0(f)\le\mathrm{D}(f)$: OSSS applies to each tree in the support of a Las Vegas algorithm, and averaging preserves the inequality.
- It is a weak lower bound and honest about it: $\mathrm{osss}(\oplus_n) = 1$, $\mathrm{osss}(\mathrm{OR}_n) = \Theta(1)$, $\mathrm{osss}(\mathrm{MAJ}_n) = \Theta(\sqrt n)$, all against $\mathrm{D} = n$. It is tight for \(\mathrm{SCORP}_m\) and for \(\mathrm{Tribes}_{w,s}\) up to the $\log$.
- The famous corollary of OSSS is for monotone transitive $f$: there $\mathrm{Inf}_i = \hat f(\{i\})$ is the same for every $i$, so $\mathrm{MaxInf} = \mathrm{I}(f)/n \le \Delta(f)/n$ and $\mathrm{Var}\le\Delta(f)^2/n$, giving $\Delta(f) = \Omega(\sqrt{n\,\mathrm{Var}})$ -- a lower bound on average depth from symmetry alone.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{osss}(f)\). “\(\mathrm{osss}(f)\) in terms of it” is the pair with \(\mathrm{osss}(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-2^{-n})\) putative | Exactly $4p(1-p)/(2p) = 2(1-p)$, since $\mathrm{MaxInf} = 2p$. The OSSS bound certifies two queries against $\mathrm{D} = n$: dividing out the bias fixes the units but cannot make a one-coordinate statistic see a global obstruction. See Dimensionless quantities and how to normalize them. |
| AND total | \(2(1-2^{-n})\) putative | Identical to \(\mathrm{OR}_n\): complementing the input and the output changes neither $\mathrm{Var}$ nor $\mathrm{MaxInf}$. |
| PARITY total | \(1\) putative | The smallest value the measure can take: $\mathrm{MaxInf} = \mathrm{Var} = 1$, because a single coordinate is pivotal on every input. OSSS therefore certifies one query against $\mathrm{D} = n$, the extreme demonstration that the bound is only as good as the spread of the influences. |
| MAJORITY total | \(2^{n-1}/\binom{n-1}{(n-1)/2} = \sqrt{\pi n/2}\,(1+o(1))\) putative | $\mathrm{Var} = 1$ over $\mathrm{MaxInf} = \binom{n-1}{(n-1)/2}2^{1-n}$. The largest value OSSS attains among the standard symmetric functions, and still only $\Theta(\sqrt n)$ against $\mathrm{D} = n$. |
| EXACT-HALF total | \(2(1-M) = 2-\Theta(1/\sqrt n)\) putative | $\mathrm{MaxInf} = 2M$ exactly, so the ratio is $4M(1-M)/(2M) = 2(1-M)$. Normalizing rescues nothing here: both numerator and denominator are $\Theta(1/\sqrt n)$, and the bound certifies two queries against $\mathrm{D} = n$. |
| ODD-MAX-BIT total | \(4/3 + o(1)\) putative | $\mathrm{Var} \to 8/9$ over $\mathrm{MaxInf} \to 2/3$. Constant against $\mathrm{D} = n$, because a single coordinate -- the top bit -- carries almost all of the influence. The \(\mathrm{Tribes}_{w,s}\)-shaped functions are where OSSS is strong; this is the opposite extreme. |
| ADDRESS / multiplexer total | \(2\) putative | $\mathrm{Var} = 1$ over $\mathrm{MaxInf} = 1/2$ (the addressed bit is pivotal with probability $1/2$). Against $\mathrm{D} = k+1$ this is only tight for $k = O(1)$. |
| Binary tree navigation total | \(2\) putative | As for \(\mathrm{ADDR}_k\): $\mathrm{Var} = 1$ and $\mathrm{MaxInf} = 1/2$. |
| TRIBES total | \(\Theta(n/\log n)\) putative | $\mathrm{Var} = 1-o(1)$ over $\mathrm{MaxInf} = \Theta(\log n/n)$. The extremal case: KKL says no function beats $O(n/\log n)$, and TRIBES attains it, so this is the largest lower bound OSSS can ever produce. It coincides with $\mathrm{s} = \mathrm{bs} = \Theta(n/\log n)$ here, and falls a $\log$ short of $\mathrm{D} = n$. |
| AND-OR tree (depth 2) total | \(\Theta(n) = \Theta(\sqrt N)\) putative | $\Theta(n2^{-n})$ over $\Theta(2^{-n})$. Tight against $\mathrm{s} = n$, and quadratically short of $\mathrm{D} = N = n^2$ -- the two exponentially small Fourier quantities cancel and leave exactly the sensitivity. |
| NAND tree (balanced AND-OR formula) total | \(\Theta(\sqrt N) = \Theta(2^{d/2})\) putative | Both $\mathrm{Var}$ and $\mathrm{MaxInf}$ are $2^{-\Theta(\sqrt N)}$, but the ratio is clean. Write $\varepsilon_d = \min\{p_d,1-p_d\}$, so $\mathrm{Var} = 4\varepsilon_d(1-\varepsilon_d)$ and $\varepsilon_{d+2} = (2+o(1))\varepsilon_d^2$, while $\mathrm{MaxInf}(f_d) = \prod_{j<d}p_j$ picks up exactly one new small factor $\varepsilon_d$ every two levels. Hence $\mathrm{osss}(f_{d+2})/\mathrm{osss}(f_d)\to 2$. Numerically $\mathrm{osss} = 2.6,\,6.8,\,17.3,\,41,\,90,\,184$ at $d = 2,4,\dots,12$. Well below $\mathrm{R}_0 = \Theta(N^{0.753})$. |
| Recursive MAJORITY-of-3 total | \(2^d = N^{0.6309}\) putative | $\mathrm{Var} = 1$ over $\mathrm{MaxInf} = 2^{-d}$. Exactly $\mathrm{s}(f) = 2^d$: for a transitive balanced function $\mathrm{osss} = N/\mathrm{I}$, and here that is the sensitivity on the nose. Still short of $\mathrm{R}_0 = \Omega(2.59^d)$. |
| Kushilevitz's function (iterated) total | \((8/3)^k = N^{0.5474}\) putative | $\mathrm{Var} = 1$ over $\mathrm{MaxInf} = (3/8)^k$. The function is transitive, so this is $N/\mathrm{I}(f) = 6^k/(9/4)^k$. Far short of $\mathrm{D} = \mathrm{R}_0 = N$, and short even of $\mathrm{s} = N$. |
| Rubinstein's function total | \(\Theta(n) = \Theta(\sqrt N)\) putative | $\Theta(n^2 2^{-n})$ over $\Theta(n2^{-n})$. Tight against $\mathrm{s} = n$ and quadratically short of $\mathrm{D} = N$. Structurally identical to \(\mathrm{AND}_n \circ \mathrm{OR}_n\) and to \(f_{\mathrm{AS}}\): an OR of exponentially rare gadgets always lands on the sensitivity. |
| Ambainis-Sun function total | \(\Theta(k) = \Theta(\sqrt N)\) putative | $\Theta(k^2 2^{-3k})$ over $\mathrm{MaxInf} = \Theta(k2^{-3k})$. Equal to $\mathrm{s} = 3k+2$ up to constants, and quadratically short of $\mathrm{D} = \Theta(N)$ -- the same picture as \(f_{\mathrm{Rub}}\), whose gadget structure this shares. |
| Ambainis' exact-quantum function total | \(O((9/5)^d) = O(N^{0.5350})\) putative | $\mathrm{Var} = \Theta(1)$ over $\mathrm{MaxInf} = \Omega((5/9)^d)$. Only an upper bound, because the recorded influence is only a lower bound; the matching direction would need the constant in the influence recursion. |
| Inner product mod 2 total | \(2(1-2^{-n})\) putative | $\mathrm{MaxInf} = 1/2$ on a flat spectrum, so the ratio is $2\mathrm{Var}$. Two queries against $\mathrm{D} = n$: OSSS is blind to a function all of whose coordinates look alike. |
| Minsky-Papert one-in-a-box total | \(\Theta(m) = \Theta(N^{1/3})\) putative | $\Theta(m2^{-m^2})$ over $\Theta(2^{-m^2})$: the two exponentially small quantities cancel and leave the number of boxes. Cubically short of $\mathrm{D} = N = m^3$. |
| Sink of a tournament total | \(\Theta(m) = \Theta(\sqrt N)\) putative | $\Theta(m2^{-m})$ over $\Theta(2^{-m})$. Tight: $\mathrm{D} = \mathrm{R}_0 = \Theta(m)$, so OSSS recovers the true complexity of SINK up to a constant -- one of only two functions in the zoo where it does. |
| Scorpion graphs total | \((1+o(1))\,m/3\) putative | Exactly $4m(m-1)(m-2)2^{6-3m}$ over $\mathrm{MaxInf} = 12(m-2)^2 2^{6-3m}$, i.e. $m(m-1)/(3(m-2))$. Tight: $\mathrm{D} = \mathrm{R}_0 = \Theta(m)$, so this is the witness recorded for \(\mathrm{osss}(f)\) vs \(\mathrm{R}_{0}(f)\) -- the exponent-$1$ lower bound on the OSSS inequality itself. |
| Graph connectivity total | \((1+o(1))\,m = \Theta(\sqrt N)\) putative | Exactly $m2^{3-m}$ over $\mathrm{MaxInf} = 2^{3-m}$, both to leading order. Quadratically short of $\mathrm{D} = N = \binom m2$ and of $\mathrm{s} = \Theta(N)$: the variance is carried by the isolated-vertex event, which touches only $m-1$ coordinates. |