Partition bound
LP relaxation of "cover the cube by few low-codimension monochromatic subcubes"; subsumes most classical lower bound techniques.
also written:
partition bound, \mathrm{prt}(f)
Definition
Introduced for query complexity (not merely imported from communication complexity) in [JainKlauck10, Def. 15]. There is a variable $w_{A,z}\ge 0$ for every partial assignment $A$ -- equivalently every subcube -- and every output $z$, and the LP is $$\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} = 1 \qquad \text{for every } x ,$$ where $|A|$ is the number of fixed variables. Read $w_{A,z}$ as "probability that a zero-communication prover announces the subcube $A$ and the answer $z$": the second constraint says exactly one subcube fires on each input, the first says the answer is right with probability $1-\varepsilon$, and $2^{|A|}$ prices a codimension-$|A|$ subcube at the number of leaves it would take to isolate it.
The LP optimum is on a number-of-leaves scale, so throughout this zoo $\mathrm{prt}_\varepsilon(f)$ denotes its logarithm, $$\mathrm{prt}_\varepsilon(f) \;:=\; \log_2\Big(\text{optimum of the LP above}\Big),$$ which is the quantity that is comparable with $\mathrm{D}$ and $\mathrm{R}$. Beware that [JainKlauck10] write $\mathrm{prt}_\varepsilon(f)$ for the optimum itself and carry the $\log$ around explicitly. The integral version of the LP is "partition the cube into monochromatic subcubes", so $\mathrm{prt}(f) \le O(\mathrm{SP}(f)) \le O(\mathrm{D}(f))$.
Parameters
\(\varepsilon\) (eps) default \(1/3\)
Error parameter.
Basic facts
- $\mathrm{prt}_\varepsilon(f) \le 2\,\mathrm{R}_\varepsilon(f)$ -- it is a lower bound technique for randomized query complexity [JainKlauck10, Thm 3.1]. The factor $2$ is real for the price used above: a complete tree of depth $d$ has $2^d$ leaves each costing $2^d$, for an LP value of $4^d$.
- It subsumes essentially every classical technique in this zoo [JainKlauck10, Thm 3]: $\mathrm{prt}_0(f) \ge \mathrm{C}(f)$; $\mathrm{prt}_{\varepsilon/4}(f) \ge \varepsilon\,\mathrm{bs}(f) + \log\varepsilon - 2$; $\mathrm{prt}_\varepsilon(f) \ge \mathrm{RC}_{2\varepsilon/(1-2\varepsilon)}(f) + \log \varepsilon$; $\mathrm{prt}_\varepsilon(f) \ge (1-4\varepsilon)\,\mathrm{CA}(f) + \log\varepsilon$; and $\mathrm{prt}_\varepsilon(f) \ge \widetilde{\deg}_{2\varepsilon}(f) + \log\varepsilon$ for Boolean $f$.
- It is not too far from $\mathrm{D}$ either: $\mathrm{D}(f) = O\big(\mathrm{prt}_0(f)\cdot \mathrm{prt}_{1/3}(f)\big)$ and $\mathrm{D}(f) = O\big(\mathrm{prt}_{1/3}(f)^3\big)$ [JainKlauck10, Thm 3.7]. So for total $f$ the partition bound is polynomially related to everything else in the classical column.
- But it is not tight: there is a total $f$ with $\mathrm{RS}(f) \ge \mathrm{prt}(f)^{2-o(1)}$, hence $\mathrm{R}(f) \ge \mathrm{prt}(f)^{2-o(1)}$ [BenDavidKothari18, Thm 30].
- Query-to-communication lifting theorems typically show $\mathrm{prt}$-type query bounds lift to communication bounds.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{prt}_{\varepsilon}(f)\). “\(\mathrm{prt}_{\varepsilon}(f)\) in terms of it” is the pair with \(\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 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| AND total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| PARITY total | \(\Theta(n)\) | Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| MAJORITY total | \(\Theta(n)\) | Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here. |
| Threshold total | \(\Theta(n)\) | Squeezed: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{s}(f) = \max\{k,\,n-k+1\}$ and $\mathrm{D}(f) = n$. |
| Symmetric functions (general) total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. |
| EXACT-HALF total | \(\Theta(n)\) | Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here. |
| ODD-MAX-BIT total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. |
| ADDRESS / multiplexer total | \(\Theta(k+1)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $k+1$ here. |
| Binary tree navigation total | \(\Theta(k)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $k$ here. |
| TRIBES total | \(\Omega(\sqrt n),\ O(n)\) | Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$. The truth is presumably $\Theta(n)$, matching $\mathrm{R}$, but the partition bound is not known to reach $\mathrm{R}$ for TRIBES and the recorded $\mathrm{RC} = \Theta(n/\log n)$ is already below $\mathrm{R}$, so no better lower bound is claimed here. |
| AND-OR tree (depth 2) total | \(\Omega(n),\ O(n^2)\) | The partition bound dominates block sensitivity, $\mathrm{prt}_{\varepsilon/4} \ge \varepsilon\,\mathrm{bs} + \log\varepsilon - 2 = \Omega(n)$, and is dominated by $2\mathrm{R} = O(n^2)$ [JainKlauck10, Thm 3.1]. JainKlauck10 |
| NAND tree (balanced AND-OR formula) total | \(\Omega(\sqrt N),\ O\!\big(N^{\,0.753\ldots}\big)\) | Sandwiched: $\mathrm{fbs} \le \mathrm{prt}_{\varepsilon} \le \mathrm{R}_{\varepsilon}$, i.e. between $\Theta(\sqrt N)$ and $\Theta(N^{0.753\ldots})$. Where the partition bound sits inside that window is open; the conical-junta relaxation \(\mathrm{cjdeg}_{\varepsilon}(f)\) is known to sit at the top of it. |
| Recursive MAJORITY-of-3 total | \(\Omega(2^{\,d}),\ O(2.64944^{\,d})\) | Sandwiched: $\mathrm{fbs} \le \mathrm{prt}_{\varepsilon} \le \mathrm{R}_{\varepsilon}$, with $\mathrm{fbs} = 2^d$ and the recorded $\mathrm{R}$ upper bound. The related conical-junta LP \(\mathrm{cjdeg}_{\varepsilon}(f)\) is known to be $\Omega(2.59^d)$, i.e. near the top of this window. |
| Kushilevitz's function (iterated) total | \(\Theta(N)\) | Sandwiched: $\mathrm{bs}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $N$ here. |
| Rubinstein's function total | \(\Theta(N)\) | Sandwiched: $\mathrm{fbs}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with $\mathrm{fbs}(f) = \Theta(N)$ and $\mathrm{D}(f) = N$ here. |
| Ambainis-Sun function total | \(\Theta(N)\) | Sandwiched: $\mathrm{fbs} \le \mathrm{prt}_{\varepsilon} \le \mathrm{R}_{\varepsilon}$, with both ends $\Theta(N)$ here. |
| AND composed with NOT-EXACT-HALF total | \(\Theta(n^2)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here. |
| Meiburg's tournament-subcube function total | \(\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}$. |
| Pointer functions total | \(\widetilde\Theta(\sqrt n)\) | Variant $g_{m,m}$: $\mathrm{prt}_\varepsilon\le 2\mathrm{R}_\varepsilon=\widetilde O(\sqrt n)$ [JainKlauck10, Thm 3.1], and $\mathrm{prt}_\varepsilon\ge\mathrm{RC}+\log\varepsilon=\widetilde\Omega(\sqrt n)$. So the partition bound is tight against $\mathrm{R}$ here and does not see the $\mathrm{D}$-vs-$\mathrm{R}$ gap. JainKlauck10 |
| Cheat-sheet functions total | \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) | Ceiling $\mathrm{prt}_\varepsilon\le 2\mathrm{R}_\varepsilon=\widetilde O(n)$ [JainKlauck10, Thm 3.1]. Best floor available: $\mathrm{prt}_\varepsilon\ge\mathrm{RC}+\log\varepsilon=\widetilde\Omega(\sqrt n)$ (the $\widetilde{\deg}$ and $\mathrm{CA}$ floors are no better, and $\mathrm{D}=O(\mathrm{prt}_{1/3}^3)$ only gives $\widetilde\Omega(n^{1/3})$). Whether the partition bound sees cheat-sheet hardness is exactly this gap. JainKlauck10 |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde\Omega(n)\) | Two floors coincide: $\mathrm{prt}_\varepsilon\ge\mathrm{RC}+\log\varepsilon=\widetilde\Omega(n)$, and $\mathrm{D}=O(\mathrm{prt}_{1/3}^3)$ against $\mathrm{D}=\widetilde\Omega(n^3)$ gives $\widetilde\Omega(n)$ as well [JainKlauck10]. No ceiling, since $\mathrm{prt}\le 2\mathrm{R}$ and $\mathrm{R}$ is unbounded above here. JainKlauck10 |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) | Floor $\mathrm{prt}_\varepsilon\ge\mathrm{RC}+\log\varepsilon=\widetilde\Omega(n^{4/3})$; ceiling $\mathrm{prt}_\varepsilon\le 2\mathrm{R}_\varepsilon=\widetilde O(n^2)$ [JainKlauck10, Thm 3.1]. JainKlauck10 |
| Gilmer-Saks-Srinivasan functions total | \(\Omega(n),\ O(n^2)\) | Floor $\mathrm{prt}_\varepsilon\ge\mathrm{RC}+\log\varepsilon=\Omega(n)$ (also $\mathrm{prt}_\varepsilon\ge(1-4\varepsilon)\mathrm{CA}+\log\varepsilon$, the same scale); ceiling $\mathrm{prt}_\varepsilon\le 2\mathrm{R}_\varepsilon=O(n^2)$ [JainKlauck10, Thm 3.1]. The zero-error partition bound is a different story: $\mathrm{prt}_0\ge\mathrm{C}=\Omega(n^2)$. JainKlauck10 |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) | Floor $\mathrm{prt}_\varepsilon\ge\mathrm{RC}+\log\varepsilon=\widetilde\Omega(\sqrt n)$; ceiling $\mathrm{prt}_\varepsilon\le 2\mathrm{R}_\varepsilon=\widetilde O(n)$ [JainKlauck10, Thm 3.1]. At zero error the story is different: $\mathrm{prt}_0\ge\mathrm{C}=\widetilde\Theta(n)$. JainKlauck10 |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) | Floor $\mathrm{prt}_\varepsilon\ge\mathrm{RC}+\log\varepsilon=\widetilde\Omega(n^{1/3})$; ceiling $\mathrm{prt}_\varepsilon\le 2\mathrm{R}_\varepsilon=\widetilde O(n^{2/3})$ [JainKlauck10, Thm 3.1]. Since $\mathrm{D}=O(\mathrm{prt}_{1/3}^3)$ also gives only $\widetilde\Omega(n^{2/9})$, the cell stays a genuine quadratic gap. JainKlauck10 |
| Ambainis' exact-quantum function total | \(\Theta(3^d)\) | Squeezed between $\mathrm{RC}$ and $2\mathrm{R}$ [JainKlauck10], which coincide at $3^d$. |
| FORRELATION partial | \(\widetilde O(\sqrt n)\) | From $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon$. |
| k-FORRELATION partial | \(\widetilde O\!\big(n^{1-1/k}\big)\) | From $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon$. |
| Simon's problem partial | \(O(2^{n/2})\) | From $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon$. |
| Deutsch-Jozsa partial | \(\Theta(1)\) | Sandwiched: $\mathrm{prt}_\varepsilon \le \mathrm{R} = O(1)$, and at least $1$. |
| Bernstein-Vazirani partial | \(O(n)\) | $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon = O(n)$; from below $(1-4\varepsilon)\mathrm{CA} \le \mathrm{prt}_\varepsilon + \log(1/\varepsilon)$ gives only $\Omega(1)$. |
| Dense marked bit partial | \(\Theta(1)\) | Sandwiched: $\mathrm{prt}_\varepsilon \le \mathrm{R} = \Theta(1)$, and at least $1$. |
| Unstructured search (relation) relation | \(O(n)\) | From $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon = O(n)$. |
| FIND-1 under a density promise relation | \(O(1)\) | From $\mathrm{prt} \le 2\mathrm{R} = O(1)$. |
| Approximate Hamming weight relation | \(O(1)\) | From $\mathrm{prt} \le 2\mathrm{R} = O(1)$. |
| SearchCNF relation | \(O(1)\) | From $\mathrm{prt} \le 2\mathrm{R} = O(1)$. |
| Gap-Majority partial | \(O(\min(n, 1/\delta^2))\) | $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon$; from below $(1-4\varepsilon)\mathrm{CA} \le \mathrm{prt}_\varepsilon + \log(1/\varepsilon)$ gives $\Omega(\min(n,1/\delta))$. |
| Gap-Majority at constant gap partial | \(O(1)\) | $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon$. |
| Parity-labelled FIND-1 partial | \(O(1)\) | $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon = O(1)$. |
| Approximate index partial | \(O(\sqrt{k\log k})\) | From $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon$. |
| Collision problem partial | \(O(\sqrt n)\) | $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon = O(\sqrt n)$. |
| Element distinctness total | \(\Theta(n)\) | Squeezed between $(1-4\varepsilon)\mathrm{CA} + \log\varepsilon = \Omega(n)$ and $2\mathrm{R} = O(n)$. JainKlauck10 |
| Ambainis-Belovs function partial | \(O(n)\) | From $\mathrm{prt}_\varepsilon \le 2\mathrm{R}_\varepsilon = O(n)$. |
| Surjectivity total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status. |
| $k$-distinctness total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(n)$ here. |
| Triangle finding total | \(\Theta(m^2) = \Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here. |
| Welded trees relation | \(\widetilde O(2^{n/2})\) | $\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon$ [JainKlauck10], a bound stated for relations, and $\mathrm{R}=\tilde\Theta(2^{n/2})$. The usual lower bound $\mathrm{prt}\ge\widetilde{\deg}$ is unavailable: approximate degree is not defined for a relation. JainKlauck10 |
| Local search on the hypercube relation | \(O(2^{n/2}\sqrt n)\) | $\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon$ [JainKlauck10] in the relation setting, and $\mathrm{R}=\Theta(2^{n/2}\sqrt n)$. The recorded $\mathrm{CA}=\tilde\Theta(2^{n/2})$ does not give a matching lower bound: $\mathrm{CA}\le\mathrm{prt}$ is proved only for partial functions. JainKlauck10 |
| Local search on the grid relation | \(O(k^{d/2})\ (d \ge 4)\) | $\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon$ [JainKlauck10] in the relation setting, and $\mathrm{R}=\Theta(k^{d/2})$ for $d\ge4$. JainKlauck10 |
| Fourier fishing relation | \(O(N)\) | $\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon\le2\,\mathrm{D}=2N$ [JainKlauck10], stated for relations. The partition bound is a lower-bound technique for $\mathrm{R}$, so the recorded $\mathrm{R}=\Omega(N/\log N)$ says nothing about it from below. JainKlauck10 |
| Ordered search partial | \(\Omega\!\big(\tfrac{\log n}{(\log\log n)^2}\big),\ O(\log n)\) | $\widetilde{\deg}_{2\varepsilon}\le\mathrm{prt}_\varepsilon+\log(1/\varepsilon)\le2\,\mathrm{R}_\varepsilon+\log(1/\varepsilon)$ [JainKlauck10], so the partition bound inherits the recorded approximate degree window between $\Omega(\log n/(\log\log n)^2)$ and $O(\log n)$. JainKlauck10 BunVoronova23 |
| Tseitin search on an expander relation | \(O(n)\) | $\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon=O(n)$ [JainKlauck10], stated for relations. The recorded $\mathrm{CA}=\Theta(n)$ does not close this from below: $\mathrm{CA}\le\mathrm{prt}$ is a partial-function statement. JainKlauck10 |
| Inner product mod 2 total | \(\Theta(n)\) | Sandwiched: $\mathrm{s}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $n$ here. |
| Minsky-Papert one-in-a-box total | \(\Omega(m^2),\ O(m^3)\) | Sandwiched, and the sandwich is loose. Lower: $\mathrm{RC} \le \mathrm{prt}_{\varepsilon}$ (\(\mathrm{RC}(f)\) vs \(\mathrm{prt}_{\varepsilon}(f)\)) with $\mathrm{RC} = \Theta(m^2)$; the $\widetilde{\deg} \le \mathrm{prt}$ route is weaker here, $\Omega(m^{3/2})$. Upper: $\mathrm{prt}_{\varepsilon} \le \mathrm{R} = \Theta(m^3)$. Whether the partition bound is tight for $\mathrm{R}$ is open in general, and the AND-OR tree is exactly the shape where nobody has closed it. |
| Sink of a tournament total | \(\Theta(m) = \Theta(\sqrt N)\) | Sandwiched: $\mathrm{bs}(f) \le \mathrm{prt}_{\varepsilon}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here. |
| Scorpion graphs total | \(\Theta(m)\) | Sandwiched: $\mathrm{RC}(f) \le \mathrm{prt}(f) + O(1) \le 2\,\mathrm{R}(f) + O(1)$, with $\mathrm{RC} = \Theta(m)$ and $\mathrm{R} = \Theta(m)$ here. The LP loses nothing on the scorpion, in contrast with the quadratic loss it can suffer in general. JainKlauck10 |
| Graph connectivity total | \(\Theta(m^2) = \Theta(N)\) | Sandwiched: $\mathrm{RC}(f) \le \mathrm{prt}(f) + O(1) \le 2\,\mathrm{R}(f) + O(1)$, with $\mathrm{RC} = \Theta(m^2)$ and $\mathrm{R} = \Theta(m^2)$ here. The LP bound is tight on connectivity, so the $\Theta(N)$ randomized lower bound is already visible to the partition bound. JainKlauck10 |