Q The Query Complexity Zoo
\(\mathrm{cjdeg}_{\varepsilon}(f)\)

Conical junta degree

Least d such that f is approximated by a non-negative combination of width-d conjunctions (a conical junta).

also written: two-sided approximate non-negative degree, conical junta / non-negative-combination degree

Definition

A conical junta of width $d$ is a non-negative linear combination $h = \sum_C \alpha_C \, C$ of conjunctions $C$ of at most $d$ literals, with all $\alpha_C \ge 0$. The two-sided approximate non-negative degree $\mathrm{cjdeg}_\varepsilon$ is the least $d$ for which some width-$d$ conical junta $\varepsilon$-approximates $f$ pointwise. Non-negativity makes this a larger measure than approximate degree; it also upper-bounds randomized query complexity's LP relaxation and, in the usual regimes, exceeds $\mathrm{Q}$.

Parameters

\(\varepsilon\) (eps) default \(1/3\)

Basic facts

  • $\widetilde{\deg}_\varepsilon(f) \le \mathrm{cjdeg}_\varepsilon(f)$ (drop non-negativity).
  • Usually $\mathrm{cjdeg}(f) \ge \mathrm{Q}(f)$, so a separation of $\mathrm{Q}$ from $\mathrm{cjdeg}$ is strictly stronger than one from $\widetilde{\deg}$.
  • Total search problems: $\mathrm{Q}(S)$ can be exponentially larger than $\mathrm{cjdeg}(S)$ [BenDavidKundu24search]; previously not even a separation from $\mathrm{R}(S)$ was known.
  • The dual object is a conical junta certificate, which is the LP-dual view of randomized query lower bounds (the "partition bound" family).

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{cjdeg}_{\varepsilon}(f)\). “\(\mathrm{cjdeg}_{\varepsilon}(f)\) in terms of it” is the pair with \(\mathrm{cjdeg}_{\varepsilon}(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.

Other measure \(\mathrm{cjdeg}_{\varepsilon}(f)\) in terms of it It in terms of \(\mathrm{cjdeg}_{\varepsilon}(f)\)
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree total2,4 partial2,? derived open pair → total1,1 partial1,1 open pair →
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity total2,4 partial2,? relation2,? open pair → total1,4 partial1,? relationexp,? derived open pair →
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total1,1 partial1,1 relation1,1 open pair → total1,4 partial1,? relationexp,? derived open pair →
\(\mathrm{Adv}(f)\) Positive-weights adversary bound total2,6 partial∞ relation∞ derived open pair → total1,2 partial1,2 relation1,? derived open pair →
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound total1,3 partial1,? relation1,? derived open pair → total1,4 partial1,? relation1,? derived open pair →

The 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(\Theta(n)\)· putative Upper: $\mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f) = n$, the $1$-leaves of the caterpillar being disjoint conjunctions. Lower: let $h = \sum_C \alpha_C C$ be a width-$d$ conical junta with $|h - \vee_n| \le 1/3$ pointwise. A conjunction with $C(e_i) = 1$ either has all its literals negative -- and then $C(0^n) = 1$ as well -- or has exactly one positive literal, necessarily $x_i$. Conjunctions of the first kind contribute at most $h(0^n) \le 1/3$ to each of the $n$ points $e_i$, so writing $A$ for the total weight of the conjunctions with exactly one positive literal, $2n/3 \le \sum_i h(e_i) \le n/3 + A$, i.e. $A \ge n/3$. Now evaluate under the product measure that sets each bit to $1$ with probability $1/d$: each such $C$ has expectation at least $\tfrac1d(1-\tfrac1d)^{d-1} \ge \tfrac{1}{ed}$, while $\mathbb{E}[h] \le 4/3$, so $A \le 4ed/3$ and $d \ge n/(4e)$. Non-negativity therefore costs a quadratic blow-up over $\widetilde{\deg} = \Theta(\sqrt n)$.
AND total \(\Theta(n)\)· putative Upper: $\mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f) = n$. Lower: let $h = \sum_C \alpha_C C$ be a width-$d$ conical junta with $|h - \wedge_n| \le 1/3$ pointwise. The conjunctions that evaluate to $1$ at $1^n$ are exactly the all-positive ones, so $\sum_{C \text{ positive}} \alpha_C = h(1^n) \ge 2/3$; an all-positive $C$ still evaluates to $1$ at $1^n - e_i$ unless $x_i$ is one of its at most $d$ literals, whence $\sum_i h(1^n - e_i) \ge \sum_{C \text{ positive}} \alpha_C\,(n - |C|) \ge (n-d)\tfrac23$. Every $1^n - e_i$ is a $0$-input, so the left-hand side is at most $n/3$, giving $d \ge n/2$. Non-negativity thus wipes out the $\widetilde{\deg} = \Theta(\sqrt n)$ saving, and it does so even though $\mathrm{sdeg}(\wedge_n) = 1$.
PARITY total \(n\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
MAJORITY total \(\Theta(n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
Threshold total \(\Theta(n)\)· putative Restricting $k-1$ variables to $1$ turns $\mathrm{THR}^n_k$ into $\vee_{n-k+1}$, and restricting $n-k$ variables to $0$ turns it into $\wedge_k$. A conical junta restricts to a conical junta of no larger width, so the \(\mathrm{OR}_n\) and \(\mathrm{AND}_n\) lower bounds give $\mathrm{cjdeg} = \Omega(\max\{k,\ n-k+1\}) = \Omega(n)$; and $\mathrm{cjdeg}_{\varepsilon} \le \mathrm{D} = n$. So, uniformly in $k$, non-negativity destroys the $\widetilde{\deg} = \Theta(\sqrt{k(n-k+1)})$ saving -- at $k=1$ this is a quadratic gap.
Symmetric functions (general) total \(\Theta(n)\)· putative Fix a jump $k$, so $f_k \ne f_{k+1}$. Restricting $k$ variables to $1$ leaves a function $g$ on $m = n-k$ variables with $g(0^m) \ne g(e_i)$ for every $i$; restricting $n-k-1$ variables to $0$ leaves a function on $k+1$ variables with the corresponding property at $1^{k+1}$. In either case the \(\mathrm{OR}_n\) / \(\mathrm{AND}_n\) argument applies verbatim -- a width-$d$ conjunction can separate $0^m$ from at most $d$ of the $e_i$ -- and a conical junta restricts to a conical junta of no larger width, so $\mathrm{cjdeg} = \Omega(\max\{k+1,\ n-k\}) = \Omega(n)$. Upper: $\mathrm{cjdeg}_{\varepsilon} \le \mathrm{D} = n$. So non-negativity destroys Paturi's $\widetilde{\deg} = \Theta(\sqrt{n(n-\Gamma(f))})$ saving for every symmetric $f$, however small $\Gamma$ is.
EXACT-HALF total \(\Theta(n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
ODD-MAX-BIT total \(\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)$.
ADDRESS / multiplexer total \(\Theta(k)\) Squeezed: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(k)$ here.
Binary tree navigation total \(\Theta(k)\) Squeezed: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(k)$ here.
TRIBES total \(\Omega(n/\log n),\ O(n)\)· putative Upper: $\mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f) = n$. Lower: fixing $w-1$ variables of each tribe to $1$ leaves $\vee_s$ on the remaining $s = \Theta(n/\log n)$ variables, and a conical junta restricts to a conical junta of no larger width, so the \(\mathrm{OR}_n\) line gives $\mathrm{cjdeg} = \Omega(s)$. This beats the $\widetilde{\deg}_{\varepsilon} = \Theta(\sqrt n)$ lower bound; whether the truth is $\Theta(n)$ is open.
AND-OR tree (depth 2) total \(\Omega(n),\ O(n^2)\) Conical junta degree sits between approximate degree and randomized complexity, $\widetilde{\deg}_\varepsilon \le \mathrm{cjdeg}_\varepsilon \le \mathrm{R}_\varepsilon$, i.e. $\Omega(n)$ and $O(n^2)$ here. Closing the window would decide whether the non-negativity constraint costs anything on the canonical $\mathrm{Q}$-vs-$\mathrm{R}$ example.
NAND tree (balanced AND-OR formula) total \(\tilde\Theta\!\big(N^{\,0.753\ldots}\big)\) The conical junta composition theorem gives $\tilde\Omega(N^{0.753\ldots})$, answering a question of Beame and Lawry; the matching upper bound is $\mathrm{cjdeg} \le \mathrm{R}$. So on the binary AND-OR tree the nonnegative LP is already tight up to logs -- unlike $\widetilde{\deg} = \Theta(\sqrt N)$, which is quadratically off. GoosJayram16
Recursive MAJORITY-of-3 total \(\Omega(2.59^{\,d}),\ O(2.64944^{\,d})\) The Goos-Jayram conical junta bound $\Omega(2.59^d)$ is, as of writing, also the best known lower bound on $\mathrm{R}$ itself -- the nonnegative LP is where all recent progress on recursive majority has come from. Upper bound inherited from $\mathrm{cjdeg} \le \mathrm{R}$. GoosJayram16 MNSSTX16
Kushilevitz's function (iterated) total \(\Omega(\sqrt N),\ O(N)\) Sandwiched: $\widetilde{\deg}_{\varepsilon} \le \mathrm{cjdeg}_{\varepsilon} \le \mathrm{R}_{\varepsilon}$, with $\widetilde{\deg} = \Omega(\sqrt N)$ and $\mathrm{R} = \Theta(N)$ here.
Rubinstein's function total \(\Omega(\sqrt N),\ O(N)\) Sandwiched: $\widetilde{\deg}_{\varepsilon} \le \mathrm{cjdeg}_{\varepsilon} \le \mathrm{R}_{\varepsilon}$, with $\widetilde{\deg} = \Theta(\sqrt N)$ and $\mathrm{R} = \Theta(N)$ here. Non-negativity is exactly what could close this quadratic window, as it does on \(\bar{\wedge}\text{-tree}\).
Ambainis-Sun function total \(\Omega(\sqrt N),\ O(N)\) Sandwiched: $\widetilde{\deg}_{\varepsilon} \le \mathrm{cjdeg}_{\varepsilon} \le \mathrm{R}_{\varepsilon}$, with $\widetilde{\deg} = \Omega(\sqrt N)$ and $\mathrm{R} = \Theta(N)$ here.
AND composed with NOT-EXACT-HALF total \(\widetilde\Omega(n^{3/2}),\ O(n^2)\) Sandwiched: $\widetilde{\deg}_{\varepsilon} \le \mathrm{cjdeg}_{\varepsilon} \le \mathrm{R}_{\varepsilon}$, with $\widetilde{\deg} = \tilde\Theta(n^{3/2})$ and $\mathrm{R} = \Theta(n^2)$ here.
Meiburg's tournament-subcube function total \(\Omega(118.3^{\,d})\) putative Conical junta degree dominates approximate degree, $\widetilde{\deg}_\varepsilon \le \mathrm{cjdeg}_\varepsilon$, and the recorded $\widetilde{\deg} = \Omega(118.3^{\,d})$.
Pointer functions total \(\widetilde\Omega(n^{1/4}),\ \widetilde O(n)\) Variant $f_{2m,m}$: a depth-$\mathrm{D}$ decision tree is an exact conical junta of width $\mathrm{D}$ (one conjunction per accepting path, all coefficients $1$), so $\mathrm{cjdeg}\le\mathrm{D}=\widetilde O(n)$; the floor is $\mathrm{cjdeg}\ge\widetilde{\deg}\ge\Omega(\sqrt{\mathrm{bs}})=\widetilde\Omega(n^{1/4})$.
Cheat-sheet functions total \(\widetilde\Omega(n^{1/4}),\ \widetilde O(n)\) Ceiling: a depth-$\mathrm{D}$ decision tree is an exact conical junta of width $\mathrm{D}$ (one conjunction per accepting path, all coefficients $1$), so $\mathrm{cjdeg}\le\mathrm{D}=\widetilde O(n)$. Floor: $\mathrm{cjdeg}\ge\widetilde{\deg}=\widetilde\Omega(n^{1/4})$. Since $\mathrm{Q}=\widetilde\Theta(n)$, pinning this cell at the bottom of its range would give a $\mathrm{Q}$-vs-$\mathrm{cjdeg}$ separation strictly stronger than the recorded $\mathrm{Q}$-vs-$\widetilde{\deg}$ one.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^{3/4})\) Squeeze: $\mathrm{cjdeg}\ge\widetilde{\deg}=\widetilde\Omega(n^{3/4})$ (dropping non-negativity can only lower the degree).
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{2/3}),\ \widetilde O(n^2)\) Floor $\mathrm{cjdeg}\ge\widetilde{\deg}=\widetilde\Theta(n^{2/3})$; ceiling $\mathrm{cjdeg}\le\mathrm{D}=\widetilde\Theta(n^2)$, since a depth-$\mathrm{D}$ decision tree is an exact conical junta of width $\mathrm{D}$.
Gilmer-Saks-Srinivasan functions total \(\Omega(\sqrt n),\ O(n^2)\) Floor $\mathrm{cjdeg}\ge\widetilde{\deg}=\Omega(\sqrt n)$; ceiling $\mathrm{cjdeg}\le\mathrm{D}=\Theta(n^2)$, a depth-$\mathrm{D}$ tree being an exact conical junta of width $\mathrm{D}$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(n^{1/4}),\ \widetilde O(n)\) Floor $\mathrm{cjdeg}\ge\widetilde{\deg}\ge\Omega(\sqrt{\mathrm{bs}})=\widetilde\Omega(n^{1/4})$; ceiling $\mathrm{cjdeg}\le\mathrm{D}=\widetilde\Theta(n)$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/6}),\ \widetilde O(n^{2/3})\) Floor $\mathrm{cjdeg}\ge\widetilde{\deg}\ge\Omega(\sqrt{\mathrm{bs}})=\widetilde\Omega(n^{1/6})$; ceiling $\mathrm{cjdeg}\le\mathrm{D}=\widetilde\Theta(n^{2/3})$.
Ambainis' exact-quantum function total \(\Omega(3^{d/2}),\ O(3^d)\) Floor: dropping non-negativity gives $\mathrm{cjdeg}\ge\widetilde{\deg}=\Omega(\sqrt{\mathrm{bs}})=\Omega(3^{d/2})$. Ceiling: a depth-$\mathrm{D}$ decision tree is already an exact conical junta -- one width-$\le\mathrm{D}$ conjunction per accepting path, all coefficients $1$ -- so $\mathrm{cjdeg}\le\mathrm{D}=3^d$.
FORRELATION partial \(\widetilde O(\sqrt n)\) Sandwiched: $\widetilde{\deg} \le \mathrm{cjdeg}_\varepsilon \le \mathrm{R}_\varepsilon$, i.e. between $O(1)$ and $\widetilde\Theta(\sqrt n)$.
k-FORRELATION partial \(\widetilde O\!\big(n^{1-1/k}\big)\) Sandwiched between $\widetilde{\deg} = O(k)$ and $\mathrm{R}_\varepsilon = \widetilde\Theta(n^{1-1/k})$.
Simon's problem partial \(O(2^{n/2})\) Sandwiched between $\widetilde{\deg} = O(n)$ and $\mathrm{R}_\varepsilon = \Theta(2^{n/2})$.
Deutsch-Jozsa partial \(\Theta(1)\) Sandwiched between $\widetilde{\deg} = 2$ and $\mathrm{R} = O(1)$.
Bernstein-Vazirani partial \(O(n)\) $\mathrm{cjdeg}_\varepsilon \le \mathrm{R}_\varepsilon = O(n)$.
Unstructured search (relation) relation \(O(n)\) $\mathrm{cjdeg}_\varepsilon \le \mathrm{R}_\varepsilon = O(n)$. The usual lower bound $\mathrm{cjdeg} \ge \widetilde{\deg}$ is unavailable: approximate degree is not defined for a relation.
FIND-1 under a density promise relation \(\Theta(1)\) Squeezed by $\mathrm{cjdeg} \le \mathrm{R} = O(1)$ and by $\mathrm{cjdeg} \ge 1$ for a non-constant problem.
Approximate Hamming weight relation \(\Theta(1)\) Squeezed by $\mathrm{cjdeg} \le \mathrm{R} = \Theta(1)$ and $\mathrm{cjdeg} \ge 1$.
SearchCNF relation \(\Theta(1)\) Squeezed by $\mathrm{cjdeg} \le \mathrm{R} = \Theta(1)$ and $\mathrm{cjdeg} \ge 1$.
Gap-Majority partial \(O(\min(n, 1/\delta^2))\) Between $\widetilde{\deg} = \Theta(\min(n,1/\delta))$ and $\mathrm{R} = \Theta(\min(n,1/\delta^2))$; the conical-junta relaxation is not known to close that quadratic gap here.
Gap-Majority at constant gap partial \(O(1)\) Between $\widetilde{\deg}$ and $\mathrm{R}$.
Parity-labelled FIND-1 partial \(\Theta(1)\) Between $1$ and $\mathrm{R} = O(1)$.
Approximate index partial \(O(\sqrt{k\log k})\) $\mathrm{cjdeg}_\varepsilon \le \mathrm{R}_\varepsilon$.
Collision problem partial \(O(\sqrt n)\) Between $\widetilde{\deg} = \Theta(n^{1/3})$ and $\mathrm{R} = \Theta(\sqrt n)$.
Element distinctness total \(\Theta(n)\) putative Upper: a randomized algorithm of cost $\mathrm{R}$ is a distribution over leaves, i.e. a width-$\mathrm{R}$ conical junta, so $\mathrm{cjdeg} \le \mathrm{R} = O(n)$. Lower: restrict to $x_i \in \{0,i\}$, which sends every block literal to a $z$-literal or a constant and hence maps conical juntas to conical juntas of no greater width. Let $h = \sum_C \alpha_C C$ have width $d$ and approximate "at most one $z_i = 1$". Only all-negative conjunctions fire at $z = 0$, so those carry total weight $\ge 2/3$; each such $C$, of support $S$, also fires at a weight-$2$ input $e_i + e_j$ unless $S$ meets $\{i,j\}$, which for a uniformly random pair happens with probability $\le 2d/n$. Averaging, $1/3 \ge (2/3)(1 - 2d/n)$, so $d \ge n/4$. This separates $\mathrm{cjdeg} = \Theta(n)$ from $\widetilde{\deg} = \Theta(n^{2/3})$: non-negativity costs the whole gap.
Ambainis-Belovs function partial \(O(n)\) Sandwiched between $\widetilde{\deg} = O(1)$ and $\mathrm{R} = O(n)$; nothing pins it, which is the point -- conflict-degree tracks $\mathrm{R}$, not $\widetilde{\deg}$, and this function separates the two.
Ben-David-Kundu total search problems relation \(O(\log^7 n)\) Corollary 32: the same polynomials are conical juntas, so the two-sided bounded non-negative degree $\widetilde{\deg}^+_2$ is also $O(t\log^2 n) = O(\log^7 n)$. This is the strong form of the result: $\mathrm{cjdeg}$ is normally at least $\mathrm{R}$, and even an $\mathrm{R}$-vs-$\mathrm{cjdeg}$ separation for a total search problem was open. BenDavidKundu24search
Surjectivity total \(\tilde\Omega(n^{3/4}),\ O(n)\) $\widetilde{\deg}_\varepsilon\le\mathrm{cjdeg}_\varepsilon\le\mathrm{R}_\varepsilon$ (\(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\), \(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), with $\widetilde{\deg}=\tilde\Theta(n^{3/4})$ [BKT18] and $\mathrm{R}=\Theta(n)$. Closing this would settle whether the conical junta relaxation sees the $n^{3/4}$ barrier or the true randomized cost.
$k$-distinctness total \(\tilde\Omega\!\big(n^{3/4-1/(4k)}\big),\ O(n)\) $\widetilde{\deg}_\varepsilon\le\mathrm{cjdeg}_\varepsilon\le\mathrm{R}_\varepsilon$ (\(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\), \(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), taking the lower end from the recorded approximate degree and the upper end from $\mathrm{R}=\Theta(n)$.
Triangle finding total \(\Omega(m),\ O(m^2)\) $\widetilde{\deg}_\varepsilon\le\mathrm{cjdeg}_\varepsilon\le\mathrm{R}_\varepsilon$ (\(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\widetilde{\deg}_{\varepsilon}(f)\), \(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), with $\widetilde{\deg}=\Omega(m)$ and $\mathrm{R}=\Theta(m^2)$.
Welded trees relation \(\widetilde O(2^{n/2})\) $\mathrm{cjdeg}_\varepsilon\le\mathrm{R}_\varepsilon=\widetilde O(2^{n/2})$ (\(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\), relation setting).
Local search on the hypercube relation \(O(2^{n/2}\sqrt n)\) $\mathrm{cjdeg}_\varepsilon\le\mathrm{R}_\varepsilon$ (\(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\), relation setting).
Local search on the grid relation \(O(k^{d/2})\ (d \ge 4)\) $\mathrm{cjdeg}_\varepsilon\le\mathrm{R}_\varepsilon$ (\(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\), relation setting).
Fourier fishing relation \(O(N)\) $\mathrm{cjdeg}_\varepsilon\le\mathrm{R}_\varepsilon\le\mathrm{D}=N$ (\(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\), relation setting).
Ordered search partial \(\Omega\!\big(\tfrac{\log n}{(\log\log n)^2}\big),\ O(\log n)\) Squeezed between $\widetilde{\deg}$ and $\mathrm{R}_{\varepsilon}$, so it inherits the [BunVoronova23] window exactly. Worth contrasting with $\deg = 1$: imposing non-negativity on top of boundedness changes nothing further here, but dropping boundedness collapses the measure completely.
Tseitin search on an expander relation \(O(n)\) $\mathrm{cjdeg}_\varepsilon\le\mathrm{R}_\varepsilon=O(n)$ (\(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\), relation setting -- the version used for total search problems).
Inner product mod 2 total \(\Theta(n)\) Sandwiched: $\mathrm{sdeg}(f) \le \mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{sdeg}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
Minsky-Papert one-in-a-box total \(\Omega(m^{3/2}),\ O(m^3)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f)$ (\(\widetilde{\deg}_{\varepsilon}(f)\) vs \(\mathrm{cjdeg}_{\varepsilon}(f)\), \(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), with $\widetilde{\deg} = \Theta(m^{3/2})$ and $\mathrm{R} = \Theta(m^3)$. On the balanced \(\bar{\wedge}\text{-tree}\) the upper end is known to be attained; here it is open which end is the truth.
Sink of a tournament total \(\Omega(\sqrt m),\ O(m)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f)$ (\(\widetilde{\deg}_{\varepsilon}(f)\) vs \(\mathrm{cjdeg}_{\varepsilon}(f)\), \(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), with $\widetilde{\deg} \in [\Omega(\sqrt m), O(m)]$ and $\mathrm{R} = \Theta(m)$. The window is exactly the open window on $\widetilde{\deg}$ -- pinning the approximate degree of SINK would pin this too.
Scorpion graphs total \(\Omega(\sqrt m),\ O(m)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f)$, with $\widetilde{\deg} \in [\Omega(\sqrt m), O(m)]$ and $\mathrm{R} = \Theta(m)$; the window is inherited wholesale from the open window on $\widetilde{\deg}$.
Graph connectivity total \(\Omega(m),\ O(m^2)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{cjdeg}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f)$ (\(\widetilde{\deg}_{\varepsilon}(f)\) vs \(\mathrm{cjdeg}_{\varepsilon}(f)\), \(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), with $\widetilde{\deg} \in [\Omega(m), O(m^{3/2})]$ and $\mathrm{R} = \Theta(m^2)$. Even pinning $\widetilde{\deg}$ would leave a $\sqrt N$ window here.