Q The Query Complexity Zoo
\(\mathrm{OMB}_n\)

ODD-MAX-BIT

Sign degree $1$, deterministic complexity $n$: the extreme sdeg separation.

total basic arity: $n$ bits

Description

$\mathrm{OMB}_n(x) = 1$ iff the largest index $i$ with $x_i = 1$ is odd (and $\mathrm{OMB}_n(0^n)=0$).

Formal definition

$$\mathrm{OMB}_n(x) = \mathrm{sign}\Big(\sum_{i=1}^n (-1)^{i+1}\, 2^{\,n-i}\, x_i\Big)_{+}$$ i.e. it is the linear threshold function with exponentially decreasing weights; the highest-index $1$ dominates all lower-index terms.

Measure values

MeasureValueNotes
\(\mathrm{sdeg}(f)\) Sign degree \(1\) It is a linear threshold function -- but every representation needs exponentially large weights.
\(\mathrm{D}(f)\) Deterministic query complexity \(n\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(n)\)
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(n)\) From $\mathrm{R}(f) = \Theta(n) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ [CKMPSS23] -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. At the top of the range there is no room for fractional queries to help.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(n\)
\(\mathrm{s}(f)\) Sensitivity \(\lfloor n/2 \rfloor + 1\) putative Coordinates below the highest $1$ are never sensitive, so at an input whose highest $1$ is at position $i$ only position $i$ and the opposite-parity positions above it can be sensitive: $\mathrm{s}(x) \le 1 + \lceil (n-i)/2\rceil$. The bound is met at $x=e_1$, where $\{1\}\cup\{j>1 : j \text{ even}\}$ is sensitive.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}}(f) = n$ here.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{C}(f)\) Certificate complexity \(\lfloor n/2 \rfloor + 1\) putative A certificate need not pin the highest $1$ -- it only has to force the answer. If the highest $1$ of $x$ is at position $i$, it is enough to fix $x_i = 1$ and to zero out the opposite-parity positions above $i$: $1 + |\{j > i : j \not\equiv i\}|$ coordinates, maximised at $i = 1$ giving $\lfloor n/2\rfloor + 1$. That also matches $\mathrm{bs} = \lfloor n/2\rfloor+1 \le \mathrm{C}$, so the bound is tight. (Verified exhaustively for $n \le 12$.)
\(\mathrm{C}^0(f)\) 0-certificate complexity \(\lceil n/2 \rceil\) putative Attained at $0^n$, where zeroing the $\lceil n/2\rceil$ odd positions already forces the answer $0$ -- and at any $0$-input whose highest $1$ sits at position $2$.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(\lfloor n/2 \rfloor + 1\) putative Attained at $e_1$: fix $x_1 = 1$ and zero the $\lfloor n/2\rfloor$ even positions above it.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(1\) putative At $x = e_n$, reading $x_n = 1$ already decides (the answer is the parity of $n$). Certificate complexity varies by a factor of $\Theta(n)$ across inputs.
\(\mathrm{bs}(f)\) Block sensitivity \(\lfloor n/2 \rfloor + 1\) putative Equal to $\mathrm{s}$, so blocks buy nothing. A sensitive block at $x$ either contains the current highest $1$ (at most one such block can be disjoint from the others) or has its own maximum above it, of parity opposite to $i$ -- and distinct disjoint blocks need distinct maxima. That caps the count at $1+\lceil (n-i)/2\rceil$, the same bound as for $\mathrm{s}$, and $x=e_1$ attains it.
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(\lfloor n/2 \rfloor + 1\) putative The same argument survives the fractional relaxation: charge each block to its maximum index, and the load constraint at that coordinate caps the total weight per admissible maximum at $1$.
\(\deg(f)\) Exact degree \(n\) putative Writing $\mathrm{OMB} = \sum_{i \text{ odd}} x_i\prod_{j>i}(1-x_j)$, the monomial $x_1x_2\cdots x_n$ can only come from the $i=1$ term, with coefficient $(-1)^{n-1} \ne 0$. So $\deg = n$ against $\mathrm{sdeg} = 1$ -- the maximum possible separation between exact and sign degree.
\(\deg_2(f)\) Mod-2 degree \(n\) putative The same expansion over $\mathbb{F}_2$, with the same top monomial and coefficient $1$.
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(\sqrt n)\) putative Upper: quantum maximum-finding [DurrHoyer96] locates the highest $1$ in $O(\sqrt n)$ queries; its parity is the answer. Lower: setting all even-indexed bits to $0$ restricts $\mathrm{OMB}$ to $\mathrm{OR}$ on the odd ones, so $\mathrm{Q} \ge \mathrm{Q}(\mathrm{OR}_{\lceil n/2\rceil}) = \Omega(\sqrt n)$.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Theta(\sqrt n)\) Squeezed: $\mathrm{bs} = O(\widetilde{\deg}^2)$ gives $\widetilde{\deg} = \Omega(\sqrt n)$, and $\widetilde{\deg} \le 2\mathrm{Q} = O(\sqrt n)$.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\Theta(n)\) Squeezed between $\deg/2 = n/2$ and $\mathrm{D} = n$. So $\mathrm{OMB}$ has a full quadratic exact-vs-bounded-error quantum gap.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Theta(n)\) Between $\mathrm{rdeg}/2 = \Theta(n)$ and $\mathrm{D} = n$. Note it is $\mathrm{rdeg}$, not $\deg$, that floors $\mathrm{Q}_0$ -- see \(\mathrm{Q}_{0}(f)\); both are $\Theta(n)$ here.
\(\mathrm{DTsize}(f)\) Decision tree size \(n+1\) putative Query $x_n, x_{n-1}, \dots$ and stop at the first $1$: a path with $n$ branchings, hence $n+1$ leaves. The all-zero input forces a root-to-leaf path of length $n$, so no smaller tree exists.
\(\mathrm{s}^0(f)\) 0-sensitivity \(\lceil n/2 \rceil\) putative Attained at $0^n$: flipping position $j$ makes $j$ the highest $1$, which flips the answer exactly for the $\lceil n/2\rceil$ odd $j$. (Verified exhaustively for $n \le 12$.)
\(\mathrm{s}^1(f)\) 1-sensitivity \(\lfloor n/2 \rfloor + 1\) putative Attained at $e_1$: the $\lfloor n/2 \rfloor$ even positions above, plus position $1$ itself. This is the value recorded as $\mathrm{s}$.
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(\lceil n/2 \rceil\) putative Equal to $\mathrm{s}^0$: blocks buy nothing on either side, by the maximum-index charging argument used for $\mathrm{bs}$. (Verified exhaustively for $n \le 12$.)
\(\mathrm{bs}^1(f)\) 1-block sensitivity \(\lfloor n/2 \rfloor + 1\) putative Equal to $\mathrm{s}^1$, and to $\mathrm{bs}$.
\(\mathrm{FC}(f)\) Fractional certificate complexity \(\lfloor n/2 \rfloor + 1\) $\mathrm{FC}(f) = \mathrm{fbs}(f)$ exactly, by LP duality. Tal13 KulkarniTal16
\(\mathrm{EC}(f)\) Expectational certificate complexity \(\lfloor n/2 \rfloor + 1\) Sandwiched: $\mathrm{fbs}(f) \le \mathrm{EC}(f) \le \mathrm{C}(f)$, with both ends $\lfloor n/2\rfloor+1$ here. GJKKLSSV17
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(n)\) $\mathrm{RC}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$, and $\mathrm{fbs}(f) = \lfloor n/2\rfloor+1$ here. Aaronson08
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(n)\) $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for total $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = \lfloor n/2\rfloor+1$ here. ABIKPS17
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(n)\) $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{CA}(f))$ for every $f$, and $\mathrm{CA}(f) = \Theta(n)$ here. CGLMSG23
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. Note $\mathrm{CG}^{*} = \Theta(n)$ against $\mathrm{Q} = \Theta(\sqrt n)$: another instance of the entangled certificate game not being bounded by quantum query complexity. CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\Theta(n)\) All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$ for every function (the non-signaling bottleneck, \(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{CG}^{\mathrm{ns}}(f)\)), so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim; only the private-coin \(\mathrm{CG}(f)\) can be larger. CGLMSG23
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Omega(n),\ O(n^2)\) From below $\mathrm{R}_0 = \Theta(n)$ and $\mathrm{Adv}^2 = \Theta(n)$; from above $\mathrm{C}^0\mathrm{C}^1 = \Theta(n^2)$ [CGLMSG23]. The two ends do not meet and nothing in the zoo closes the gap, so the cell is recorded as a range rather than as the old (unjustified) $\Theta(n)$, which rested on the false inequality $\mathrm{CG} \le \mathrm{D}$. CGLMSG23
\(\mathrm{RS}(f)\) Sabotage complexity \(\Theta(n)\) Sandwiched: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. BenDavidKothari18
\(\chi(f)\) Conflict complexity \(\Theta(n)\) Sandwiched: $\chi(f) = \Omega(\mathrm{bs}(f))$ and $\chi(f) = O(\mathrm{R}(f))$, with both ends $\Theta(n)$ here. Li18
\(\bar{\chi}(f)\) Max-conflict complexity \(\Theta(n)\) Sandwiched: $\mathrm{RS}(f) = O(\bar{\chi}(f))$ and $\bar{\chi}(f) = O(\mathrm{R}(f))$, with both ends $\Theta(n)$ here. GLSS19
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Theta(n)\) Sandwiched: $\bar{\chi}(f) = O(\mathrm{LR}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. BBGM22
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\Theta(n)\) Sandwiched: $\mathrm{LR}(f) = O(\mathrm{R}^{*}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. BBGM22
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Theta(n)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Theta(\sqrt n)\) $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(n)$ here. Aaronson08
\(\lambda(f)\) Spectral sensitivity \(\Theta(\sqrt n)\) Sandwiched: $\sqrt{\mathrm{s}(f)} \le \lambda(f) = O(\mathrm{Q}_{\varepsilon}(f))$, with $\mathrm{s}(f) = \lfloor n/2\rfloor+1$ and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt n)$ here. So \(\mathrm{OMB}_n\) joins \(\mathrm{OR}_n\) as a family where Huang's $\mathrm{s} \le \lambda^2$ is tight. ABKRT21
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(\sqrt n)\) $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt n)$ here.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(\sqrt n)\) Sandwiched: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f)$, with both ends $\Theta(\sqrt n)$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(\sqrt n)\) $\gamma_2^{\alpha}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q}_{\varepsilon}(f) = \Theta(\sqrt n)$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(\sqrt n)\) Sandwiched: $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(\sqrt n)$ here. Spalek08
\(\mathrm{rank}(f)\) Decision tree rank \(1\) putative The optimal tree is a caterpillar: query $x_n$, then $x_{n-1}$, and so on, stopping at the first $1$ -- whose index immediately gives the answer. Every internal node therefore has a leaf child, so the rank is $1$ (and it cannot be $0$, as $\mathrm{OMB}$ is not constant). Against $\mathrm{D} = n$ this is the maximum possible rank-vs-depth gap, matching \(\mathrm{OR}_n\). It also explains $\mathrm{DTsize} = n+1$.
\(\mathrm{I}(f)\) Total influence (L2 influence) \(\Theta(1)\) putative Coordinate $i$ is pivotal only when every bit above it is $0$, which costs $2^{-(n-i)}$; conditioned on that, flipping $x_i$ moves the maximum to the highest $1$ below $i$, whose index has the opposite parity with probability $\tfrac12+\tfrac18+\tfrac1{32}+\cdots = \tfrac23$. Summing the geometric series, $\mathrm{I}(\mathrm{OMB}_n) \to 4/3$. So $\mathrm{OMB}$ is a balanced function of total influence $O(1)$ and $\mathrm{D} = n$.
\(\mathrm{I}^{1}(f)\) Total L1 influence \(\Theta(1)\) Boolean-valued, so equal to $\mathrm{I}(f)$.
\(\mathrm{MaxInf}(f)\) Maximum influence \(\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.
\(\mathrm{Var}(f)\) Variance \(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.
\(\mathrm{osss}(f)\) OSSS number \(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.
\(\mathrm{nsr}(f)\) Noise robustness \(5 + o(1)\) putative Solving $\mathrm{NS}_\delta = \tfrac{4\delta}{3(1+\delta)} = \mathrm{Var}/4 = 2/9$ gives $\delta^{*} = 1/5$ exactly, in the $n\to\infty$ limit. One of the few functions here whose critical noise rate is a constant that can be written down.
\(\deg_p(f)\) Mod-p degree \(n\) putative For every prime $p$. The expansion $\mathrm{OMB} = \sum_{i \text{ odd}} x_i\prod_{j>i}(1-x_j)$ has the top monomial $x_1\cdots x_n$ only from the $i=1$ term, with coefficient $(-1)^{n-1}$, which is nonzero in every characteristic. So small characteristic buys nothing, exactly as for \(\mathrm{OR}_n\).
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(\Theta(n)\) Sandwiched: $\mathrm{C}(f) \le \mathrm{UC}(f) \le \mathrm{D}(f)$, with $\mathrm{C}(f) = \lfloor n/2\rfloor+1$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(\Theta(n)\) Squeezed: $\mathrm{fbs}(f) \le 2\,\mathrm{UC}_{\min}(f)-1$ [BHT17] forces $\mathrm{UC}_{\min} \ge \tfrac12(\lfloor n/2\rfloor+2) = \Omega(n)$, and $\mathrm{UC}_{\min} \le \mathrm{UC} = \Theta(n)$. Note the contrast with $\mathrm{C}_{\min} = 1$: the one-sided unambiguous measure is not a minimum over inputs and does not collapse. BHT17
\(\mathrm{SP}(f)\) Subcube partition complexity \(\Theta(n)\) Sandwiched: $\mathrm{C}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$, with $\mathrm{C}(f) = \lfloor n/2\rfloor+1$ and $\mathrm{D}(f) = n$ here.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(n\) putative At most $\mathrm{D} = n$. For the lower bound, take the $\pm1$-valued $g = 1-2\mathrm{OMB}$: in the expansion $\mathrm{OMB} = \sum_{i \text{ odd}} x_i\prod_{j>i}(1-x_j)$ only the $i=1$ term involves $x_1$, so it alone determines $\hat g(S)$ for every $S \ni 1$, and each such coefficient is exactly $\pm 2^{-(n-1)}$. The granularity is therefore exactly $n-1$, and the bound $\mathrm{D}^{\oplus} \ge \mathrm{gran}+1$ of [ChistopolskayaPodolskii18] gives $n$. So parity queries buy nothing, even though $\mathrm{sdeg} = 1$. ChistopolskayaPodolskii18
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension \(n\) putative Full. By the computation on the \(\mathrm{D}^{\oplus}(f)\) line, $\hat g(S) = \pm2^{-(n-1)} \ne 0$ for every $S$ containing the coordinate $1$; in particular $\{1\}$ and $\{1,j\}$ are in the support, and their $\mathbb{F}_2$-sum is $\{j\}$.
\(\mathrm{spar}(f)\) Fourier sparsity \(\Theta(2^n)\) putative At least $2^{n-1}$, since every one of the $2^{n-1}$ sets containing coordinate $1$ carries the nonzero coefficient $\pm2^{-(n-1)}$ (see the \(\mathrm{D}^{\oplus}(f)\) line); at most $2^n$ trivially.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(n)\) putative Take the product distribution with each bit $1$ independently with probability $c/n$ for a suitable constant $c$. Run a depth-$m$ deterministic tree and follow the path on which every answer is $0$: it is reached with probability $\approx e^{-cm/n}$, and conditioned on it the highest $1$ lies among the $n-m$ unread coordinates, where its index is odd with probability $\tfrac12(1-e^{-c(n-m)/n})$ -- bounded away from $0$ and $1$. For $m \le 0.1n$ the product of the two exceeds $1/3$, so $\mathrm{D}^{\mathrm{prod}} = \Omega(n)$, matching $\mathrm{D} = n$. Unlike its randomized expected cost, which is $O(1)$ under this distribution, the worst-case depth stays linear.
\(\hat{L}_1(f)\) Spectral norm \(\Theta(n)\) putative Exactly. The $2^{-(n-i+1)}$-weighted subcubes $B_i = \{x_i=1,\ x_j=0\ \forall j>i\}$ for odd $i$ partition $\mathrm{OMB}^{-1}(1)$, and $\mathbb{1}_{B_i} = 2^{-(n-i+1)}(1-\chi_i)\prod_{j>i}(1+\chi_j)$. Summing, a set $S$ with $\min S = t$ gets $\widehat{\mathrm{OMB}}(S) = \sum_{i \text{ odd},\, i \le t} 2^{i-n-1} - 2\cdot[t \text{ odd}]\,2^{t-n-1}$, whose absolute value is $\tfrac23 2^{t-n-1}(1+o(1))$ for either parity of $t$. There are $2^{n-t}$ sets with $\min S = t$, so each $t$ contributes $\tfrac13$ and $\hat L_1 = \tfrac{2n}{3}(1+o(1))$ in the $\pm1$ encoding. Linear, not exponential -- $\mathrm{OMB}$ is a sum of only $n/2$ subcube indicators, so it sits with \(\mathrm{OR}_n\) rather than with \(\mathrm{MAJ}_n\) on the spectral-norm scale, despite having full degree.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Theta(n)\)· putative Upper: $\mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f) = n$. Lower: setting every even position to $0$ leaves $\vee_{\lceil n/2\rceil}$ on the odd positions, and a conical junta restricts to a conical junta of no larger width, so $\mathrm{cjdeg} = \Omega(n)$ by the \(\mathrm{OR}_n\) line. Non-negativity therefore costs a quadratic blow-up over $\widetilde{\deg}_{\varepsilon} = \Theta(\sqrt n)$.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Omega(\sqrt n),\ O(n)\) Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(\sqrt n)$. Upper: the universal $O(n)$ bound of [BNRdW05] for recovering all $n$ noisy bits. Whether the $\sqrt n$ algorithm survives noise is the interesting question and is not settled here. BNRdW05
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Omega(n),\ O(n\log n)\) Lower: $\mathrm{N}_p \ge \mathrm{R} = \Theta(n)$. Upper: repeat each query $O(\log n)$ times. The influence-based lower bound of the \(\mathrm{N}_{p}(f)\) record gives nothing here, since $\mathrm{I}(\mathrm{OMB}) = \Theta(1)$ -- so unlike \(\oplus_n\) or \(\mathrm{ADDR}_k\) there is no evidence that the log factor is needed. FRPU94
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(\lfloor n/2 \rfloor + 1\) putative Exactly. Upper: $\mathrm{ndeg} \le \mathrm{C}^1 = \lfloor n/2\rfloor + 1$ (the \(\mathrm{C}^1(f)\) line). Lower: set every odd position $\ge 3$ to $0$ and leave $x_1$ together with the $\lfloor n/2\rfloor$ even positions free; the restriction is $1$ iff $x_1 = 1$ and all even positions are $0$, an $\mathrm{AND}$ on $\lfloor n/2\rfloor+1$ variables with some of them negated. Nondeterministic degree cannot increase under restriction or under negating variables, and $\mathrm{ndeg}(\wedge_m) = m$ (the \(\mathrm{AND}_n\) line). Exhaustive computation of the minimal witnessing degree for $n \le 9$ agrees. deWolf03
\(\mathrm{rdeg}(f)\) Rational degree \(\lfloor n/2 \rfloor + 1\) putative Exactly, from $\mathrm{rdeg}(f) = \max\{\mathrm{ndeg}(f),\ \mathrm{ndeg}(\bar f)\}$. The line above gives $\mathrm{ndeg}(f) = \lfloor n/2\rfloor+1$. For the complement, $\mathrm{ndeg}(\bar f) \le \mathrm{C}^0 = \lceil n/2\rceil$, and setting all even positions to $0$ leaves $\bar f$ equal to the $\mathrm{AND}$ of the negations of the $\lceil n/2 \rceil$ odd variables, so $\mathrm{ndeg}(\bar f) = \lceil n/2\rceil$. The maximum is $\lfloor n/2\rfloor+1$, meeting the general bound $\mathrm{rdeg} \le \mathrm{C}$ recorded on the \(\mathrm{C}(f)\) line. deWolf03
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\lceil (\lfloor n/2 \rfloor + 1)/2 \rceil\) Exactly, from $\mathrm{NQ}(f) = \lceil\mathrm{ndeg}(f)/2\rceil$ [deWolf00] and the \(\mathrm{ndeg}(f)\) line. So $\mathrm{NQ} = \Theta(n)$ while $\mathrm{Q} = \Theta(\sqrt n)$: nondeterminism is quadratically worse than bounded error here, the same phenomenon as at \(\mathrm{AND}_n\). deWolf00
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(\Theta(\sqrt n)\) putative Upper: $\widetilde{\deg}_+ \le \widetilde{\deg} = \Theta(\sqrt n)$. Lower: one-sided approximate degree does not increase under restriction or under negating variables, and the restriction used on the \(\mathrm{ndeg}(f)\) line turns OMB into an $\mathrm{AND}$ on $\lfloor n/2\rfloor+1$ variables, for which $\widetilde{\deg}_+ = \Theta(\sqrt n)$ (the \(\mathrm{AND}_n\) line). So the one-sided relaxation buys nothing, even though $\mathrm{sdeg}(\mathrm{OMB}) = 1$.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(1\) putative Degree $1$ suffices, as for \(\mathrm{OR}_n\). Take $N(x) = \sum_{i \text{ odd}} 10^i x_i$ and $D(x) = 1 + \sum_i 10^i x_i$, both of degree $1$, and let $h$ be the highest position with $x_h = 1$ (with $h=0$ for $x = 0^n$, where $N/D = 0$). Then $10^h \le D \le 1 + \tfrac{10}{9}(10^h-1) < 1.112\cdot 10^h$. If $h$ is odd then $10^h \le N \le \tfrac{100}{99}10^h$, so $N/D \ge 0.899$; if $h$ is even then $N \le \tfrac{100}{99}10^{h-1}$, so $N/D \le 0.102$. Hence $|N/D - \mathrm{OMB}| \le 0.102$ everywhere, for every $n$ (the true maximum is $0.092$). Compare $\widetilde{\deg} = \Theta(\sqrt n)$ and $\mathrm{D} = n$. MahadevdeWolf15
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(\Theta(1)\) $\mathrm{PostQ}_{\varepsilon}(f) = \Theta(\mathrm{rdeg}_{\varepsilon}(f))$ [MahadevdeWolf15], and $\mathrm{rdeg}_{\varepsilon} = 1$ on the \(\mathrm{rdeg}_{\varepsilon}(f)\) line. Postselection collapses OMB entirely, against $\mathrm{Q} = \Theta(\sqrt n)$ and $\mathrm{D} = n$ -- the largest gap in this file after \(\mathrm{EH}_n\). MahadevdeWolf15
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity \(\tfrac{4\delta}{3(1+\delta)} + o(1)\) putative For every fixed $\delta$, as $n \to \infty$. Scan positions from the top: at each one the pair $(x_i,y_i)$ is $(0,0)$ with probability $(1-\delta)/2$, so conditioned on the first position $k$ where it is not, the pair is $(1,1)$ with probability $\tfrac{1-\delta}{1+\delta}$ -- both highest ones are then at $k$ and the answers agree -- and is $(1,0)$ or $(0,1)$ with probability $\tfrac{2\delta}{1+\delta}$. In the latter case one highest one is at $k$ and the other is the highest one of a fresh uniform string below $k$, whose position has parity opposite to $k$ with probability $\tfrac12+\tfrac18+\cdots = \tfrac23$. Multiplying gives $\tfrac{2\delta}{1+\delta}\cdot\tfrac23$. So OMB is noise-stable in the sense that $\mathrm{NS}_\delta \to 0$ with $\delta$, uniformly in $n$, unlike \(\oplus_n\) or \(\mathrm{Tribes}_{w,s}\).
\(\mathrm{Stab}_{\rho}(f)\) Noise stability \(1 - \tfrac{8(1-\rho)}{3(3-\rho)} + o(1)\) putative From $\mathrm{Stab}_\rho = 1 - 2\,\mathrm{NS}_{(1-\rho)/2}$ and the \(\mathrm{NS}_{\delta}(f)\) line. It is $1/9$ at $\rho = 0$, so two independent uniform inputs still give correlated answers -- the highest-one statistic is dominated by the top few coordinates.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(n)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(n)$; the \(\mathrm{D}^{\mathrm{prod}}(f)\) line exhibits a product distribution attaining it. Yao77
\(\mathrm{cbs}(S)\) Critical block sensitivity \(\lfloor n/2 \rfloor + 1\) Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$, recorded on the \(\mathrm{bs}(f)\) line. GoosPitassi14
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(n)\) Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ $= \Theta(n)$. CDM23

Separations its values prove — computed, not recorded

Read straight off the table above by comparing two values: no relation record states these, and where one does and says more, the record wins and the pair is not listed here. 150 in total, strongest first.

… and 136 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.

Separations it witnesses