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

Relaxed partition bound

The partition bound with the "fires with probability exactly 1" constraint relaxed to "at most 1"; weaker, but unlike prt it lower-bounds information complexity.

also written: relaxed partition bound, \mathrm{prt}^{\ast}

Definition

Take the LP of the partition bound and relax the completeness constraint from an equality to an inequality: $$\min \sum_{A,z} w_{A,z}\, 2^{|A|} \quad\text{s.t.}\quad \sum_{A \ni x} w_{A,f(x)} \ge 1-\varepsilon \ \text{ and }\ \sum_{A \ni x,\, z} w_{A,z} \;\le\; 1 \qquad \text{for every } x ,$$ and again put $\overline{\mathrm{prt}}_\varepsilon(f) := \log_2(\text{optimum})$. The only change is the second constraint: $=1$ has become $\le 1$. In the zero-communication reading, the prover is now allowed to abort: the probability that some subcube fires may be anywhere in $[1-\varepsilon, 1]$ instead of being exactly $1$ on every input. The relaxation is genuine but not vacuous -- the two constraints together still force $\sum_{A\ni x} w_{A,z} \le \varepsilon$ for every wrong answer $z \ne f(x)$, so e.g. one cannot simply buy the whole cube twice, once under each label.

The bound was defined for communication complexity by [KLLRX15, Def. 3.2], who write the objective as $1/\eta$ where $\eta$ is the non-abort probability, normalise $\sum_{R,z} p_{R,z} = 1$, and impose correctness only on average under an input distribution $\mu$ before taking $\overline{\mathrm{prt}}_\varepsilon = \max_\mu \overline{\mathrm{prt}}^{\,\mu}_\varepsilon$ (the averaging is what lets them handle promise problems). The display above is the query analogue in the subcube dictionary, with correctness kept pointwise.

Parameters

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

