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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{I}(f_n) = O(1)\)from \(\mathrm{D}(f) = n\) against \(\mathrm{I}(f) = \Theta(1)\)
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \mathrm{I}^{1}(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = n+1\) against \(\mathrm{I}^{1}(f) = \Theta(1)\)
-
\(\mathrm{D}^{\oplus}(f_n) \to \infty \ \text{ while } \ \mathrm{nsr}(f_n) = O(1)\)from \(\mathrm{D}^{\oplus}(f) = n\) against \(\mathrm{nsr}(f) = 5 + o(1)\)
-
\(\mathrm{UC}_{\min}(f_n) \to \infty \ \text{ while } \ \mathrm{PostQ}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{UC}_{\min}(f) = \Theta(n)\) against \(\mathrm{PostQ}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{N}_{p}(f_n) \to \infty \ \text{ while } \ \mathrm{sdeg}(f_n) = O(1)\)from \(\mathrm{N}_{p}(f) = \Omega(n),\ O(n\log n)\) against \(\mathrm{sdeg}(f) = 1\)
-
\(\deg_2(f_n) \to \infty \ \text{ while } \ \mathrm{MaxInf}(f_n) = O(1)\)from \(\deg_2(f) = n\) against \(\mathrm{MaxInf}(f) = \Theta(1)\)
-
\(\deg_p(f_n) \to \infty \ \text{ while } \ \mathrm{Var}(f_n) = O(1)\)from \(\deg_p(f) = n\) against \(\mathrm{Var}(f) = 8/9 + o(1)\)
-
\(\hat{L}_1(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\hat{L}_1(f) = \Theta(n)\) against \(\mathrm{C}_{\min}(f) = 1\)
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{I}^{1}(f_n) = O(1)\)from \(\mathrm{D}(f) = n\) against \(\mathrm{I}^{1}(f) = \Theta(1)\)
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \mathrm{I}(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = n+1\) against \(\mathrm{I}(f) = \Theta(1)\)
-
\(\mathrm{N}_{p}(f_n) \to \infty \ \text{ while } \ \mathrm{PostQ}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{N}_{p}(f) = \Omega(n),\ O(n\log n)\) against \(\mathrm{PostQ}_{\varepsilon}(f) = \Theta(1)\)
-
\(\deg_p(f_n) \to \infty \ \text{ while } \ \mathrm{MaxInf}(f_n) = O(1)\)from \(\deg_p(f) = n\) against \(\mathrm{MaxInf}(f) = \Theta(1)\)
-
\(\hat{L}_1(f_n) \to \infty \ \text{ while } \ \mathrm{rank}(f_n) = O(1)\)from \(\hat{L}_1(f) = \Theta(n)\) against \(\mathrm{rank}(f) = 1\)
-
\(\mathrm{UC}_{\min}(f_n) = \Omega\big(\mathrm{Adv}(f_n)^{2}\big)\)from \(\mathrm{UC}_{\min}(f) = \Theta(n)\) against \(\mathrm{Adv}(f) = \Theta(\sqrt n)\)
… and 136 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.
Separations it witnesses
-
Unbounded: $\mathrm{D}=n$, $\mathrm{sdeg}=1$. Sign degree is not polynomially related to any other measure in the zoo.
-
Unbounded and maximal: $\deg = n$ against $\mathrm{sdeg} = 1$.
-
Unbounded: $\mathrm{C}=\lfloor n/2\rfloor+1$ at $e_1$ against $\mathrm{C}_{\min}=1$ at $e_n$.
-
Quadratic: $\mathrm{Q}_E = \Theta(n)$ (forced by $\deg = n$) against $\mathrm{Q} = \Theta(\sqrt n)$ (quantum maximum finding).