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