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.
The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| 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 |