Binary tree navigation
Adaptivity at its most extreme: $\mathrm{D}=k$ but every one of the $2^k-1$ variables is relevant.
total basic arity: $2^k - 1$ bits
Description
Index the variables by the nodes of a complete binary tree of depth $k$, so $x_0$ sits at the root and node $i$ has children $2i+1$ and $2i+2$. Walk the tree: read $x_0$, and from node $i$ move to node $2i+1+x_i$. After $k$ reads the walk is at a node of the bottom level; the output is the bit read there.
Formal definition
$$\mathrm{Nav}_k(x) = x_{i_k}, \qquad i_0 = 0,\ \ i_{j+1} = 2 i_j + 1 + x_{i_j},$$ so $i_k \in \{2^{k-1}-1,\dots,2^k-2\}$ indexes the bottom level.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{D}(f)\) Deterministic query complexity | \(k\) | The walk reads one variable per level. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(2^k - 1\) | Every variable is relevant: for the node $v$, take the input whose walk reaches $v$ and whose two subtrees below $v$ lead to bottom bits of opposite value. So a non-adaptive algorithm must read all of them, and $\mathrm{D}^{\mathrm{na}} = 2^{\mathrm{D}}-1$ exactly -- the extreme case of the bound $\mathrm{D}^{\mathrm{na}} \le 2^{\mathrm{D}}-1$. |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Theta(k)\) | At most $\mathrm{D}=k$. For the lower bound, on a uniformly random input each of the $k$ variables on the walk is sensitive with probability $1/2$, so $\mathrm{bs} = \Omega(k)$ and $\mathrm{R} \ge \mathrm{bs}/3$. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Theta(2^k)\) | On a uniformly random input the bottom node reached is uniform over the $2^{k-1}$ bottom nodes, and an algorithm that has not read it is guessing an unbiased bit; a fixed set of $m$ variables contains it with probability at most $m/2^{k-1}$. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Theta(k)\) | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \bar{\mathrm{R}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(k)$ and $\mathrm{D}(f) = k$ here. |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\Theta(k)\) | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(k)$ and $\mathrm{D}(f) = k$ here. |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\Theta(k)\) | Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{1}(f) \le \mathrm{D}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(k)$ and $\mathrm{D}(f) = k$ here. |
| \(\mathrm{C}(f)\) Certificate complexity | \(k\) putative | The walk itself is a certificate, and nothing shorter is: omit a node of the walk and the walk is free to leave. So $\mathrm{C} = \mathrm{C}^0 = \mathrm{C}^1 = \mathrm{C}_{\min} = \mathrm{D} = k$ -- navigation is completely certificate-uniform, and all the difficulty is in finding the $k$ relevant variables among $2^k-1$. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(k\) putative | Every input has the same certificate structure. |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(k\) putative | As $\mathrm{C}$: complementing the bottom level swaps the two sides, so the certificate structure is the same for both. (Verified exhaustively for $k \le 3$.) |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(k\) putative | As $\mathrm{C}^0$. |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(k\) putative | As $\mathrm{s}$: the construction there can be run with either final value, so both sides reach $k$. (Verified exhaustively for $k \le 3$.) |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(k\) putative | As $\mathrm{s}^0$. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(k\) | Squeezed between $\mathrm{s}^0 = k$ and $\mathrm{C}^0 = k$. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(k\) | Squeezed between $\mathrm{s}^1 = k$ and $\mathrm{C}^1 = k$. |
| \(\mathrm{s}(f)\) Sensitivity | \(k\) putative | At the right input all $k$ walk variables are sensitive: flipping the bottom one flips the output, and flipping the one at level $j$ diverts the walk into the sibling subtree -- arrange each sibling subtree to deliver the opposite bit. Nothing off the walk is sensitive. |
| \(\mathrm{bs}(f)\) Block sensitivity | \(k\) | Squeezed between $\mathrm{s}=k$ and $\mathrm{C}=k$. |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(k\) | Squeezed between $\mathrm{bs}=k$ and $\mathrm{C}=k$. |
| \(\deg(f)\) Exact degree | \(k\) putative | Expand recursively: $\mathrm{Nav}_k = (1-x_0)\mathrm{Nav}_{k-1}(L) + x_0\mathrm{Nav}_{k-1}(R)$. The two subtrees have disjoint variable sets, so the top monomial of the right branch times $x_0$ has degree $k$ and cannot be cancelled by anything in the left branch. |
| \(\deg_2(f)\) Mod-2 degree | \(k\) putative | The same recursion over $\mathbb{F}_2$: $\mathrm{Nav}_k = L + x_0(L+R)$. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(\Theta(k)\) | Squeezed between $\deg/2$ and $\mathrm{D}$, both $\Theta(k)$. |
| \(\mathrm{I}(f)\) Total influence (L2 influence) | \((k+1)/2\) putative | On a uniform input the level-$j$ walk variable is pivotal exactly when the sibling subtree would deliver the opposite bit, which happens with probability $1/2$; the bottom variable is always pivotal. So $\mathrm{I} = 1 + (k-1)/2$ while the function has $2^k-1$ variables -- influence logarithmic in the input length, and a clean instance of $\mathrm{I} \le \mathrm{D}$ being tight up to a factor of $2$. |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(2^k\) putative | Exactly. The walk tree is complete of depth $k$, giving $2^k$ leaves. For the lower bound: the walk is the unique minimal certificate, so every leaf's read-set contains one complete walk together with its final bit, and the $2^{k-1}$ walks times the $2$ values of the final bit need $2^k$ distinct leaves. |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(k\) | $\mathrm{FC}(f) = \mathrm{fbs}(f)$ exactly, by LP duality, and $\mathrm{fbs} = k$ here. Tal13 KulkarniTal16 |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(\Theta(k)\) | $\mathrm{RC}(f) = \Theta(\mathrm{fbs}(f))$ for every $f$, and $\mathrm{fbs}(f) = k$ here. Aaronson08 |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(k\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{EC}(f) \le \mathrm{C}(f)$, with both ends $k$ here. GJKKLSSV17 |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\Theta(k)\) | $\mathrm{CA}(f) = \Theta(\mathrm{fbs}(f))$ for total $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs}(f) = k$ here. ABIKPS17 |
| \(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) | \(\Theta(k)\) | $\mathrm{CG}^{\mathrm{pub}}(f) = \Theta(\mathrm{CA}(f))$ for every $f$, and $\mathrm{CA}(f) = \Theta(k)$ here. CGLMSG23 |
| \(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity | \(\Theta(k)\) | 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}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity | \(\Theta(k)\) | 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(k),\ O(k^2)\) | From below $\mathrm{R}_0 = \Theta(k)$; from above $\mathrm{C}^0\mathrm{C}^1 = k^2$ [CGLMSG23]. No value of $\mathrm{Adv}$ is recorded for this family, so the gap stays open; the previous $\Theta(k)$ rested on the false inequality $\mathrm{CG} \le \mathrm{D}$. CGLMSG23 |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(k\) | Sandwiched: $\mathrm{C}(f) \le \mathrm{UC}(f) \le \mathrm{D}(f)$, with both ends $k$ here. Concretely the $2^k$ leaves of the walk tree are already an unambiguous certificate family. |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(k\) | Sandwiched: $\mathrm{C}_{\min}(f) \le \mathrm{UC}_{\min}(f) \le \mathrm{UC}(f)$, with both ends $k$ here -- navigation is completely certificate-uniform, so none of the four certificate variants can separate. |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(k\) | Sandwiched: $\mathrm{C}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$, with both ends $k$ here. The walk tree partitions the cube into $2^k$ monochromatic subcubes of codimension exactly $k$. |
| \(\mathrm{rank}(f)\) Decision tree rank | \(k\) putative | Prover-Delayer: whenever the Prover queries a node the walk has just reached, both answers are still live, so the Delayer scores; the Prover must resolve all $k$ walk nodes, and off-walk queries are answered for free. That gives $\mathrm{rank} \ge k$, and the complete depth-$k$ walk tree has rank exactly $k$. So $\mathrm{rank} = \mathrm{D}$ here -- the opposite extreme from \(\mathrm{OR}_n\), where $\mathrm{rank} = 1$ and $\mathrm{D} = n$. |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(\Theta(k)\) | Sandwiched: $\mathrm{CA}(f) \le \mathrm{RS}(f) \le \mathrm{R}(f)$, with both ends $\Theta(k)$ here. BenDavidKothari18 |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\Theta(k)\) | Sandwiched: $\mathrm{RS}(f) = O(\bar{\chi}(f))$ and $\bar{\chi}(f) = O(\mathrm{R}(f))$, with both ends $\Theta(k)$ here. GLSS19 |
| \(\chi(f)\) Conflict complexity | \(\Theta(k)\) | Sandwiched: $\chi(f) = \Omega(\mathrm{bs}(f))$ and $\chi(f) = O(\mathrm{R}(f))$, with both ends $\Theta(k)$ here. Li18 |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\Theta(k)\) | Sandwiched: $\bar{\chi}(f) = O(\mathrm{LR}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(k)$ here. BBGM22 |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\Theta(k)\) | Sandwiched: $\mathrm{LR}(f) = O(\mathrm{R}^{*}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(k)$ here. BBGM22 |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\Theta(k)\) | Sandwiched: $\mathrm{Q}(f) \le \mathrm{Q}_{0}(f) \le \mathrm{D}(f)$, with $\mathrm{Q}(f) = \Theta(k)$ and $\mathrm{D}(f) = k$ here. |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\Theta(\sqrt k)\) | $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{RC}(f)})$ for every $f$, and $\mathrm{RC}(f) = \Theta(k)$ here. Verifying a claimed walk is quadratically cheaper than following it. Aaronson08 |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(\Theta(k)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $k$ here. |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(\Theta(k)\)· | Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $k$ 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{N}_{p}(f)\) Noisy decision tree complexity | \(\Theta(k\log k)\) | Upper: $\mathrm{N}_p(f) = O(\mathrm{R}(f)\log \mathrm{R}(f))$ by repeating each query $O(\log k)$ times. Lower: $\mathrm{N}_p(f) = \Omega(\mathrm{I}(f)\log \mathrm{I}(f))$ [GLX26noisy] with $\mathrm{I}(f) = (k+1)/2$. The two meet, so navigation is a second natural family (after \(\oplus_n\)) where the repetition log factor is provably necessary. GLX26noisy FRPU94 |
| \(\mathrm{I}^{1}(f)\) Total L1 influence | \((k+1)/2\) | Boolean-valued, so equal to $\mathrm{I}(f)$. |
| \(\mathrm{MaxInf}(f)\) Maximum influence | \(1/2\) putative | The root is the most influential coordinate: flipping $x_0$ swaps the two subtrees, and the two bits they deliver differ with probability $1/2$ under the uniform input. A node at level $j$ is on the walk only with probability $2^{-j}$, so its influence is $2^{-j-1}$. Note this is $\Theta(1)$ while $\mathrm{MaxInf}$ is $O(\log n/n)$ for \(\mathrm{Tribes}_{w,s}\) -- navigation is as far from the KKL extremal shape as a balanced function can be. |
| \(\mathrm{Var}(f)\) Variance | \(1\) | Balanced: the leaf reached is a uniform data bit. |
| \(\mathrm{osss}(f)\) OSSS number | \(2\) putative | As for \(\mathrm{ADDR}_k\): $\mathrm{Var} = 1$ and $\mathrm{MaxInf} = 1/2$. |
| \(\mathrm{nsr}(f)\) Noise robustness | \(k/\ln 2\,(1+o(1)) = \Theta(k)\) putative | $(1-2\delta)(1-\delta)^{k-1} = \tfrac12$ gives $\delta^{*} = (\ln 2)/k\,(1+o(1))$: the walk survives until one of the $k$ navigation bits flips. Tight against $\mathrm{D} = k$. |
| \(\mathrm{spar}(f)\) Fourier sparsity | \(4^{k-1}\) putative | From the recursion $\mathrm{Nav}_k = \tfrac{L+R}{2} + x_0\tfrac{L-R}{2}$ in the $\pm1$ encoding, where $L$ and $R$ are $\mathrm{Nav}_{k-1}$ on disjoint variable sets and each is balanced (no constant term). The four groups of monomials have pairwise disjoint supports, so $\mathrm{spar}(k) = 4\,\mathrm{spar}(k-1)$ with $\mathrm{spar}(1) = 1$. |
| \(\hat{L}_1(f)\) Spectral norm | \(2^{k-1}\) putative | Same recursion: the halving is exactly cancelled by the doubling of the number of terms, giving $\hat L_1(k) = 2\,\hat L_1(k-1)$ from $\hat L_1(1) = 1$. So $\hat L_1 = 2^{\mathrm{D}-1}$, the maximum a depth-$\mathrm{D}$ tree can have. |
| \(\dim_{\mathbb{F}_2}(f)\) Fourier dimension | \(2^k - 1\) putative | Full. By the same recursion the support contains both $S$ and $S \cup \{0\}$ for every $S$ in the support of the left subtree, so their sum $\{0\}$ lies in the $\mathbb{F}_2$-span; inductively the span is everything. |
| \(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity | \(k\) putative | At most $\mathrm{D} = k$. For the lower bound, the recursion above makes every nonzero Fourier coefficient exactly $\pm 2^{-(k-1)}$, so the granularity is $k-1$ and the granularity bound $\mathrm{D}^{\oplus} \ge \mathrm{gran} + 1$ of [ChistopolskayaPodolskii18] gives $k$. Parity queries buy nothing at all here. ChistopolskayaPodolskii18 |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(\Theta(k)\) putative | Substituting one fresh variable $y_j$ for all nodes at level $j$ ($0 \le j \le k-2$), and the constant $\mathrm{parity}(b(v))$ for the bottom node $v$ reached by the path $b(v)$, turns $\mathrm{Nav}_k$ into $\mathrm{PARITY}_{k-1}$ -- the walk reads $y_0,\dots,y_{k-2}$ and then outputs their parity. Approximate degree cannot increase under a substitution of variables by variables and constants, so $\widetilde{\deg}(\mathrm{Nav}_k) \ge \widetilde{\deg}(\mathrm{PARITY}_{k-1}) = k-1$; and $\widetilde{\deg} \le \deg = k$. Navigation is therefore as hard for polynomials as it is for decision trees. |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\Theta(k)\) putative | Squeezed: $\widetilde{\deg}(f)/2 \le \mathrm{Q}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}(f) = \Theta(k)$ from the line above and $\mathrm{D}(f) = k$. So navigation admits no quantum speedup at all: the $k$ walk steps must be taken one after another even coherently, and the embedded \(\oplus_n\) certifies it. |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\Theta(k)\) | $\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(k)$ here. |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\Theta(k)\) | $\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(k)$ here. |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\Theta(k)\) | Squeezed: $\mathrm{Adv}^{\pm}(f) \le \mathrm{MAdv}(f) \le \mathrm{Q}_{\varepsilon}(f)$, with both ends $\Theta(k)$ here. |
| \(\lambda(f)\) Spectral sensitivity | \(\Theta(k)\) putative | Upper: $\lambda(f) \le \mathrm{s}(f) = k$. Lower: the spectral norm of a graph is at least its average degree, and the average degree of the sensitivity graph is exactly $\mathrm{I}(f) = (k+1)/2$. So $\lambda = \Theta(k)$, far above the $\sqrt{\deg} = \sqrt k$ floor of [Huang19]. |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(\Theta(k)\) | Squeezed: $\lambda(f) \le \mathrm{Adv}(f) \le \mathrm{Adv}^{\pm}(f)$, with $\lambda(f) = \Theta(k)$ and $\mathrm{Adv}^{\pm}(f) = \Theta(k)$ here. Note $\sqrt{\mathrm{C}^0\mathrm{C}^1} = k$, so the certificate barrier is met with equality and the positive-weight adversary is already optimal. |
| \(\mathrm{sdeg}(f)\) Sign degree | \(\Theta(k)\) putative | Upper: $2f-1$ sign-represents $f$ and has degree $\deg(f) = k$. Lower: sign-representation survives the substitution of the \(\widetilde{\deg}_{\varepsilon}(f)\) line, so $\mathrm{sdeg}(\mathrm{Nav}_k) \ge \mathrm{sdeg}(\mathrm{PARITY}_{k-1}) = k-1$. Contrast \(\mathrm{OR}_n\) and \(\mathrm{AND}_n\), where $\mathrm{sdeg} = 1$. |
| \(\widetilde{\deg}_{+}(f)\) One-sided approximate degree | \(\Theta(k)\) putative | Squeezed between $\mathrm{odeg}(\mathrm{PARITY}_{k-1}) = k-1$ (one-sided approximation also survives the substitution of the \(\widetilde{\deg}_{\varepsilon}(f)\) line) and $\widetilde{\deg}(f) = O(k)$. |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(\Theta(k)\) putative | Upper: $f$ itself is $0/1$-valued, so its exact multilinear polynomial is nonzero precisely on the $1$-inputs, giving $\mathrm{ndeg} \le \deg = k$. Lower: the property "nonzero exactly on the $1$-inputs" survives the substitution of the \(\widetilde{\deg}_{\varepsilon}(f)\) line, so $\mathrm{ndeg}(\mathrm{Nav}_k) \ge \mathrm{ndeg}(\mathrm{PARITY}_{k-1}) = k-1$. |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(\Theta(k)\) | $\mathrm{NQ}(f) = \lceil\mathrm{ndeg}(f)/2\rceil$ and $\mathrm{ndeg}(f) = \Theta(k)$ here. deWolf00 |
| \(\mathrm{rdeg}(f)\) Rational degree | \(\Theta(k)\) | $\mathrm{rdeg}(f) = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\} = \Theta(k)$ by the \(\mathrm{ndeg}(f)\) line (the complement is another navigation function, with the bottom level flipped), and $\mathrm{rdeg} \le \mathrm{C} = k$. |
| \(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree | \(\Theta(k)\) putative | Upper: $\mathrm{rdeg}_{\varepsilon} \le \mathrm{rdeg} = O(k)$. Lower: a rational approximation survives the substitution of the \(\widetilde{\deg}_{\varepsilon}(f)\) line, so $\mathrm{rdeg}_{\varepsilon}(\mathrm{Nav}_k) \ge \mathrm{rdeg}_{\varepsilon}(\mathrm{PARITY}_{k-1}) = \Omega(k)$. Postselection is useless here, unlike for \(\mathrm{MAJ}_n\) where it gives an exponential saving. MahadevdeWolf15 |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(\Theta(k)\) | $\mathrm{PostQ}_{\varepsilon}(f) = \Theta(\mathrm{rdeg}_{\varepsilon}(f)) = \Theta(k)$. MahadevdeWolf15 |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(\Theta(k)\) | Squeezed: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(k)$ here. |
| \(\mathrm{noisyR}(f)\) Noisy randomized query complexity | \(\Theta(k)\) | From $\mathrm{R}(f) = \Theta(k) \Rightarrow \mathrm{noisyR}(f) = \Theta(\mathrm{R}(f))$ -- see the \(\mathrm{noisyR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\) record. CKMPSS23 |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\Omega(k),\ O(k\log k)\) | Lower: $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Theta(k)$. Upper: run the depth-$k$ walk classically, repeating each query $O(\log k)$ times. The universal $O(\mathrm{arity})$ bound of [BNRdW05] is useless here, since the arity is $2^k-1$; whether the $\log k$ can be removed is exactly the open case of robust computation for very shallow, very wide functions. BNRdW05 |
| \(\deg_p(f)\) Mod-p degree | \(k\) putative | The recursion $\mathrm{Nav}_k = L + x_0(R-L)$ over $\mathbb{F}_p$: by induction $R$ carries a degree-$(k-1)$ monomial with coefficient $\pm1$ in variables disjoint from those of $L$, so $x_0$ times it survives with coefficient $\pm1 \ne 0$ for every $p$. Unlike \(\oplus_n\) and \(\mathrm{MAJ}_n\), navigation gets no discount in any characteristic. |
| \(\mathrm{Stab}_{\rho}(f)\) Noise stability | \(\rho\big(\tfrac{1+\rho}{2}\big)^{k-1}\) putative | From the $\pm1$ recursion $\mathrm{Nav}_k = \tfrac{L+R}{2} + x_0\tfrac{L-R}{2}$ on disjoint variable sets: the four monomial groups are disjoint, so $\mathrm{Stab}_\rho(k) = \tfrac{1+\rho}{2}\,\mathrm{Stab}_\rho(k-1)$ with $\mathrm{Stab}_\rho(1) = \rho$. Checked at $k=2$ against the multiplexer spectrum $\{\pm\tfrac12\}$ on four sets. |
| \(\mathrm{NS}_{\delta}(f)\) Noise sensitivity | \(\tfrac12\big(1-(1-2\delta)(1-\delta)^{k-1}\big)\) putative | The \(\mathrm{Stab}_{\rho}(f)\) line at $\rho = 1-2\delta$, where $\tfrac{1+\rho}{2} = 1-\delta$, through $\mathrm{NS}_\delta = \tfrac12(1-\mathrm{Stab}_{1-2\delta})$. So navigation becomes noise-sensitive at $\delta = \Theta(1/k)$ -- exponentially earlier in the input length $2^k-1$ than \(\mathrm{MAJ}_n\) does. |
| \(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity | \(k\) putative | Take the uniform (product) distribution. The output is determined only once every one of the $k$ walk nodes has been read, since the last of them is the output bit and the earlier ones are what identify it; so a tree of depth $< k$ leaves an unbiased bit and errs with probability $1/2$. Hence $\mathrm{D}^{\mathrm{prod}} \ge k$, matching $\mathrm{D}^{\mathrm{prod}} \le \mathrm{D} = k$. Product distributions are already worst case for navigation. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\Theta(k)\) | Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(k)$, and the \(\mathrm{D}^{\mathrm{prod}}(f)\) line shows the uniform distribution already forces the full depth $k$. Yao77 |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(k\) | Degenerate for Boolean functions: every input is critical and the only solution function is $f$ itself, so $\mathrm{cbs}(f) = \mathrm{bs}(f)$, which is $k$ here by the \(\mathrm{bs}(f)\) line. GoosPitassi14 |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\Theta(k)\) | 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(k)$. 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. 4 in total.
-
\(\mathrm{D}^{\mathrm{na}}(f_n) = 2^{\Omega(\mathrm{UC}(f_n))}\)from \(\mathrm{D}^{\mathrm{na}}(f) = 2^k - 1\) against \(\mathrm{UC}(f) = k\)
-
\(\mathrm{R}^{\mathrm{na}}(f_n) = 2^{\Omega(\mathrm{SP}(f_n))}\)from \(\mathrm{R}^{\mathrm{na}}(f) = \Theta(2^k)\) against \(\mathrm{SP}(f) = k\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) = 2^{\Omega(\mathrm{SP}(f_n))}\)from \(\mathrm{D}^{\mathrm{na}}(f) = 2^k - 1\) against \(\mathrm{SP}(f) = k\)
-
\(\mathrm{R}^{\mathrm{na}}(f_n) = 2^{\Omega(\mathrm{UC}(f_n))}\)from \(\mathrm{R}^{\mathrm{na}}(f) = \Theta(2^k)\) against \(\mathrm{UC}(f) = k\)
Separations it witnesses
-
$\mathrm{D}^{\mathrm{na}} = 2^{\mathrm{D}}-1$: exactly tight against the general bound, where $\mathrm{ADDR}_k$ is loose by a factor of two.
-
$\mathrm{R}^{\mathrm{na}} = 2^{\Theta(\mathrm{R})}$, against the general bound $\mathrm{R}^{\mathrm{na}} \le 2^{\mathrm{R}}-1$.
Cited as a witness by
-
\(\mathrm{D}^{\mathrm{na}}(\mathrm{Nav}_k) = 2^k - 1 = 2^{\mathrm{D}(\mathrm{Nav}_k)} - 1\)
-
\(\mathrm{R}^{\mathrm{na}}(\mathrm{Nav}_k) = \Theta(2^k),\quad \mathrm{R}(\mathrm{Nav}_k) = \Theta(k)\)