Q The Query Complexity Zoo
\(f_{\mathrm{Mei}}\)

Meiburg's tournament-subcube function

Refutes $\mathrm{bs} = O(\lambda^2)$: a total function with $\mathrm{bs} \ge \lambda^{2.127}$.

total composed arity: $N = 2{,}017{,}584^{\,d}$ bits ($d = 1$ is the base case)

Description

The indicator of a union of $k$ subcubes of the Boolean cube, indexed by the vertices of a doubly regular tournament; the remaining free choices in the construction are fixed by the Lovász Local Lemma. Composing the base function with itself gives an infinite family with $\lambda \to \infty$ and $\mathrm{bs} = \Omega(\lambda^{2.127})$.

Measure values

MeasureValueNotes
\(\mathrm{bs}(f)\) Block sensitivity \(14011^{\,d}\) The base case ($d=1$) is $\mathrm{bs} \ge 14011$, established -- and formally verified in Lean -- in [Meiburg26]. Block sensitivity is supermultiplicative under block composition (plant a $\mathrm{bs}$-maximising inner input in each copy and take unions of inner blocks across each outer block), so the $d$-fold composition has $\mathrm{bs} \ge 14011^{\,d}$. Exact, not merely a lower bound: $\mathrm{bs} \le \mathrm{C} = \mathrm{C}^0 = 14011^{\,d}$ by \(\mathrm{C}^0(f)\). Meiburg26
\(\lambda(f)\) Spectral sensitivity \(\le 89.0162^{\,d}\) The base case is $\lambda \le 89.0162$ [Meiburg26]. Spectral sensitivity is exactly multiplicative under block composition [ABKRT21] -- the sensitivity-graph adjacency operator of $f\circ g$ is a tensor-like product -- so the family has $\lambda \le 89.0162^{\,d}$. Against the $\mathrm{bs}$ entry this gives $\mathrm{bs} \ge \lambda^{\log 14011/\log 89.0162} = \lambda^{2.127}$ for every $d$. Meiburg26 ABKRT21
\(\mathrm{C}(f)\) Certificate complexity \(14011^{\,d}\) putative Squeezed exactly: $\mathrm{C} \ge \mathrm{bs} \ge \mathrm{bs}^0 = 14011^{\,d}$ from \(\mathrm{bs}^0(f)\), and $\mathrm{C} = \max\{\mathrm{C}^0,\mathrm{C}^1\} = \mathrm{C}^0 = 14011^{\,d}$ from \(\mathrm{C}^0(f)\) and \(\mathrm{C}^1(f)\).
\(\mathrm{fbs}(f)\) Fractional block sensitivity \(14011^{\,d}\) putative Squeezed exactly between $\mathrm{bs} = 14011^{\,d}$ and $\mathrm{C} = 14011^{\,d}$.
\(\mathrm{D}(f)\) Deterministic query complexity \(\ge 14011^{\,d}\) putative Immediate from $\mathrm{D} \ge \mathrm{C} \ge \mathrm{bs}$. Against $N = 2{,}017{,}584^{\,d}$ this is a very small fraction of the input, which is the point: the construction buys a large $\mathrm{bs}$ cheaply in $\lambda$, not in $N$.
\(\deg(f)\) Exact degree \(\le 7923.9^{\,d}\) putative $\lambda(f) \ge \sqrt{\deg(f)}$ [ABKRT21], so $\deg \le \lambda^2 \le 89.0162^{2d}$. In the other direction $\mathrm{bs} \le \deg^2$ gives $\deg \ge \sqrt{\mathrm{bs}} \ge 118.3^{\,d}$, so the degree is pinned into $[118.3^{\,d},\, 7923.9^{\,d}]$. Chaining the two is exactly where the $\mathrm{bs} = O(\lambda^4)$ upper bound comes from, and this family shows the truth is at least $\lambda^{2.127}$. ABKRT21
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\ge 118.3^{\,d}\) putative $\mathrm{Q} = \Omega(\sqrt{\mathrm{bs}})$, and $\mathrm{bs} \ge 14011^{\,d}$.
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\ge 14011^{\,d}\) putative $\mathrm{R} = \Omega(\mathrm{bs})$, and $\mathrm{bs} \ge 14011^{\,d}$.
\(\mathrm{s}(f)\) Sensitivity \(\Omega(10.87^{\,d})\) putative Chain the two directions of the degree: $\mathrm{bs} = O(\deg^2)$ [NS94] gives $\deg = \Omega(\sqrt{\mathrm{bs}})$, and $\mathrm{s} \ge \sqrt{\deg}$ [Huang19] then gives $\mathrm{s} = \Omega(\mathrm{bs}^{1/4}) = \Omega(14011^{\,d/4})$. Sensitivity of this family is therefore not pinned: anywhere from $\mathrm{bs}^{1/4}$ to $\mathrm{bs}$ is consistent with what is proved, and $\lambda \le \mathrm{s}$ says nothing here because only an upper bound on $\lambda$ is known. Huang19 NS94
\(\mathrm{FC}(f)\) Fractional certificate complexity \(14011^{\,d}\) putative $\mathrm{FC} = \mathrm{fbs}$ by LP duality, and \(\mathrm{fbs}(f)\) is pinned at $14011^{\,d}$.
\(\mathrm{RC}(f)\) Randomized certificate complexity \(\Theta(14011^{\,d})\) putative $\mathrm{RC} = \Theta(\mathrm{fbs})$ for every total $f$ (\(\mathrm{RC}(f)\) vs \(\mathrm{fbs}(f)\)), and \(\mathrm{fbs}(f)\) is pinned at $14011^{\,d}$.
\(\mathrm{EC}(f)\) Expectational certificate complexity \(14011^{\,d}\) putative Expectational certificate complexity satisfies $\mathrm{fbs} \le \mathrm{EC} \le \mathrm{C}$, and both ends are exactly $14011^{\,d}$.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity \(\ge 14011^{\,d}\) putative Immediate from $\mathrm{UC} \ge \mathrm{C} \ge \mathrm{bs}$.
\(\mathrm{SP}(f)\) Subcube partition complexity \(\ge 14011^{\,d}\) putative Every subcube of a monochromatic partition is a certificate for the inputs it contains, so $\mathrm{SP} \ge \mathrm{C} \ge \mathrm{bs}$.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(\ge 118.3^{\,d}\) putative An unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as the sum of the indicators of disjoint subcubes of codimension $\le w$, with no cancellation, so $\deg(f) \le \mathrm{UC}^0$ and $\deg(f) \le \mathrm{UC}^1$, hence $\deg \le \mathrm{UC}_{\min}$. With $\deg \ge \sqrt{\mathrm{bs}} \ge 118.3^{\,d}$ from the \(\deg(f)\) entry this is the bound; the alternative route $\mathrm{D} \le \mathrm{UC}_{\min}^2$ gives the same $\sqrt{14011^{\,d}}$.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(\ge 14011^{\,d}\) putative Non-adaptivity only costs more: $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D} \ge \mathrm{bs}$.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\ge 14011^{\,d}\) putative $\mathrm{R}_0 \ge \mathrm{R} = \Omega(\mathrm{bs})$; in fact $\mathrm{R}_0 \ge \mathrm{C} \ge \mathrm{bs}$ directly, since a zero-error algorithm must output a certificate.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\ge 14011^{\,d}\) putative Between $\mathrm{R}$ and $\mathrm{R}_0$, both $\ge 14011^{\,d}$ here.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\ge 14011^{\,d}\) putative Between $\mathrm{R}$ and $\mathrm{R}_0$, both $\ge 14011^{\,d}$ here.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\ge 14011^{\,d}\) putative $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \Omega(\mathrm{bs})$.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate \(\ge 14011^{\,d}\) putative Block sensitivity is supermultiplicative under composition, so $\mathrm{R}(f_d^{\circ m}) \ge \mathrm{bs}(f_d^{\circ m}) \ge \mathrm{bs}(f_d)^m$ for every $m$; taking $m$-th roots gives $\mathrm{R}^{*}(f_d) \ge \mathrm{bs}(f_d) \ge 14011^{\,d}$. The same computation makes $\mathrm{R}^{*}$ multiplicative along this family, since $f_d$ is itself the $d$-fold self-composition of the base function.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(14011^{\,d})\) putative $\mathrm{CA} = \Theta(\mathrm{fbs})$ for every total $f$ (\(\mathrm{CA}(f)\) vs \(\mathrm{fbs}(f)\)), and \(\mathrm{fbs}(f)\) is pinned at $14011^{\,d}$.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) \(\Theta(14011^{\,d})\) putative $\mathrm{CG}^{\mathrm{pub}} = \Theta(\mathrm{fbs})$ for every total $f$ (\(\mathrm{CG}^{\mathrm{pub}}(f)\) vs \(\mathrm{fbs}(f)\)), and \(\mathrm{fbs}(f)\) is pinned at $14011^{\,d}$.
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity \(\Theta(14011^{\,d})\) putative All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$, so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim. CGLMSG23
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity \(\Theta(14011^{\,d})\) putative All three of $\mathrm{CG}^{\mathrm{pub}}$, $\mathrm{CG}^{*}$ and $\mathrm{CG}^{\mathrm{ns}}$ collapse to $\Theta(\mathrm{CA})$, so this is the recorded $\mathrm{CG}^{\mathrm{pub}}$ value verbatim. CGLMSG23
\(\mathrm{CG}(f)\) Certificate game complexity (private coin) \(\Omega(14011^{\,d})\) putative The private-coin certificate game is at least $\max\{\mathrm{Adv}^2,\ \mathrm{R}_0,\ \mathrm{CA}\}$, and already $\mathrm{Adv}^2 \ge \mathrm{bs} \ge 14011^{\,d}$. Note $\mathrm{CG}$ is not capped by $\mathrm{D}$, so nothing here is squeezed from above.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(\Omega(14011^{\,d})\) putative The partition bound dominates fractional block sensitivity, $\mathrm{fbs} \le \mathrm{prt}_{\varepsilon}$, and $\mathrm{fbs} \ge \mathrm{bs} \ge 14011^{\,d}$.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(\Omega(14011^{\,d})\)· putative As \(\mathrm{prt}_{\varepsilon}(f)\); the relaxed partition bound still dominates $\mathrm{fbs}$ (the zoo's own observation that the [JainKlauck10] techniques survive dropping the completeness equality -- see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record).
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\ge 118.3^{\,d}\) putative $\mathrm{Q}_E \ge \mathrm{Q} \ge 118.3^{\,d}$; the degree route $\mathrm{Q}_E \ge \deg/2$ gives only $59.2^{\,d}$ and is weaker.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\ge 118.3^{\,d}\) putative $\mathrm{Q}_0 \ge \mathrm{Q} \ge 118.3^{\,d}$.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Omega(118.3^{\,d})\) putative Ambainis' basic adversary bound at a maximally block-sensitive input gives $\mathrm{Adv} \ge \sqrt{\mathrm{bs}}$ (\(\mathrm{bs}(f)\) vs \(\mathrm{Adv}(f)\)), i.e. $\ge 14011^{\,d/2}$. This is what supplies the $\mathrm{Q}$ entry, since $\mathrm{Adv} \le \mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$. Ambainis02
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Omega(118.3^{\,d})\) putative $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q}_{\varepsilon})$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} \ge 118.3^{\,d}$ here.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Omega(118.3^{\,d})\) putative $\gamma_2^{\alpha} = \Theta(\mathrm{Q}_{\varepsilon})$ for every $f$ (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)), and $\mathrm{Q} \ge 118.3^{\,d}$ here.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Omega(118.3^{\,d})\) putative Between $\mathrm{Adv}^{\pm}$ and $\mathrm{Q}_{\varepsilon}$, which agree up to constants; both are $\Omega(118.3^{\,d})$ here.
\(\mathrm{QC}(f)\) Quantum certificate complexity \(\Omega(118.3^{\,d})\) putative $\mathrm{QC}(f) = \Theta(\sqrt{\mathrm{fbs}(f)})$ for every $f$ (\(\mathrm{QC}(f)\) vs \(\mathrm{fbs}(f)\)), and $\mathrm{fbs} \ge \mathrm{bs} \ge 14011^{\,d}$.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\ge 14011^{\,d}\) putative For a Boolean-valued function the canonical answer is forced to be $f(x)$, so pseudo-determinism is free: $\mathrm{psD}(f) = \Theta(\mathrm{R}(f)) = \Omega(\mathrm{bs})$.
\(\mathrm{RS}(f)\) Sabotage complexity \(\ge 14011^{\,d}\) putative $\mathrm{RS} = \Omega(\mathrm{bs})$: at a maximally block-sensitive input, star out a uniformly random one of the disjoint sensitive blocks; every unstarred bit agrees with that input, so finding a $\ast$ is unstructured search over the blocks. No upper bound is available, since only a lower bound on $\mathrm{R}$ is known here.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(\Omega(118.3^{\,d})\) putative $\mathrm{bs} = O(\widetilde{\deg}^2)$ [NS94], so $\widetilde{\deg} = \Omega(\sqrt{\mathrm{bs}}) = \Omega(14011^{\,d/2})$. Above it sits $\widetilde{\deg} \le \deg \le 7923.9^{\,d}$ from the \(\deg(f)\) entry, so approximate degree is pinned into a factor-$67^{\,d}$ window. NS94
\(\mathrm{C}^0(f)\) 0-certificate complexity \(14011^{\,d}\) putative Exact, and the load-bearing cell for the whole entry. The base function is the indicator of a union of $k = 14011$ subcubes, so a $0$-input is certified by naming, for each subcube, one coordinate on which it is violated: $\mathrm{C}^0 \le 14011$ for $d=1$. Since $\mathrm{C}^1 \le 7149$ (the codimension of a single subcube), $\mathrm{C} = 14011$ at $d=1$, and certificate complexity is submultiplicative under composition ($\mathrm{C}^0(F\circ g^m) \le \mathrm{C}^0(F)\,\mathrm{C}(g)$: certify the outer coordinates, then each of the corresponding inner copies), giving $\mathrm{C}^0 \le 14011^{\,d}$. The matching lower bound is $\mathrm{C}^0 \ge \mathrm{bs}^0 \ge 14011^{\,d}$ (see \(\mathrm{bs}^0(f)\)). Consequently $\mathrm{bs} = \mathrm{fbs} = \mathrm{FC} = \mathrm{EC} = \mathrm{C} = 14011^{\,d}$ exactly, all of them being squeezed between $\mathrm{bs}^0$ and $\mathrm{C}$. Meiburg26
\(\mathrm{bs}^0(f)\) 0-block sensitivity \(14011^{\,d}\) putative Lower bound: [Meiburg26, Lemma 3.1] exhibits $14011$ disjoint sensitive blocks at the all-zeros input, which is a $0$-input, so $\mathrm{bs}^0 \ge 14011$ at $d=1$. Because the witnessing input is a $0$-input in every copy, the usual planting argument keeps the $0$-side: place the all-zeros input in every inner copy and take unions of inner blocks across each outer block, so $\mathrm{bs}^0(f^{\circ d}) \ge 14011^{\,d}$. Upper bound: $\mathrm{bs}^0 \le \mathrm{C}^0 \le 14011^{\,d}$ by \(\mathrm{C}^0(f)\). The two meet, so this is exact. Meiburg26
\(\mathrm{cbs}(S)\) Critical block sensitivity \(14011^{\,d}\) putative $\mathrm{cbs} = \mathrm{bs}$ for Boolean-valued problems [GoosPitassi14]. Here $\mathrm{bs}$ is in fact pinned exactly rather than merely bounded below: $14011^{\,d} \le \mathrm{bs}^0 \le \mathrm{bs} \le \mathrm{C} \le 14011^{\,d}$, using \(\mathrm{bs}^0(f)\) and \(\mathrm{C}^0(f)\). GoosPitassi14 Meiburg26
\(\mathrm{C}^1(f)\) 1-certificate complexity \(\le 7149\cdot 14011^{\,d-1}\) putative A $1$-input of the base function lies in one of the subcubes, whose codimension is $7149$, so $\mathrm{C}^1 \le 7149$ at $d = 1$. Composing, $\mathrm{C}^1(F\circ g^m) \le \mathrm{C}^1(F)\,\mathrm{C}(g)$ -- the outer $1$-certificate fixes both $0$s and $1$s, so the inner cost is the two-sided $\mathrm{C}(g) = 14011^{\,d-1}$. No lower bound is available: nothing in the construction forces a $1$-certificate to be large. Meiburg26
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(\le 7149\cdot 14011^{\,d-1}\) putative $\mathrm{C}_{\min} = \min\{\mathrm{C}^0,\mathrm{C}^1\} = \mathrm{C}^1$ here, since the \(\mathrm{C}^1(f)\) bound $7149\cdot 14011^{\,d-1} \approx 0.51\cdot 14011^{\,d}$ is strictly below the exact $\mathrm{C}^0 = 14011^{\,d}$. The relation $\mathrm{D} \le \mathrm{C}_{\min}\cdot\mathrm{C}$ therefore gives only $\mathrm{D} = O(14011^{2d})$, far above the recorded lower bound.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\ge 14011^{\,d}\) putative Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3} = \Theta(\mathrm{R}_{1/3})$, and $\mathrm{R} \ge \mathrm{bs} \ge 14011^{\,d}$. Yao77
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\ge 14011^{\,d}\) putative A noisy-query algorithm is in particular a randomized one, so $\mathrm{N}_p \ge \mathrm{R} \ge 14011^{\,d}$. The matching $O(\mathrm{R}\log \mathrm{R})$ upper bound [FRPU94] is vacuous here, since no upper bound on $\mathrm{R}$ is known. FRPU94
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Omega(118.3^{\,d})\) putative A robust quantum algorithm works in particular with a clean oracle, so $\mathrm{Q}^{\mathrm{rob}} \ge \mathrm{Q} = \Omega(\sqrt{\mathrm{bs}}) = \Omega(118.3^{\,d})$. The generic upper bound $\mathrm{Q}^{\mathrm{rob}} = O(\mathrm{Q}\log \mathrm{Q})$ [BNRdW05] is vacuous here, since no upper bound on $\mathrm{Q}$ is known. BNRdW05
\(\chi(f)\) Conflict complexity \(\Omega(14011^{\,d})\) putative Conflict complexity dominates block sensitivity, $\chi = \Omega(\mathrm{bs})$ [Li18], and $\mathrm{bs} = 14011^{\,d}$. Li18
\(\bar{\chi}(f)\) Max-conflict complexity \(\Omega(14011^{\,d})\) putative $\bar\chi \ge \chi = \Omega(\mathrm{bs}) = \Omega(14011^{\,d})$; the recorded $\mathrm{RS} \le \bar\chi$ [GLSS19] gives the same bound. GLSS19
\(\mathrm{LR}(f)\) Linearised randomized complexity \(\Omega(14011^{\,d})\) putative $\mathrm{LR} = \Omega(\bar\chi) = \Omega(\mathrm{bs}) = \Omega(14011^{\,d})$ [BBGM22]. Since $\mathrm{LR} \le \mathrm{R}$ and $\mathrm{R} \ge \mathrm{bs}$ is all that is known, the two lower bounds coincide. BBGM22
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\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})$.
\(\deg_2(f)\) Mod-2 degree \(\le 7923.9^{\,d}\) putative The unique multilinear representation of a Boolean function has integer coefficients, so reducing it mod $2$ computes $f$ over $\mathbb{F}_2$: $\deg_2 \le \deg \le 7923.9^{\,d}$ by the \(\deg(f)\) entry. No lower bound is available.
\(\mathrm{ndeg}(f)\) Nondeterministic degree \(\le 7923.9^{\,d}\) putative A polynomial computing $f$ exactly is nonzero exactly on $f^{-1}(1)$, so $\mathrm{ndeg} \le \deg \le 7923.9^{\,d}$. The competing bound $\mathrm{ndeg} \le \mathrm{C}^1$ of [IJKKKSWW23] gives $7149\cdot 14011^{\,d-1}$, which is worse for $d \ge 2$. IJKKKSWW23
\(\mathrm{rdeg}(f)\) Rational degree \(\le 7923.9^{\,d}\) putative $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\} \le \deg(f)$ [IJKKKSWW23], since $\deg(\bar f) = \deg(f)$, and $\deg \le 7923.9^{\,d}$. IJKKKSWW23
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity \(\le 3962^{\,d}\) putative $\mathrm{NQ} = \lceil \mathrm{ndeg}/2\rceil$ [deWolf03] with $\mathrm{ndeg} \le 7923.9^{\,d}$ from the \(\mathrm{ndeg}(f)\) entry. deWolf03
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree \(\le 7923.9^{\,d}\) putative $\mathrm{sdeg} \le \widetilde{\deg}_+ \le \widetilde{\deg} \le \deg \le 7923.9^{\,d}$ by the \(\deg(f)\) entry.
\(\mathrm{sdeg}(f)\) Sign degree \(\le 7923.9^{\,d}\) putative From $\mathrm{sdeg} \le \widetilde{\deg} \le \deg \le 7923.9^{\,d}$. Note the recorded $\widetilde{\deg} = \Omega(118.3^{\,d})$ does not transfer: sign degree can be arbitrarily far below approximate degree.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree \(\le 7923.9^{\,d}\) putative $\mathrm{rdeg}_{1/3} \le \widetilde{\deg} \le \deg \le 7923.9^{\,d}$.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(O(7923.9^{\,d})\) putative $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon)$ [MahadevdeWolf15], bounded by the \(\mathrm{rdeg}_{\varepsilon}(f)\) entry. Contrast the recorded $\mathrm{Q} = \Omega(118.3^{\,d})$: post-selection is not known to help or hurt on this family. MahadevdeWolf15

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.

Separations it witnesses

Cited as a witness by

Notes

Numerical (non-rigorous) evidence in the same paper suggests a 1255-variable relative attains exponent $\approx 2.20$, and a 30-variable instance already beats exponent $2$ with an exactly computable $\lambda$. The rigorous exponent $2.12697356\ldots$ (approximately $2.12$, usually quoted as $2.127$) is weaker than the current $2.1308255793978239\ldots$ lower endpoint supplied by Prove2Me’s refined tournament sensitivity family [Prove2MeSensitivity26]. The numerical $2.20$ value is not an established lower bound.