\(\mathrm{DJ}_n\)
Deutsch-Jozsa
Exact quantum: 1 query vs $N/2+1$ deterministic queries (but $\mathrm{R}=O(1)$).
partial quantum arity: $N=2^n$ bits
Description
Promise: $x$ is constant or exactly balanced. Decide which.
Formal definition
$\mathrm{DJ}(x) = 0$ if $|x| = 0$ or $|x| = N$; $=1$ if $|x| = N/2$; undefined otherwise.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(1\) | DeutschJozsa92 |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(N/2+1\) | |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(O(1)\) | Two random samples suffice with bounded error -- so this is an exact-quantum-vs-deterministic separation only. |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(1\) | $\mathrm{Q} \le \mathrm{Q}_E = 1$, and one query is needed. |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(1\) | Same: $\mathrm{Q} \le \mathrm{Q}_0 \le \mathrm{Q}_E = 1$. |
| \(\mathrm{s}(f)\) Sensitivity | \(0\) putative | For $N \ge 4$ no single flip stays inside the promise: a constant input becomes weight $1$ or $N-1$, a balanced one weight $N/2 \pm 1$. So $\mathrm{s}^0 = \mathrm{s}^1 = 0$ while $\mathrm{D} = N/2+1$. The extreme illustration of why sensitivity says nothing about partial functions. |
| \(\mathrm{bs}(f)\) Block sensitivity | \(2\) putative | At $0^N$ the sensitive blocks are exactly the $\binom{N}{N/2}$ half-sized sets, and two disjoint halves fit; at a balanced $x$ they are exactly $\mathrm{supp}(x)$ and its complement, again two disjoint blocks. Three disjoint blocks of size $N/2$ do not fit in $N$ coordinates, so $\mathrm{bs}^0=\mathrm{bs}^1=2$. |
| \(\mathrm{fbs}(f)\) Fractional block sensitivity | \(2\) putative | The fractional relaxation buys nothing: every sensitive block has size exactly $N/2$, so a feasible weighting has $\tfrac N2\sum_B w_B = \sum_i \mathrm{load}(i) \le N$. |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(N/2+1\) putative | Fixing $|S|$ coordinates to $0$ still admits a balanced input whenever $|S| \le N/2$, so a $0$-certificate needs $N/2+1$ zeros -- and that many suffice. |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(2\) putative | Every other domain point consistent with "one $0$ here, one $1$ there" is balanced, hence also a $1$-input. Nothing needs to be pinned down beyond killing the two constants. |
| \(\mathrm{C}(f)\) Certificate complexity | \(N/2+1\) putative | From $\mathrm{C}^0$. With $\mathrm{fbs}=2$ this is a much cleaner unbounded $\mathrm{C}$-vs-$\mathrm{fbs}$ witness than any total function can give. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(2\) putative | Attained on the balanced inputs. |
| \(\deg(f)\) Exact degree | \(2\) putative | On the promise $f$ is the symmetric function $t \mapsto [t = N/2]$ of $t=|x|$ restricted to $t \in \{0, N/2, N\}$, and $(1 - (1-2t/N)^2)$ interpolates it. Degree $1$ is impossible since $p(0)=p(N)=0$ forces $p \equiv 0$. So $\mathrm{deg} = 2 = 2\,\mathrm{Q}_E$: Deutsch-Jozsa makes $\mathrm{deg} \le 2\mathrm{Q}_E$ tight. |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(2\) putative | Symmetrise: a degree-$1$ univariate with $|q(0)|,|q(N)| \le 1/3$ has $q(N/2) = \tfrac12(q(0)+q(N))$, which cannot reach $2/3$. So approximation does not help either. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(N/2+1\) putative | Adaptivity is worthless here: any fixed $N/2+1$ positions contain a $0$ and a $1$ of every balanced input (which has exactly $N/2$ of each), so reading them decides. And $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$. |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(N/2+1\) putative | Zero error means every run ends on a certificate, and on a constant input that is $N/2+1$ queries; $\mathrm{R}_0 \le \mathrm{D}$ gives the match. So the $\mathrm{R}=O(1)$ upper bound is entirely a bounded-error phenomenon -- a clean $\mathrm{R}_0$ vs $\mathrm{R}$ separation of unbounded ratio for a partial function. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Theta(1)\) putative | Read $10$ fixed positions and answer "balanced" iff they are not all equal; a balanced input fools this with probability $2^{-9}$. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Theta(1)\) | $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(1\) | Sandwiched: $\mathrm{Q} \le \mathrm{Adv}^{\pm} \le \mathrm{Q}_E$, with both ends $1$. |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(1\) | Sandwiched: $\mathrm{Adv}^{\pm} \le \mathrm{MAdv} \le \mathrm{Q}_E$, with both ends $1$. |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\Theta(1)\) | Sandwiched between $\mathrm{Q}$ and $\mathrm{R} = O(1)$. |
| \(\mathrm{RC}(f)\) Randomized certificate complexity | \(\Theta(1)\) | Sandwiched: $\mathrm{RC} \le \mathrm{R} = O(1)$, and every measure here is at least $1$. |
| \(\mathrm{FC}(f)\) Fractional certificate complexity | \(\Theta(1)\) | Equal to $\mathrm{fbs} = 2$ by LP duality; also $\le \mathrm{R} = O(1)$. |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(\Theta(1)\) | Sandwiched between $\widetilde{\deg} = 2$ and $\mathrm{R} = O(1)$. |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(\Theta(1)\) | Sandwiched: $\mathrm{prt}_\varepsilon \le \mathrm{R} = O(1)$, and at least $1$. |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(\Theta(1)\) | Sandwiched: $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{R} = O(1)$, and at least $1$. |
| \(\mathrm{s}^0(f)\) 0-sensitivity | \(0\) putative | See $\mathrm{s}$: no single flip of a constant input stays in the promise. |
| \(\mathrm{s}^1(f)\) 1-sensitivity | \(0\) putative | See $\mathrm{s}$: flipping one bit of a balanced input gives weight $N/2 \pm 1$, outside the promise. |
| \(\mathrm{bs}^0(f)\) 0-block sensitivity | \(2\) putative | At $0^N$ the sensitive blocks are exactly the $N/2$-sized sets, and two disjoint ones fit. |
| \(\mathrm{bs}^1(f)\) 1-block sensitivity | \(2\) putative | At a balanced $x$ the sensitive blocks are exactly $\mathrm{supp}(x)$ and its complement. |
| \(\lambda(f)\) Spectral sensitivity | \(0\) putative | The sensitivity graph of $\mathrm{DJ}$ on its promise has no edges at all (see $\mathrm{s}=0$), so its adjacency matrix is zero. Spectral sensitivity, which for total functions satisfies $\deg \le \lambda^2$ and lower-bounds $\mathrm{Q}$, degenerates completely: $\lambda = 0$ while $\deg = 2$ and $\mathrm{D} = N/2+1$. |
| \(\mathrm{rank}(f)\) Decision tree rank | \(2\) putative | Query $x_1, x_2, \dots$ and stop as soon as two different values appear (answer "balanced") or $N/2+1$ equal values appear (answer "constant"). Each of the root's two subtrees is a caterpillar, hence of rank $1$, so the tree has rank $2$; and $\mathrm{rank} \ge \mathrm{C}_{\min} = 2$. So rank sees none of the $\Theta(N)$ depth -- all of it is caterpillar. |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(\Theta(N)\) putative | The tree above has one leaf per stopping point on each of its two branches, so $O(N)$; and a tree of depth $d$ has more than $d$ leaves, so $\Omega(N)$ from $\mathrm{D} = N/2+1$. |
| \(\mathrm{UC}(f)\) Unambiguous certificate complexity | \(N/2+1\) putative | Squeezed: $\mathrm{C} \le \mathrm{UC} \le \mathrm{D}$, with both ends $N/2+1$. (The leaves of the tree above are an unambiguous family of exactly this width.) |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(O(N)\) | Squeezed between $\mathrm{C}_{\min} = 2$ and $\mathrm{UC} = N/2 + 1$. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is worst-case within the cheaper side, not a minimum over inputs, so the width-$2$ certificates on the balanced side do not give $O(1)$: a balanced input has $N^2/4$ disagreeing pairs, and an unambiguous family must still name one of them, which is the same obstruction that forces $\mathrm{UC} = \Omega(N)$. |
| \(\mathrm{SP}(f)\) Subcube partition complexity | \(N/2+1\) putative | Squeezed: $\mathrm{C} \le \mathrm{SP} \le \mathrm{D}$, with both ends $N/2+1$; the tree's leaves are the subcube partition. |
| \(\mathrm{EC}(f)\) Expectational certificate complexity | \(\Theta(\sqrt N)\) putative | A genuinely intermediate value, strictly between $\mathrm{fbs} = 2$ and $\mathrm{C} = N/2+1$. Upper: put $w^x_i = 1/\sqrt N$ at the two constant inputs and $w^y_i = 2/\sqrt N$ everywhere at each balanced $y$; a constant $x$ and a balanced $y$ differ on $N/2$ coordinates, giving $\sum_{i : x_i \ne y_i} w^x_i w^y_i = (N/2)(2/N) = 1$, and every weight vector sums to at most $2\sqrt N$. Lower: at $x = 0^N$, for each balanced $y$ we need $1 \le \sum_{i \in \mathrm{supp}(y)} w^x_i w^y_i \le k \max_{i \in \mathrm{supp}(y)} w^x_i$, so fewer than $N/2$ coordinates can have $w^x_i < 1/k$; hence $k \ge \sum_i w^x_i \ge N/(2k)$. |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(\Theta(1)\) | A lower bound on $\mathrm{Q} = 1$. |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\Theta(1)\) | $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(1)$. |
| \(\mathrm{QC}(f)\) Quantum certificate complexity | \(\Theta(1)\) | An algorithm computing $f$ also verifies it, so $\mathrm{QC} \le \mathrm{Q} = 1$. Compare $\mathrm{C} = N/2+1$: this is the extreme case of quantum certificates beating classical ones. |
| \(\mathrm{CA}(f)\) Classical adversary bound | \(\Theta(1)\) | A lower bound on $\mathrm{R} = O(1)$. |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\Theta(1)\) putative | Read $O(1)$ fixed positions $O(1)$ times each and majority-vote away the noise. |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\Theta(1)\) | At most $\mathrm{N}_p = \Theta(1)$, at least $\mathrm{Q} = 1$. |
| \(\mathrm{sdeg}(f)\) Sign degree | \(2\) putative | Symmetrising a sign-representing polynomial gives a univariate $q$ on $t \in \{0, N/2, N\}$ with $q(0), q(N) > 0 > q(N/2)$, impossible for degree $1$; and $1 - 2(1-2t/N)^2$ has the right signs. So $\mathrm{sdeg} = \widetilde{\deg} = \deg = 2$ -- no relaxation of degree helps at all. |
| \(\mathrm{CG}(f)\) Certificate game complexity (private coin) | \(\Theta(N)\) putative | The private-coin certificate game is linear here, and the argument is short. Upper: both players output a uniformly random index of $[N]$; when Alice holds a constant $x$ and Bob a balanced $y$ they differ on exactly $N/2$ indices, so they win with probability $(N/2)/N^2 = 1/(2N)$. Lower: fix Alice at $x = 0^N$, where she has a single output distribution $p$. Against a balanced $y$ her success is $\sum_{i \in \mathrm{supp}(y)} p(i)\,q_y(i) \le \max_{i \in \mathrm{supp}(y)} p(i)$. Let $y$ be the indicator of the $N/2$ indices with the smallest $p(i)$: the $(N/2)$-th largest value of $p$ is at most $2/N$, so the value is at most $2/N$ and $\mathrm{CG} \ge N/2$. Note the total-function sandwich $\mathrm{R}_0 \le \mathrm{CG} \le \mathrm{C}^0\mathrm{C}^1$ is not available on a promise problem and is not used. CGLMSG23 |
| \(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin) | \(\Theta(1)\) | One shared random index $i$, output by both players, already wins with probability $1/2$. So $\mathrm{CG}^{\mathrm{pub}} \le 2$, matching $\mathrm{CG}^{\mathrm{pub}} = \Theta(\mathrm{CA}) = \Theta(1)$. Against $\mathrm{CG} = \Theta(N)$ this is an unbounded private-versus-public certificate game gap on a partial function: shared randomness is what lets the two players agree on where to look. CGLMSG23 |
| \(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity | \(\Theta(1)\) | Between $\mathrm{CG}^{\mathrm{ns}}$ and $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$. CGLMSG23 |
| \(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity | \(\Theta(1)\) | Between $1$ and $\mathrm{CG}^{*} = \Theta(1)$. CGLMSG23 |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(N/2+1\) putative | One-sided error does not help, even though the cheap side is only two queries. Fix coins $r$ for which the run on $0^N$ outputs $0$ -- at least $2/3$ of them do -- and let $L \le q$ be the positions it reads. If $L \le N/2$ some balanced $y$ agrees with all of them, so the same run outputs $0$ on a $1$-input, which zero error on the $1$-side forbids. Hence $q \ge N/2+1$, and $\mathrm{R}^1 \le \mathrm{R}_0 = N/2+1$. Compare $\mathrm{R} = O(1)$. |
| \(\mathrm{LR}(f)\) Linearised randomized complexity | \(\Theta(1)\) | Sandwiched: $\Omega(\sqrt{\mathrm{R}}) \le \mathrm{LR} \le \mathrm{R} = O(1)$. |
| \(\bar{\chi}(f)\) Max-conflict complexity | \(\Theta(1)\) | Sandwiched: $\Omega(\sqrt{\mathrm{R}}) \le \bar\chi = O(\mathrm{LR}) = O(1)$. |
| \(\chi(f)\) Conflict complexity | \(\Theta(1)\) | At most $\bar\chi = \Theta(1)$, and at least $1$. |
| \(\mathrm{RS}(f)\) Sabotage complexity | \(\Theta(1)\) | At most $\bar\chi = \Theta(1)$; finding a $\ast$ in a sabotaged input is as easy as the problem itself here. |
| \(\mathrm{R}^{*}(f)\) Asymptotic composition rate | \(\Theta(1)\) | Sandwiched: $\Omega(\mathrm{Q}) \le \mathrm{R}^{*} \le \mathrm{R} = O(1)$. |
| \(\mathrm{noisyR}(f)\) Noisy randomized query complexity | \(\Theta(1)\) | At most $\mathrm{R} = O(1)$, and at least $1$. |
| \(\mathrm{noisyR}^{\mathrm{na}}(f)\) Non-adaptive noisy randomized query complexity | \(\Theta(1)\) | Squeezed: $\mathrm{noisyR} = \Theta(1) \le \mathrm{noisyR}^{\mathrm{na}} \le \mathrm{R}^{\mathrm{na}} = \Theta(1)$. Also what Theorem 8 of [BenDavidBlais20composition] predicts -- $\mathrm{noisyR}^{\mathrm{na}} = \Theta(\mathrm{R}^{\mathrm{na}})$ holds for partial functions. BenDavidBlais20composition |
| \(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity | \(\Theta(1)\) | At most $\mathrm{D}^\mu = \Theta(1)$ for every $\mu$, and at least one query. |
| \(\mathrm{rdeg}(f)\) Rational degree | \(1\) putative | Rational degree collapses below exact degree. By the characterisation $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f), \mathrm{ndeg}(\bar f)\}$: $\mathrm{ndeg}(f) = 1$ (see below), and $\mathrm{ndeg}(\bar f) = 1$ too, since $p(x) = |x| - N/2$ vanishes on exactly the balanced inputs. So $\mathrm{rdeg} = 1 < \deg = \widetilde{\deg} = \mathrm{sdeg} = 2$. |
| \(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree | \(1\) | At most $\mathrm{rdeg} = 1$, and at least $1$. |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(\Theta(1)\) | $\mathrm{PostQ}_\varepsilon = \Theta(\mathrm{rdeg}_\varepsilon) = \Theta(1)$. |
| \(\widetilde{\deg}_{+}(f)\) One-sided approximate degree | \(2\) | Squeezed between $\mathrm{sdeg} = 2$ and $\widetilde{\deg} = 2$. |
| \(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity | \(1\) | $\mathrm{NQ} = \lceil\mathrm{ndeg}/2\rceil = 1$, from $\mathrm{ndeg} = 1$ below. |
| \(\mathrm{ndeg}(f)\) Nondeterministic degree | \(1\) putative | Nondeterministic degree collapses where ordinary degree does not. Take $p = \sum_i c_i x_i$ with $\sum_i c_i = 0$ and the $c_i$ otherwise generic: then $p$ vanishes at $0^N$ and at $1^N$, while $\sum_{i \in \mathrm{supp}(y)} c_i \ne 0$ for every balanced $y$ because generic points of the hyperplane $\sum c_i = 0$ avoid the finitely many further hyperplanes. So $\mathrm{ndeg} = 1 < \deg = 2$. |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\Theta(1)\) | Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R}) = \Theta(1)$. |
| \(\mathrm{cbs}(S)\) Critical block sensitivity | \(2\) | Degenerate on a Boolean function: $\mathrm{cbs} = \mathrm{bs} = 2$. In particular the measure that governs $\mathrm{Search}(\varphi)$ says nothing here. GoosPitassi14 |
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. 249 in total, strongest first.
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mathrm{prod}}(f_n) = O(1)\)from \(\mathrm{D}(f) = N/2+1\) against \(\mathrm{D}^{\mathrm{prod}}(f) = \Theta(1)\)
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \mathrm{C}^1(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = \Theta(N)\) against \(\mathrm{C}^1(f) = 2\)
-
\(\mathrm{C}(f_n) \to \infty \ \text{ while } \ \mathrm{rank}(f_n) = O(1)\)from \(\mathrm{C}(f) = N/2+1\) against \(\mathrm{rank}(f) = 2\)
-
\(\mathrm{C}^0(f_n) \to \infty \ \text{ while } \ \bar{\chi}(f_n) = O(1)\)from \(\mathrm{C}^0(f) = N/2+1\) against \(\bar{\chi}(f) = \Theta(1)\)
-
\(\mathrm{UC}(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mu}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{UC}(f) = N/2+1\) against \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{SP}(f_n) \to \infty \ \text{ while } \ \mathrm{R}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{SP}(f) = N/2+1\) against \(\mathrm{R}_{\varepsilon}(f) = O(1)\)
-
\(\mathrm{EC}(f_n) \to \infty \ \text{ while } \ \mathrm{s}(f_n) = O(1)\)from \(\mathrm{EC}(f) = \Theta(\sqrt N)\) against \(\mathrm{s}(f) = 0\)
-
\(\mathrm{D}^{\mathrm{na}}(f_n) \to \infty \ \text{ while } \ \mathrm{LR}(f_n) = O(1)\)from \(\mathrm{D}^{\mathrm{na}}(f) = N/2+1\) against \(\mathrm{LR}(f) = \Theta(1)\)
-
\(\mathrm{R}_{0}(f_n) \to \infty \ \text{ while } \ \bar{\mathrm{R}}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{R}_{0}(f) = N/2+1\) against \(\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{R}^{1}(f_n) \to \infty \ \text{ while } \ \mathrm{noisyR}(f_n) = O(1)\)from \(\mathrm{R}^{1}(f) = N/2+1\) against \(\mathrm{noisyR}(f) = \Theta(1)\)
-
\(\mathrm{CG}(f_n) \to \infty \ \text{ while } \ \mathrm{s}^0(f_n) = O(1)\)from \(\mathrm{CG}(f) = \Theta(N)\) against \(\mathrm{s}^0(f) = 0\)
-
\(\mathrm{D}(f_n) \to \infty \ \text{ while } \ \mathrm{D}^{\mu}_{\varepsilon}(f_n) = O(1)\)from \(\mathrm{D}(f) = N/2+1\) against \(\mathrm{D}^{\mu}_{\varepsilon}(f) = \Theta(1)\)
-
\(\mathrm{DTsize}(f_n) \to \infty \ \text{ while } \ \mathrm{C}_{\min}(f_n) = O(1)\)from \(\mathrm{DTsize}(f) = \Theta(N)\) against \(\mathrm{C}_{\min}(f) = 2\)
-
\(\mathrm{C}(f_n) \to \infty \ \text{ while } \ \bar{\chi}(f_n) = O(1)\)from \(\mathrm{C}(f) = N/2+1\) against \(\bar{\chi}(f) = \Theta(1)\)
… and 235 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/2+1$ vs $\mathrm{Q}_E=1$.
-
Unbounded: $\mathrm{s}=0$ (no promise-preserving flip exists) with $\mathrm{D}=N/2+1$.
-
Unbounded: $\mathrm{fbs}=2$ against $\mathrm{C}=N/2+1$. The total-function bound $\mathrm{C} = O(\mathrm{fbs}^2)$ fails as badly as possible off the promise.
-
Unbounded: $\mathrm{R}=O(1)$ but $\mathrm{R}_0 = N/2+1$, since zero error forces a full $0$-certificate on the constant inputs.
-
Unbounded: $\mathrm{CG} = \Theta(N)$ against $\mathrm{CG}^{\mathrm{pub}} = \Theta(1)$. With shared randomness the two players just name a common random index and win with probability $1/2$; with private randomness Alice, who holds a constant input, has one fixed output distribution and the adversary balances $y$ onto her $N/2$ lightest indices.
Cited as a witness by
-
\(\mathrm{CG}(\mathrm{DJ}_N) = \Theta(N) \text{ while } \mathrm{CG}^{\mathrm{pub}}(\mathrm{DJ}_N) = \Theta(1)\)