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
| Measure | Value | Notes |
|---|---|---|
| \(\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.
-
\(\mathrm{bs}^0(f_n) = \Omega\big(\lambda(f_n)^{2.127}\big)\)from \(\mathrm{bs}^0(f) = 14011^{\,d}\) against \(\lambda(f) = \le 89.0162^{\,d}\)
-
\(\mathrm{RS}(f_n) = \Omega\big(\lambda(f_n)^{2.127}\big)\)from \(\mathrm{RS}(f) = \ge 14011^{\,d}\) against \(\lambda(f) = \le 89.0162^{\,d}\)
-
\(\mathrm{CG}^{*}(f_n) = \Omega\big(\lambda(f_n)^{2.127}\big)\)from \(\mathrm{CG}^{*}(f) = \Theta(14011^{\,d})\) against \(\lambda(f) = \le 89.0162^{\,d}\)
-
\(\mathrm{CG}^{\mathrm{ns}}(f_n) = \Omega\big(\lambda(f_n)^{2.127}\big)\)from \(\mathrm{CG}^{\mathrm{ns}}(f) = \Theta(14011^{\,d})\) against \(\lambda(f) = \le 89.0162^{\,d}\)
Separations it witnesses
-
$\mathrm{bs}(f_n) = \Omega(\lambda(f_n)^{2.12697})$, an earlier rigorous separation of exponent approximately $2.12$, refuting the quadratic bound asked about in [ABKRT21]. The main result is formally verified in Lean.
Cited as a witness by
-
\(\mathrm{bs}(f_d)=\Omega(\lambda(f_d)^{2.12697})\)
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.