Basic facts

  • $\overline{\mathrm{prt}} \le \mathrm{prt} \le 2\,\mathrm{R}$: enlarging the feasible region can only lower the optimum.
  • Why the relaxation was invented: $\overline{\mathrm{prt}}$ lower-bounds information complexity, $\mathrm{prt}$ is not known to [KLLRX15, Thm 1.1]. The proof compresses a protocol leaking $I$ bits into a zero-communication protocol with non-abort probability $2^{-O(I)}$, and one cannot make that probability come out exactly equal on every input -- hence the inequality.
  • In communication complexity it sits above the smooth rectangle bound, $\mathrm{srec}^z_\varepsilon \le \overline{\mathrm{prt}}_\varepsilon \le \mathrm{prt}_\varepsilon$ [KLLRX15, Lem. 3.3], and therefore also above corruption, $\gamma_2$ and discrepancy.
  • In the query setting every lower bound the partition bound subsumes survives the relaxation -- see the $\mathrm{bs} \to \overline{\mathrm{prt}}$ record for the argument -- so $\overline{\mathrm{prt}}$ is pinned to $\Theta(\mathrm{R})$ on all the usual functions, exactly like $\mathrm{prt}$.
  • For total search problems there is an exponential separation between quantum information complexity (communication) and the relaxed partition bound [BenDavidKundu24search]; even the randomized-vs-$\overline{\mathrm{prt}}$ separation was previously unknown for total search problems.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\overline{\mathrm{prt}}_{\varepsilon}(f)\). “\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) in terms of it” is the pair with \(\overline{\mathrm{prt}}_{\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 \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) in terms of it It in terms of \(\overline{\mathrm{prt}}_{\varepsilon}(f)\)
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound total1,1 partial1,1 relation1,1 open pair → total1,3 partial1,? relation1,? derived open pair →
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total1,1 partial1,1 relation1,1 derived open pair → total2,3 partial2,? relation2,? derived open pair →
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree total1,4 partial1,? relation1,? derived open pair → total1,3 partial1,? relation1,? derived open pair →
\(\mathrm{CA}(f)\) Classical adversary bound total1,3 partial∞ relation1,? derived open pair → total1,1 partial1,2 relation1,? derived open pair →

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

Known values

FunctionValueNotes
OR total \(\Theta(n)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $n$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
AND total \(\Theta(n)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $n$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
PARITY total \(\Theta(n)\)· Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $n$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
MAJORITY total \(\Theta(n)\)· Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
Threshold total \(\Theta(n)\)· Squeezed: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{s}(f) = \max\{k,\,n-k+1\}$ and $\mathrm{D}(f) = n$. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
Symmetric functions (general) total \(\Theta(n)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
EXACT-HALF total \(\Theta(n)\)· Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
ODD-MAX-BIT total \(\Theta(n)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
ADDRESS / multiplexer total \(\Theta(k+1)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $k+1$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
Binary tree navigation total \(\Theta(k)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $k$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
TRIBES total \(\Omega(\sqrt n),\ O(n)\)· Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$. Same caveat as the \(\mathrm{prt}_{\varepsilon}(f)\) line above.
AND-OR tree (depth 2) total \(\Omega(n),\ O(n^2)\)· The same sandwich as \(\mathrm{prt}_{\varepsilon}(f)\): the relaxed bound still dominates $\mathrm{bs}$ (the zoo's own $\mathrm{bs} \to \overline{\mathrm{prt}}$ record, which checks that the [JainKlauck10] argument never uses the completeness equality) and is at most $\mathrm{prt} \le 2\mathrm{R}$.
NAND tree (balanced AND-OR formula) total \(\Omega(\sqrt N),\ O\!\big(N^{\,0.753\ldots}\big)\)· As \(\mathrm{prt}_{\varepsilon}(f)\); the relaxed bound still dominates $\mathrm{fbs}$ (the zoo's own observation that the [JainKlauck10] techniques survive dropping the completeness equality) and is still at most $\mathrm{R}$.
Recursive MAJORITY-of-3 total \(\Omega(2^{\,d}),\ O(2.64944^{\,d})\)· As \(\mathrm{prt}_{\varepsilon}(f)\); the relaxed partition bound still dominates $\mathrm{fbs}$ (the zoo's own observation about the [JainKlauck10] techniques) and is still at most $\mathrm{R}$.
Kushilevitz's function (iterated) total \(\Theta(N)\)· Sandwiched: $\mathrm{bs}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $N$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
Rubinstein's function total \(\Theta(N)\)· Sandwiched: $\mathrm{fbs}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{fbs}(f) = \Theta(N)$ and $\mathrm{D}(f) = N$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
Ambainis-Sun function total \(\Theta(N)\)· Sandwiched: $\mathrm{fbs} \le \overline{\mathrm{prt}}_{\varepsilon} \le \mathrm{R}_{\varepsilon}$, with both ends $\Theta(N)$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record).
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
Meiburg's tournament-subcube function total \(\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).
Pointer functions total \(\widetilde\Theta(\sqrt n)\) Variant $g_{m,m}$: $\mathrm{rprt}\le\mathrm{prt}=\widetilde O(\sqrt n)$, and the $\mathrm{RC}$ floor survives the relaxation, so $\mathrm{rprt}=\widetilde\Omega(\sqrt n)$ too. JainKlauck10
Cheat-sheet functions total \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) The relaxation only loses from above, $\mathrm{rprt}\le\mathrm{prt}=\widetilde O(n)$, and every floor quoted on the $\mathrm{prt}$ line survives it, so the same range applies. JainKlauck10
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n)\) The $\mathrm{RC}$ floor survives the relaxation of the partition bound, so $\mathrm{rprt}=\widetilde\Omega(n)$ by the argument of the $\mathrm{prt}$ line. JainKlauck10
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) The $\mathrm{RC}$ floor survives the relaxation and $\mathrm{rprt}\le\mathrm{prt}$, so the $\mathrm{prt}$ range carries over unchanged. JainKlauck10
Gilmer-Saks-Srinivasan functions total \(\Omega(n),\ O(n^2)\) The $\mathrm{RC}$ and $\mathrm{CA}$ floors survive the relaxation and $\mathrm{rprt}\le\mathrm{prt}$, so the $\mathrm{prt}$ range carries over. JainKlauck10
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) The $\mathrm{RC}$ floor survives the relaxation and $\mathrm{rprt}\le\mathrm{prt}$, so the $\mathrm{prt}$ range carries over. JainKlauck10
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) The $\mathrm{RC}$ floor survives the relaxation and $\mathrm{rprt}\le\mathrm{prt}$, so the $\mathrm{prt}$ range carries over. JainKlauck10
Ambainis' exact-quantum function total \(\Theta(3^d)\) Squeeze: $\overline{\mathrm{prt}}\ge\mathrm{RC}=3^d$ and $\overline{\mathrm{prt}}\le\mathrm{prt}$.
FORRELATION partial \(\widetilde O(\sqrt n)\) From $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{prt}_\varepsilon$.
k-FORRELATION partial \(\widetilde O\!\big(n^{1-1/k}\big)\) From $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{prt}_\varepsilon$.
Simon's problem partial \(O(2^{n/2})\) From $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{prt}_\varepsilon$.
Deutsch-Jozsa partial \(\Theta(1)\) Sandwiched: $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{R} = O(1)$, and at least $1$.
Bernstein-Vazirani partial \(O(n)\) $\mathrm{rprt} \le \mathrm{prt} = O(n)$.
Dense marked bit partial \(\Theta(1)\) Sandwiched: $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{prt}_\varepsilon = \Theta(1)$, and at least $1$.
Unstructured search (relation) relation \(O(n)\) From $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{prt}_\varepsilon = O(n)$.
FIND-1 under a density promise relation \(O(1)\) From $\overline{\mathrm{prt}} \le \mathrm{prt} = O(1)$.
Approximate Hamming weight relation \(O(1)\) From $\overline{\mathrm{prt}} \le \mathrm{prt} = O(1)$.
SearchCNF relation \(O(1)\) From $\overline{\mathrm{prt}} \le \mathrm{prt} = O(1)$.
Gap-Majority partial \(O(\min(n, 1/\delta^2))\) $\overline{\mathrm{prt}} \le \mathrm{prt}$.
Gap-Majority at constant gap partial \(O(1)\) $\overline{\mathrm{prt}} \le \mathrm{prt}$.
Parity-labelled FIND-1 partial \(O(1)\) $\overline{\mathrm{prt}} \le \mathrm{prt} = O(1)$.
Approximate index partial \(O(\sqrt{k\log k})\) From $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{prt}_\varepsilon$.
Collision problem partial \(O(\sqrt n)\) $\overline{\mathrm{prt}} \le \mathrm{prt}$.
Element distinctness total \(\Theta(n)\) The relaxation keeps every classical lower bound the partition bound subsumes, in particular $\Omega(\mathrm{bs}) = \Omega(n)$, and $\overline{\mathrm{prt}} \le \mathrm{prt} = \Theta(n)$. KLLRX15
Ambainis-Belovs function partial \(O(n)\) From $\overline{\mathrm{prt}}_\varepsilon \le \mathrm{prt}_\varepsilon = O(n)$.
Surjectivity total \(\Theta(n)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional. The lower end also inherits the provenance of $\mathrm{s}$ on this page.
$k$-distinctness total \(\Theta(n)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. As on \(\mathrm{SURJ}_{N,R}\), the lower end rests on the observation that the [JainKlauck10] arguments survive the relaxation of the completeness constraint; the upper end is unconditional. JainKlauck10
Triangle finding total \(\Theta(m^2) = \Theta(n)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
Welded trees relation \(\widetilde O(2^{n/2})\) $\overline{\mathrm{prt}}_\varepsilon\le\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon=\widetilde O(2^{n/2})$ [JainKlauck10]. JainKlauck10
Local search on the hypercube relation \(O(2^{n/2}\sqrt n)\) $\overline{\mathrm{prt}}_\varepsilon\le\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon$ [JainKlauck10]. JainKlauck10
Local search on the grid relation \(O(k^{d/2})\ (d \ge 4)\) $\overline{\mathrm{prt}}_\varepsilon\le\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon$ [JainKlauck10]. JainKlauck10
Fourier fishing relation \(O(N)\) $\overline{\mathrm{prt}}_\varepsilon\le\mathrm{prt}_\varepsilon=O(N)$ [JainKlauck10]. JainKlauck10
Ordered search partial \(\Omega\!\big(\tfrac{\log n}{(\log\log n)^2}\big),\ O(\log n)\) Same window as \(\mathrm{prt}_{\varepsilon}(f)\): $\widetilde{\deg}_{2\varepsilon}\le\overline{\mathrm{prt}}_\varepsilon+\log(1/\varepsilon)$ [KLLRX15] and $\overline{\mathrm{prt}}\le\mathrm{prt}\le2\,\mathrm{R}$. JainKlauck10 KLLRX15
Tseitin search on an expander relation \(O(n)\) $\overline{\mathrm{prt}}_\varepsilon\le\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon=O(n)$ [JainKlauck10]. JainKlauck10
Inner product mod 2 total \(\Theta(n)\)· Sandwiched: $\mathrm{s}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $n$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
Minsky-Papert one-in-a-box total \(\Omega(m^2),\ O(m^3)\) The same window as \(\mathrm{prt}_{\varepsilon}(f)\), and it cannot be narrower: $\mathrm{RC} \le \overline{\mathrm{prt}}_{\varepsilon} \le \mathrm{prt}_{\varepsilon} \le \mathrm{R}$, with $\mathrm{RC} = \Theta(m^2)$ and $\mathrm{R} = \Theta(m^3)$.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\)· Sandwiched: $\mathrm{bs}(f) \le \overline{\mathrm{prt}}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here. The lower end is the zoo's own observation that the [JainKlauck10] techniques survive the relaxation of the completeness constraint (see the $\mathrm{RC}\to\overline{\mathrm{prt}}$ record); the upper end is unconditional.
Scorpion graphs total \(\Theta(m)\)· The same sandwich as \(\mathrm{prt}_{\varepsilon}(f)\) survives the relaxation, $\mathrm{RC}(f) \le \overline{\mathrm{prt}}(f) + O(1) \le \mathrm{prt}(f) + O(1) = O(m)$; medium confidence because the $\mathrm{RC}$ containment is the zoo's own reading of [JainKlauck10] against the LP of [KLLRX15]. JainKlauck10 KLLRX15
Graph connectivity total \(\Theta(m^2) = \Theta(N)\)· The \(\mathrm{prt}_{\varepsilon}(f)\) sandwich survives the relaxation, $\mathrm{RC}(f) \le \overline{\mathrm{prt}}(f) + O(1) \le \mathrm{prt}(f) + O(1) = O(m^2)$; medium confidence because the $\mathrm{RC}$ containment is the zoo's own reading of [JainKlauck10] against the LP of [KLLRX15]. JainKlauck10 KLLRX15