Q The Query Complexity Zoo
\(\mathrm{AndOr}_{\mathcal{H},t}\)

Ben-David-Kundu total search problems

A total search problem with $\mathrm{Q} = \Omega(\sqrt n\log^4 n)$ but conical junta degree $O(\log^7 n)$ -- exponential, and against a measure usually larger than $\mathrm{R}$.

relation relational arity: $t\,n^2\log(n/2)$ bits, in $t$ blocks of $n^2\log(n/2)$; the separating setting is $t = \log^5 n$— also: shifted AND-OR search problem, query TFNP separations

Description

Start from $\mathrm{AndOr}_n$: an $\mathrm{OR}$ of size $n^2$ of $\mathrm{AND}$s of size $\log(n/2)$, viewed as the search problem "given a $1$-input, output the index of an all-$1$ block". This is a promise problem -- an input with no all-$1$ block has no valid output.

Totality is bought by shifting. Fix a family $\mathcal{H}$ of $\log^2 n$-wise independent functions and take $t$ independent copies $x^1,\dots,x^t$; a valid output is a tuple $(i_1,\dots,i_t)$ together with a shift $h \in \mathcal{H}$ such that $i_\ell$ solves $\mathrm{AndOr}_n(x^\ell \oplus h)$ for every $\ell$. For $t = \mathrm{polylog}(n)$ some shift always works, so the problem is total: it lives in the query analogue of $\mathrm{TFNP}$, with certificates of only $t\log(n/2)$ bits.

The two "tricks" of the paper are a translation of a partial function into a total search problem and a translation back. Composing them turns unbounded degree measures (where separations are easy) into bounded ones (where they are hard), which is how the separations below are manufactured.

Formal definition

Blocks: $x^\ell \in \{0,1\}^{n^2\log(n/2)}$ split into $n^2$ blocks of $\log(n/2)$ bits; $\mathrm{AndOr}_n(x) = \{i : x_{ij} = 1 \text{ for all } j\}$. Valid outputs of $\mathrm{AndOr}_{\mathcal{H},t}$ on $(x^1,\dots,x^t)$: $$\big\{(i_1,\dots,i_t) \;:\; \exists\, h \in \mathcal{H} \text{ with } i_\ell \in \mathrm{AndOr}_n(x^\ell \oplus h) \text{ for all } \ell \in [t]\big\}.$$ All values below are at $t = \log^5 n$.

Measure values

MeasureValueNotes
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree \(O(\log^7 n)\) Theorem 31: $\widetilde{\deg} = O(t\log^2 n)$, here $O(\log^7 n)$. The witnessing system of polynomials is built from the unbounded degree-$\log(n/2)$ system $p_i(x) = \tfrac{1}{3n}\prod_j x_{ij}$ for $\mathrm{AndOr}_n$, error-reduced to $1/\sqrt n$ at degree $O(\log^2 n)$ and then made bounded by the shift. BenDavidKundu24search
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(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
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\widetilde\Omega(\sqrt n)\) Theorem 39: at $t = \log^5 n$, any quantum algorithm making $o(\sqrt n \log^4 n)$ queries succeeds with probability only $2^{-\Omega(\log^4 n)}$ against the uniform distribution. The core is the $\Omega(t\sqrt n/\log\log n)$ direct-sum bound for $t$ copies of $\mathrm{AndOr}_n$ at exponentially small success, and a union bound over the $2^{2\log^3 n\log\log(n/2)}$ shifts. BenDavidKundu24search
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\widetilde\Omega(\sqrt n)\) $\mathrm{Adv}^{\pm} = \Theta(\mathrm{Q})$, so the negative-weight adversary is $\widetilde\Omega(\sqrt n)$ here while $\widetilde{\deg} = O(\log^7 n)$: for search problems the adversary bound is exponentially stronger than the polynomial method.
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{Q} = \widetilde\Omega(\sqrt n)$; no better classical lower bound is claimed, and the trivial ceiling is the input length $t n^2\log(n/2)$.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\widetilde\Omega(\sqrt n)\) $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{R}$.
\(\mathrm{D}(f)\) Deterministic query complexity \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{R}$.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{D}$.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{R}$.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{R}$, since $\mathrm{R} \le \mathrm{psD}$.
\(\mathrm{DTsize}(f)\) Decision tree size \(2^{\widetilde\Omega(\sqrt n)}\)? putative A tree of depth $d$ has more than $d$ leaves, so this only says $\mathrm{DTsize} > \mathrm{D}$; the exponential form follows because every leaf must force a valid output, and $\mathrm{C} = O(\log^6 n)$ certificates cannot be reached in fewer than $\mathrm{D}$ queries on the hard inputs.
\(\mathrm{C}(f)\) Certificate complexity \(O(\log^6 n)\) putative A valid output is a tuple $(i_1,\dots,i_t)$ of all-$1$ blocks, and exhibiting the $t\log(n/2) = O(\log^6 n)$ bits of those blocks certifies it. Membership in query $\mathrm{TFNP}$ is exactly the requirement that certificates be polylogarithmic in the input size, and it is what makes the $\mathrm{Q} = \widetilde\Omega(\sqrt n)$ lower bound interesting.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(O(\log^6 n)\) The problem is total: every input has a valid output, so there is no "no" side and $\mathrm{C}^1 = \mathrm{C} = O(\log^6 n)$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(\Theta(\log^6 n)\) putative Unusually, the min and the max coincide. Any certificate must name an output $(i_1,\dots,i_t)$ and a shift, and to know that $i_\ell$ is an all-$1$ block of $x^\ell \oplus h$ one must have read all $\log(n/2)$ bits of that block, for every $\ell$. So $\mathrm{C}_x \ge t\log(n/2)$ on every input, matching the upper bound of the \(\mathrm{C}(f)\) entry.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\widetilde\Omega(\sqrt n)\) The hard distribution of [BenDavidKundu24search, Thm 39] is the uniform distribution on $t$ independent blocks, which is a product distribution, and a deterministic tree is in particular a quantum algorithm. So the restriction to product distributions costs nothing here: $\mathrm{D}^{\mathrm{prod}} = \widetilde\Omega(\sqrt n)$, and combined with $\mathrm{RS}(g) = \widetilde\Omega(\mathrm{D}^{\mathrm{prod}}(g))$ this makes the problem hard to use as an inner function in a composition.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\widetilde\Omega(\sqrt n)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \widetilde\Omega(\sqrt n)$; the uniform distribution already achieves it -- see \(\mathrm{D}^{\mathrm{prod}}(f)\).
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{Q}$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{Q}$.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{Q}$: noisy oracles cannot be cheaper than exact ones.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{R}$: setting the noise rate to $0$ recovers the ordinary model.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\widetilde\Omega(\sqrt n)\) Sandwiched: $\mathrm{Adv}^{\pm} \le \mathrm{MAdv} \le \mathrm{Q}$, and the recorded $\mathrm{Adv}^{\pm}$ is already $\widetilde\Omega(\sqrt n)$.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\widetilde\Omega(\sqrt n)\) $\gamma_2 = \Theta(\mathrm{Adv}^{\pm}) = \widetilde\Omega(\sqrt n)$.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\widetilde\Omega(\sqrt n)\) Squeezed from below by $\mathrm{R} \le \mathrm{R}^1$, with $\mathrm{R} = \widetilde\Omega(\sqrt n)$; above, $\mathrm{R}^1 \le \mathrm{R}_0$. The relational reading of one-sided error is available here because the search problem is total and its outputs are self-certifying.

