Variance
How far f is from constant. Not a complexity measure -- the unit the other Fourier quantities are divided by.
also written:
4p(1-p), balance, Var(f)
Definition
For $f:\{0,1\}^n\to\{-1,1\}$ with $p = \Pr[f=1]$, $$\mathrm{Var}(f) \;=\; \mathbb{E}[f^2]-\mathbb{E}[f]^2 \;=\; \sum_{S\ne\emptyset}\hat f(S)^2 \;=\; 4p(1-p).$$ It is $1$ for a balanced function, $2^{2-n}(1-2^{-n})$ for $\mathrm{OR}_n$, and $0$ for a constant. Two identities let you read it off other entries in the zoo: $$\mathrm{Var}(f) = 2\,\mathrm{NS}_{1/2}(f) = 1 - \mathrm{Stab}_0(f),$$ since at $\delta = 1/2$ the noisy copy is independent and $\mathrm{Stab}_0 = \hat f(\emptyset)^2$.
Why this is not a query complexity measure
Variance is not a query complexity measure and cannot be made into one. It is a number in $[0,1]$ that says how far $f$ is from constant, it does not grow with $n$, and two functions with wildly different complexity ($\oplus_n$ and a dictator) have exactly the same variance. It is in the zoo because it is the unit every other Fourier quantity has to be measured against.
The reason is bias. $\mathrm{OR}_n$ is $1$ on all but one input, so every Fourier quantity attached to it is exponentially small -- influences, noise sensitivity, spectral weight -- and none of that smallness has anything to do with $\mathrm{OR}_n$ needing $n$ queries. Dividing by $\mathrm{Var}$ cancels the bias exactly: $\mathrm{Var}(\mathrm{OR}_n) = \Theta(2^{-n})$ sits in the numerator and the $2^{-n}$ disappears. That is what turns $\mathrm{MaxInf}$ into \(\mathrm{osss}(f)\) and $\mathrm{NS}_\delta$ into \(\mathrm{nsr}(f)\), both of which are honest query counts. See Dimensionless quantities and how to normalize them.
Basic facts
- $\mathrm{MaxInf}(f)\le \mathrm{Var}(f)\le \mathrm{I}(f)$: the first because $\mathrm{Inf}_i = \sum_{S\ni i}\hat f(S)^2$ is part of the sum defining $\mathrm{Var}$, the second because $|S|\ge 1$ off the empty set.
- Every non-constant $f$ has $\mathrm{Var}(f)\ge 2^{2-n}(1-2^{-n})$, attained by $\mathrm{OR}_n$ and $\mathrm{AND}_n$.
- $\mathrm{Var}$ is not monotone under restriction and does not compose: $\mathrm{Var}(f\circ g)$ depends on the bias of $g$, which is exactly why biased gadgets destroy Fourier lower bounds.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{Var}(f)\). “\(\mathrm{Var}(f)\) in terms of it” is the pair with \(\mathrm{Var}(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^{2-n}(1-2^{-n})\) | Exactly $4p(1-p)$ with $p = 2^{-n}$. Exponentially unbalanced, which is why every raw Fourier quantity on this page is tiny while $\mathrm{D} = n$: they are all measuring the bias, not the difficulty. |
| AND total | \(2^{2-n}(1-2^{-n})\) | $4p(1-p)$ at $p = 1-2^{-n}$; identical to \(\mathrm{OR}_n\) by De Morgan, which flips $p$ to $1-p$ and leaves $\mathrm{Var}$ alone. |
| PARITY total | \(1\) | Perfectly balanced, so $\mathrm{Var} = 4\cdot\tfrac12\cdot\tfrac12 = 1$ -- the maximum. |
| MAJORITY total | \(1\) | Balanced for odd $n$. |
| Threshold total | \(4p(1-p),\quad p = 2^{-n}\sum_{j\ge k}\binom nj\) | The whole family in one line; $p\to\tfrac12$ and $\mathrm{Var}\to 1$ for $k$ within $O(\sqrt n)$ of $n/2$, and $\mathrm{Var}$ is exponentially small at the extremes $k \in \{1,n\}$, where the threshold degenerates to \(\mathrm{OR}_n\) and \(\mathrm{AND}_n\). |
| Symmetric functions (general) total | \(4p(1-p),\quad p = 2^{-n}\sum_{j\,:\,f_j = 1}\binom nj\) | Determined by the level set alone, like every other quantity on this page. |
| EXACT-HALF total | \(4M(1-M) = \Theta(1/\sqrt n),\quad M = \binom{n}{n/2}2^{-n}\) | The Fourier weight above level $0$, as noted in the \(\mathrm{Stab}_{\rho}(f)\) entry. |
| ODD-MAX-BIT total | \(8/9 + o(1)\) | From $\mathrm{Var} = 1-\mathrm{Stab}_0$ and the \(\mathrm{Stab}_{\rho}(f)\) entry, which gives $\mathrm{Stab}_0 = 1/9$. So $\mathrm{OMB}$ is balanced only in the weak sense: two independent inputs still agree $5/9$ of the time. |
| ADDRESS / multiplexer total | \(1\) | Balanced: the addressed data bit is uniform. |
| Binary tree navigation total | \(1\) | Balanced: the leaf reached is a uniform data bit. |
| TRIBES total | \(\Theta(1)\) | Exactly $1-o(1)$: the width is chosen so that $\Pr[f = 1] \to \tfrac12$. It also follows from the recorded $\mathrm{NS}_\delta = \tfrac12-o(1)$ and $\mathrm{NS}_\delta \le \mathrm{Var}/2$. |
| AND-OR tree (depth 2) total | \(\Theta(n2^{-n}) = \Theta(\sqrt N\,2^{-\sqrt N})\) | $4p(1-p)$ at $p = (1-2^{-n})^n = 1-\Theta(n2^{-n})$, as computed in the \(\mathrm{NS}_{\delta}(f)\) entry. |
| NAND tree (balanced AND-OR formula) total | \(2^{-\Theta(\sqrt N)}\) | $4p_d(1-p_d)$ with $p_d = 1-p_{d-1}^2$ from $p_0 = \tfrac12$; the orbit escapes to the $\{0,1\}$ two-cycle doubly exponentially, as computed in the \(\mathrm{NS}_{\delta}(f)\) entry. |
| Recursive MAJORITY-of-3 total | \(1\) | $\mathrm{MAJ}_3$ is balanced, so every level is, and $\hat f(\emptyset) = 0$. |
| Kushilevitz's function (iterated) total | \(1\) | The $\pm1$ Fourier expansion of the gadget recorded in the \(\mathrm{I}(f)\) entry has no constant term, so the gadget and every iterate of it is balanced. |
| Rubinstein's function total | \(\Theta(n^2 2^{-n})\) | $4p(1-p)$ at $p = 1-(1-(n/2)2^{-n})^n = \Theta(n^2 2^{-n})$, as computed in the \(\mathrm{NS}_{\delta}(f)\) entry. |
| Ambainis-Sun function total | \(\Theta(k^2 2^{-3k})\) | $4p(1-p)$ at $p = 1-(1-(2k+1)2^{-(3k+2)})^{3k+2} = (1+o(1))(3k+2)(2k+1)2^{-(3k+2)}$. |
| AND composed with NOT-EXACT-HALF total | \(2^{-\Theta(\sqrt n)} = 2^{-\Theta(N^{1/4})}\) | From $\mathrm{Var} = 2\,\mathrm{NS}_{1/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry. The ratio to $\mathrm{MaxInf}$ is not pinned at this precision, so \(\mathrm{osss}(f)\) and \(\mathrm{nsr}(f)\) are not recorded for this function. |
| Gilmer-Saks-Srinivasan functions total | \(2^{-\Theta(n)}\) | From $\mathrm{Var} = 2\,\mathrm{NS}_{1/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry; the exponent is not pinned tightly enough to read off \(\mathrm{osss}(f)\) or \(\mathrm{nsr}(f)\). |
| Ambainis' exact-quantum function total | \(\Theta(1)\) | Exactly $8/9-o(1)$: $\Pr[\mathrm{NE}^d = 1] \to 2/3$, so $\mathrm{Var} = 4p(1-p) \to 8/9$; equivalently $1-\hat f(\emptyset)^2$ with the $1/9$ of the \(\mathrm{Stab}_{\rho}(f)\) entry. |
| Surjectivity total | \(2^{-\Theta(n/\log n)}\) | From $\mathrm{Var} = 2\,\mathrm{NS}_{1/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry. A uniform input is surjective with doubly negligible probability, so the whole Fourier picture is about the bias; the ratio to $\mathrm{MaxInf}$ is not pinned, so \(\mathrm{osss}(f)\) is not recorded. |
| Triangle finding total | \(2^{-\Theta(m^2)}\) | From $\mathrm{Var} = 2\,\mathrm{NS}_{1/2}$ and the \(\mathrm{NS}_{\delta}(f)\) entry: a uniform graph contains a triangle with probability $1-2^{-\Theta(m^2)}$. |
| Inner product mod 2 total | \(1-2^{-n}\) | $4p(1-p)$ at $p = \tfrac12 - 2^{-n/2-1}$; equivalently $1-\mathrm{Stab}_0$ from the \(\mathrm{Stab}_{\rho}(f)\) entry. |
| Minsky-Papert one-in-a-box total | \((4+o(1))\,m\,2^{-m^2}\) | $2\,\mathrm{NS}_{1/2}$ from the \(\mathrm{NS}_{\delta}(f)\) entry; almost every input is a $1$-input, and $1-p = (1+o(1))m2^{-m^2}$ is the chance that some box is empty. |
| Sink of a tournament total | \((1+o(1))\,m\,2^{3-m}\) | $2\,\mathrm{NS}_{1/2}$ from the \(\mathrm{NS}_{\delta}(f)\) entry, i.e. $4p(1-p)$ at $p = m2^{1-m}$: a random tournament almost never has a sink. |
| Scorpion graphs total | \((4+o(1))\,m(m-1)(m-2)\,2^{6-3m} = \Theta(m^3 2^{-3m})\) | $2\,\mathrm{NS}_{1/2}$ from the \(\mathrm{NS}_{\delta}(f)\) entry: a uniform graph is a scorpion with probability $p = m(m-1)(m-2)2^{6-3m}$ and $\mathrm{Var} = 4p(1-p)$. |
| Graph connectivity total | \((1+o(1))\,m\,2^{3-m}\) | $2\,\mathrm{NS}_{1/2}$ from the \(\mathrm{NS}_{\delta}(f)\) entry, i.e. $4p(1-p)$ with $1-p = (1+o(1))m2^{1-m}$ the probability of an isolated vertex. |