Q The Query Complexity Zoo

Dimensionless quantities and how to normalize them

MaxInf, NS and Stab are probabilities, not query counts. Why they cannot appear in the matrix, and what ratio to use instead.

Every measure in the exponent matrix answers the same question: how many queries? Each one grows with $n$, and a cell of the matrix asserts something of the form $\mathrm{M}_1 = O(\mathrm{M}_2^{\,b})$ -- a comparison that only means anything if both sides are on the same scale.

Several natural Fourier quantities are not on that scale. \(\mathrm{MaxInf}(f)\) is a probability. So is noise sensitivity \(\mathrm{NS}_{\delta}(f)\). Noise stability \(\mathrm{Stab}_{\rho}(f)\) is a correlation, and \(\mathrm{Var}(f)\) is a variance of a $\pm 1$ random variable. All of them live in a bounded interval no matter how large $n$ is. That has three consequences:

  1. No exponent exists. A quantity that never exceeds $1$ cannot be polynomially related to one that grows like $n$, in either direction, for reasons of units alone. The cell is not "open"; it is meaningless.
  2. The sign is often backwards. $\mathrm{MaxInf}$ and $\mathrm{NS}_\delta$ tend to be smaller for harder functions, so even a qualitative reading of the row would mislead.
  3. Bias dominates. $\mathrm{MaxInf}(\mathrm{OR}_n) = 2^{1-n}$ is tiny not because $\mathrm{OR}_n$ is easy -- it is evasive -- but because $\mathrm{OR}_n$ is nearly constant. Any statement about a lopsided function is really a statement about its bias.

So the zoo keeps these quantities, with their own pages, definitions and relations, but hides them from the matrix. What goes into the matrix instead is a normalized version: a ratio of two dimensionless quantities, or an inverse of a rate, chosen so that the result is a query count.

Divide by the variance

$\mathrm{Var}(f) = 4p(1-p)$, where $p = \Pr[f = 1]$, is the natural unit of "how much there is to lose". Every Fourier quantity above is measured against it, and dividing cancels the bias exactly. The zoo records one such ratio: $$\mathrm{osss}(f) \;=\; \frac{\mathrm{Var}(f)}{\mathrm{MaxInf}(f)} .$$ This is a genuine query count -- it is between $1$ and $O(n/\log n)$, and the OSSS inequality says it lower-bounds the average depth of a decision tree for $f$, hence $\mathrm{R}_0(f)$ and $\mathrm{D}(f)$. See \(\mathrm{osss}(f)\).

Invert a rate

When a dimensionless quantity comes with a free parameter, the query-scale content is where the parameter has to be for something to happen. For noise sensitivity, the critical rate $\delta^{*}$ at which $\mathrm{NS}_\delta$ reaches a fixed fraction of its maximum gives $$\mathrm{nsr}(f) \;=\; 1/\delta^{*}(f),$$ which is $\Theta(n)$ for $\oplus_n$ and $\Theta(1)$ for $\mathrm{MAJ}_n$. See \(\mathrm{nsr}(f)\).

The other end of the same curve is also a query count: the slope of $\mathrm{NS}_\delta$ at $\delta = 0$ is the total influence $\mathrm{I}(f)$, which was already in the zoo as \(\mathrm{I}(f)\) and satisfies $\mathrm{I}\le\mathrm{D}$. One dimensionless family thus yields two measures that point in opposite directions -- $\mathrm{I}$ is large when $f$ is fragile, $\mathrm{nsr}$ when it is robust.

What normalization does not fix

A normalized quantity inherits the weakness of its ingredients. $\mathrm{osss}$ is a weak lower bound: it is $1$ for $\oplus_n$ and $\Theta(1)$ for $\mathrm{OR}_n$, both of which have $\mathrm{D} = n$. Nor are the two normalizations comparable to each other -- $\oplus_n$ has $\mathrm{osss} = 1$ and $\mathrm{nsr} = \Theta(n)$, $\mathrm{MAJ}_n$ has $\mathrm{osss} = \Theta(\sqrt n)$ and $\mathrm{nsr} = \Theta(1)$. Putting a quantity on the query scale makes it comparable, not strong.

Finally, the constants in a normalization are a convention. Any fixed fraction of the maximum defines $\delta^{*}$ up to a constant factor, so $\mathrm{nsr}$ is only meaningful up to $\Theta(\cdot)$; values are recorded that way.