Separations it witnesses

  • For a total search problem in query $\mathrm{TFNP}$: at $t = \log^5 n$, $\widetilde{\deg}(\mathrm{AndOr}_{\mathcal{H},t}) = O(t\log^2 n) = O(\mathrm{polylog}\,n)$ while $\mathrm{Q} = \Omega(\sqrt n\log^4 n)$, i.e. $\mathrm{Q} = 2^{\widetilde\Omega(\widetilde{\deg}^{1/7})}$ -- exponential. Translating back gives a partial function with $\widetilde{\deg} = O(\mathrm{polylog}\,n)$ and $\mathrm{Q} = \widetilde\Omega(n^{1/6})$ on inputs of length $2^{\mathrm{polylog}\,n}$, a second proof of [AmbainisBelovs23].
  • The same problem, with the upper bound strengthened to the larger two-sided bounded non-negative degree: $\widetilde{\deg}^+_2 = O(t\log^2 n) = O(\mathrm{polylog}\,n)$ against $\mathrm{Q} = \Omega(\sqrt n\log^4 n)$. Since $\mathrm{cjdeg}$ normally sits above $\mathrm{R} \ge \mathrm{Q}$, this also gives the first $\mathrm{R}$-vs-$\mathrm{cjdeg}$ separation for a total search problem, and for a partial function.
  • A different and simpler total search problem: the pigeonhole problem $\mathrm{PH}_n$ -- given $n$ blocks holding symbols from an alphabet of size $n/2$, find two equal blocks. Reduction from the collision lower bound gives $\widetilde{\deg}(\mathrm{PH}_n) = \Omega(n^{1/3})$, while an explicit feasible solution $m_x(i) = 2/n$ gives $\mathrm{CA}(\mathrm{PH}_n) \le 2\log(n/2) = O(\log n)$. Since $\mathrm{CA}$ dominates $\mathrm{Adv}$, $\mathrm{fbs}$, $\mathrm{bs}$ and $\mathrm{fcbs}/2$, every block-sensitivity and adversary method is $O(\log n)$ here: the polynomial method is exponentially stronger than the positive adversary on search problems, the reverse of the usual situation.

Notes

Two translations drive everything. Trick 1 turns a partial function into a total search problem by hiding the promise behind a shift; Trick 2 turns a search problem back into a partial function using an array of "queried cells". Applying both in turn converts unbounded degree measures into bounded ones, which is why separations that are trivial for unbounded degree become exponential separations for approximate degree and conical junta degree.

Lifted with a constant-size inner gadget, the same construction gives an exponential separation between quantum information cost and the relaxed partition bound in communication complexity -- previously open even for randomized communication complexity against $\mathrm{relprt}$.