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

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.

Other measure \(\mathrm{prt}_{\varepsilon}(f)\) in terms of it It in terms of \(\mathrm{prt}_{\varepsilon}(f)\)
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound total1,3 partial1,? relation1,? derived open pair → total1,1 partial1,1 relation1,1 open pair →
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total1,1 partial1,1 relation1,1 open pair → total2,3 partial2,? relation2,? open pair →
\(\mathrm{RS}(f)\) Sabotage complexity total1,2 partial∞ derived open pair → total2,3 partial2,? open pair →
\(\mathrm{CA}(f)\) Classical adversary bound total1,3 partial∞ relation1,? derived open pair → total1,1 partial1,1 relation1,? open pair →
\(\mathrm{SP}(f)\) Subcube partition complexity total1,2 partial∞ derived open pair → total2,3 partial∞ derived open pair →

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

Known values

FunctionValueNotes
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