Q The Query Complexity Zoo
\(\mathrm{SP}(f)\)

Subcube partition complexity

Smallest k such that the cube can be partitioned into monochromatic subcubes of codimension <= k.

also written: partition number, unambiguous DNF/CNF width

Definition

The minimum $k$ such that $\{0,1\}^n$ (or $\mathrm{Dom}(f)$) can be partitioned into subcubes of codimension at most $k$, each monochromatic for $f$. $\mathrm{SP}$ is the query-complexity analogue of the partition number in communication complexity; the deterministic-vs-partition question lifts to $\mathrm{D}$ vs $\mathrm{SP}$.

Basic facts

  • $\mathrm{C}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$ and $\mathrm{SP} \le \mathrm{UC}$.
  • $\mathrm{D}(f) = O(\mathrm{SP}(f)^2)$, and this is essentially tight: [AKK16] give a total $f$ with $\mathrm{D}(f) = \tilde\Omega(\mathrm{SP}(f)^2)$, in fact already $\mathrm{R}(f) = \tilde\Omega(\mathrm{SP}(f)^2)$. The first separation of any kind is [KRS15]; the power-$1.5$ stage is the query half of [GPW18].
  • Quantum is not settled: $\mathrm{Q} = \tilde\Omega(\mathrm{SP}^{1.5})$ [AKK16] against the $O(\mathrm{SP}^2)$ ceiling. The quadratic quantum separation in [AKK16], like the $\log^2\chi_1$ bound of [GPW18], is against the one-sided partition number -- a different measure, and not one the zoo carries.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{SP}(f)\). “\(\mathrm{SP}(f)\) in terms of it” is the pair with \(\mathrm{SP}(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{SP}(f)\) in terms of it It in terms of \(\mathrm{SP}(f)\)
\(\mathrm{UC}(f)\) Unambiguous certificate complexity total1,1 partial1,1 open pair → total1,1 partial1,1 open pair →
\(\mathrm{C}(f)\) Certificate complexity total2,2 partial2,? derived open pair → total1,1 partial1,1 open pair →
\(\mathrm{D}(f)\) Deterministic query complexity total1,1 partial1,1 open pair → total2,2 partial∞ open pair →

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

Known values

FunctionValueNotes
OR total \(n\) The subcube containing $0^n$ must fix all $n$ coordinates, since any free coordinate could be set to $1$; the "first $1$" tree achieves codimension $n$.
AND total \(n\) The subcube containing $1^n$ must fix everything.
PARITY total \(n\) A monochromatic subcube must fix every coordinate.
MAJORITY total \(\Theta(n)\) Sandwiched: $\mathrm{C}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$, with $\mathrm{C}(f) = (n+1)/2$ and $\mathrm{D}(f) = n$ here. Majority cannot separate any of the certificate-flavoured measures from $\mathrm{D}$ by more than a factor of two.
Threshold total \(\Theta(n)\) Squeezed: $\mathrm{C}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$, with $\mathrm{C}(f) \ge (n+1)/2$ and $\mathrm{D}(f) = n$.
Symmetric functions (general) total \(\Theta(n)\) Sandwiched: $\mathrm{C}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here.
EXACT-HALF total \(n\) Sandwiched: $\mathrm{C}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$, with both ends $n$ here. The $1$-inputs are isolated points of the cube, so no monochromatic subcube containing one can have codimension below $n$.
ODD-MAX-BIT total \(\Theta(n)\) Sandwiched: $\mathrm{C}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$, with $\mathrm{C}(f) = \lfloor n/2\rfloor+1$ and $\mathrm{D}(f) = n$ here.
ADDRESS / multiplexer total \(k+1\) putative The natural tree (read the address, then the addressed entry) partitions the cube into codimension-$(k+1)$ monochromatic subcubes, and no monochromatic subcube can have codimension below $\mathrm{C}_{\min} = k+1$.
Binary tree navigation total \(k\) Sandwiched: $\mathrm{C}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$, with both ends $k$ here. The walk tree partitions the cube into $2^k$ monochromatic subcubes of codimension exactly $k$.
TRIBES total \(n\) putative A subcube partition induces an unambiguous cover on each side, so $\mathrm{SP} \ge \mathrm{UC} = n$ by the parity argument on the \(\mathrm{UC}(f)\) line; and $\mathrm{SP} \le \mathrm{D} = n$. The $\Theta(\log n)$-size $1$-certificates cannot be assembled into a partition.
AND-OR tree (depth 2) total \(N = n^2\) putative A partition of the cube into monochromatic subcubes of codimension $\le k$ writes $f$ as the sum of the indicators of its $1$-subcubes, each a conjunction of $\le k$ literals and none of them cancelling, so $\deg(f) \le \mathrm{SP}(f)$. Here $\deg = \mathrm{D} = n^2$, so the chain $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$ collapses. Every read-once formula is pinned this way.
NAND tree (balanced AND-OR formula) total \(N\) putative A monochromatic subcube partition writes $f$ as a sum of indicators of subcubes of codimension $\le \mathrm{SP}$, with no cancellation, so $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$. On a read-once formula $\deg = \mathrm{D} = N$, so all four coincide.
Recursive MAJORITY-of-3 total \(N = 3^d\) Between $\mathrm{UC} = N$ and $\mathrm{D} = N$.
Kushilevitz's function (iterated) total \(N\) Squeezed between $\mathrm{UC} = N$ and $\mathrm{D} = N$.
Rubinstein's function total \(N\) putative A monochromatic subcube partition writes $f$ as a sum of indicators of subcubes of codimension $\le\mathrm{SP}$, so $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$; here $\deg = \mathrm{D} = N$.
Ambainis-Sun function total \(\Theta(N)\) A monochromatic subcube partition expresses $f$ as a signless sum of subcube indicators, so $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$; here $\deg$ and $\mathrm{D}$ are both $\Theta(N)$.
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) A monochromatic subcube partition writes $f$ as a signless sum of subcube indicators of codimension $\le \mathrm{SP}$, so $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$; here $\deg$ and $\mathrm{D}$ are both $\Theta(n^2)$.
Meiburg's tournament-subcube function total \(\ge 14011^{\,d}\) putative Every subcube of a monochromatic partition is a certificate for the inputs it contains, so $\mathrm{SP} \ge \mathrm{C} \ge \mathrm{bs}$.
Pointer functions total \(\widetilde\Omega(\sqrt n)\) Variant $f_{2m,m}$: every subcube of a monochromatic partition is a certificate, so $\mathrm{SP}\ge\mathrm{C}=\widetilde\Omega(\sqrt n)$.
Cheat-sheet functions total \(\widetilde\Omega(\sqrt n)\) Squeeze: every subcube of a monochromatic partition is a certificate, so $\mathrm{SP}\ge\mathrm{C}=\widetilde\Omega(\sqrt n)$.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^{3/2})\) Squeeze: $\mathrm{SP}\ge\mathrm{C}$; equivalently $\mathrm{D}\le\mathrm{SP}^2$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Theta(n^2)\) Squeeze: $\mathrm{C}\le\mathrm{SP}\le\mathrm{D}$.
Gilmer-Saks-Srinivasan functions total \(\Theta(n^2)\) Squeeze: $\mathrm{C}\le\mathrm{SP}\le\mathrm{D}$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Theta(n)\) Squeeze: $\mathrm{C}\le\mathrm{SP}\le\mathrm{D}$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Theta(n^{2/3})\) Squeeze: $\mathrm{C}\le\mathrm{SP}\le\mathrm{D}$. So the two-sided partition number is maximal here, which is why the $\mathrm{R}$-vs-$\mathrm{SP}$ witness has to be the AND-composed variant.
Ambainis' exact-quantum function total \(3^d\) Squeeze: $\mathrm{C}\le\mathrm{SP}\le\mathrm{D}$.
FORRELATION partial \(\Theta(n)\) Equal to $\mathrm{UC}$ exactly, and squeezed between $\mathrm{C} = \Theta(n)$ and $\mathrm{D} = \Theta(n)$.
k-FORRELATION partial \(O(kn)\) Equal to $\mathrm{UC}$, and at most $\mathrm{D} = O(kn)$.
Simon's problem partial \(\Theta(2^{n/2})\) putative Squeezed between $\mathrm{C}$ and $\mathrm{D}$, both $\Theta(2^{n/2})$.
Deutsch-Jozsa partial \(N/2+1\) putative Squeezed: $\mathrm{C} \le \mathrm{SP} \le \mathrm{D}$, with both ends $N/2+1$; the tree's leaves are the subcube partition.
Bernstein-Vazirani partial \(n\) putative Squeezed between $\mathrm{C} = n$ and $\mathrm{D} = n$; the $2^n$ subcubes "$x_{e_1} = b_1, \dots, x_{e_n} = b_n$" partition the promise.
Unique search partial \(n\) putative The $n$ subcubes $\{x_i = 1\}$ together with the single point $\{0^n\}$ partition the domain, so a partition of width $n$ exists; and no partition can do better, since the part containing $0^n$ must exclude all $n$ points $e_i$ and therefore fixes every coordinate.
Gap-Majority partial \(\Theta(n)\) putative Squeezed between $\mathrm{C}$ and $\mathrm{D}$, both $\Theta(n)$.
Gap-Majority at constant gap partial \(\Theta(n)\) putative Between $\mathrm{C}$ and $\mathrm{D}$.
Approximate index partial \(O(\sqrt{k\log k})\) Between $\mathrm{C}$ and $\mathrm{D}$: the leaves of the deterministic tree form a subcube partition of the promise.
Collision problem partial \(n/2+1\) putative Squeezed between $\mathrm{C}$ and $\mathrm{D}$, both $n/2+1$.
Element distinctness total \(n\) putative Squeezed between $\mathrm{C} = n$ and $\mathrm{D} = n$.
Ambainis-Belovs function partial \(O(n)\) Equal to $\mathrm{UC}$, and at most $\mathrm{D} = O(n)$.
Surjectivity total \(\Theta(n)\) Squeezed between $\mathrm{C}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$, with $\mathrm{C} = \Theta(n)$ and $\mathrm{D} = n$.
$k$-distinctness total \(n\) Squeezed between $\mathrm{C} = n$ and $\mathrm{D} = n$.
Triangle finding total \(\binom m2 = n\) Squeezed between $\mathrm{C} = \binom m2$ and $\mathrm{D} = \binom m2$.
Ordered search partial \(2\) putative The $n+1$ subcubes $\{x_k=0,x_{k+1}=1\}$ (with $\{x_1=1\}$ and $\{x_n=0\}$ at the ends) have codimension at most $2$ and each meets the promise in exactly one input, so they partition $\mathrm{Dom}(f)$ into monochromatic pieces. And $\mathrm{SP}\ge\mathrm{C}=2$. A subcube partition of size $2$ against $\mathrm{D}=\Theta(\log n)$: the $\mathrm{D}$ versus $\mathrm{SP}$ question is hopeless on promises.
Inner product mod 2 total \(n\) A width-$w$ subcube partition is in particular an unambiguous family, so $\mathrm{UC} \le \mathrm{SP} \le \mathrm{D}$, and both ends are $n$ here.
Minsky-Papert one-in-a-box total \(N = m^3\) putative A partition of the cube into monochromatic subcubes writes $f$ as a sum of indicators of conjunctions of $\le \mathrm{SP}$ literals with no cancellation, so $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$; here $\deg = \mathrm{D} = N$, so the chain collapses. Read-once formulas are always pinned this way.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) As for $\mathrm{UC}$: the leaves of any decision tree form a subcube partition, so $\mathrm{SP} \le \mathrm{D} = O(m)$, and $\mathrm{SP} \ge \mathrm{UC} \ge \mathrm{C} = \Theta(m)$.
Scorpion graphs total \(\Theta(m)\) The leaves of the $O(m)$-query algorithm form a monochromatic subcube partition, so $\mathrm{SP} \le \mathrm{D} = O(m)$; and $\mathrm{SP} \ge \mathrm{UC} \ge \mathrm{C} = \Theta(m)$.
Graph connectivity total \(\binom{m}{2} = N\) putative A monochromatic subcube partition writes $f$ as a sum of indicators of conjunctions of $\le \mathrm{SP}$ literals with no cancellation, so $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$; here $\deg = \mathrm{D} = N$ and the whole chain collapses.