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

Unambiguous certificate complexity

Certificate complexity where the certificates form a partition-like unambiguous cover.

also written: unambiguous nondeterministic query complexity

Definition

An unambiguous certificate family is a set of certificates such that every input is consistent with exactly one of them (per output value). $\mathrm{UC}(f)$ is the smallest $k$ such that such a family exists with all certificates of size $\le k$. $\mathrm{UC}^b$ restricts to $b$-certificates, so that $\mathrm{UC} = \max\{\mathrm{UC}^0, \mathrm{UC}^1\}$ and $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0, \mathrm{UC}^1\}$ -- the one-sided version, which asks for an unambiguous cover on only the cheaper side.

Basic facts

  • $\mathrm{C}(f) \le \mathrm{UC}(f) \le \mathrm{D}(f)$.
  • $\mathrm{C}(f) = \Omega(\mathrm{UC}_{\min}(f)^{1.22})$ for an explicit family [BHT17].
  • $\mathrm{UC}(f) = \mathrm{SP}(f)$ exactly, for every $f$. Splitting a monochromatic subcube partition by colour gives an unambiguous family on each side, and conversely two unambiguous families glue into a partition. The two ids are kept apart only because the literature uses them in different places -- \(\mathrm{SP}(f)\) is what lifts to the communication partition number, $\mathrm{UC}$ is what appears in low-sensitivity constructions -- so $\mathrm{D}$ vs $\mathrm{SP}$ and $\mathrm{D}$ vs $\mathrm{UC}$ are one open problem, not two. The one-sided $\mathrm{UC}_{\min}$ has no such partner.
  • $\mathrm{D}(f) = O(\mathrm{UC}(f)^2)$; separations up to $\mathrm{D} = \tilde\Omega(\mathrm{UC}^2)$ come from the Göös-Pitassi-Watson function.

Relations to other measures

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

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

Known values

FunctionValueNotes
OR total \(n\) At least $\mathrm{C}=n$; and the "first $1$" family -- $x_1=\cdots=x_{i-1}=0,\,x_i=1$ for each $i$, together with $0^n$ -- is unambiguous with all certificates of size $\le n$.
AND total \(n\) The "first $0$" family, mirroring OR.
PARITY total \(n\) The full binary tree is already an unambiguous partition, and $\mathrm{UC}\ge\mathrm{C}=n$.
MAJORITY total \(\Theta(n)\) Sandwiched: $\mathrm{C}(f) \le \mathrm{UC}(f) \le \mathrm{D}(f)$, with $\mathrm{C}(f) = (n+1)/2$ and $\mathrm{D}(f) = n$ here.
Threshold total \(\Theta(n)\) Squeezed: $\mathrm{C}(f) \le \mathrm{UC}(f) \le \mathrm{D}(f)$, with $\mathrm{C}(f) = \max\{k,\,n-k+1\} \ge (n+1)/2$ and $\mathrm{D}(f) = n$.
Symmetric functions (general) total \(\Theta(n)\) Sandwiched: $\mathrm{C}(f) \le \mathrm{UC}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here.
EXACT-HALF total \(n\) Sandwiched: $\mathrm{C}(f) \le \mathrm{UC}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
ODD-MAX-BIT total \(\Theta(n)\) Sandwiched: $\mathrm{C}(f) \le \mathrm{UC}(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 family $\{a \text{ fixed},\, y_a = b\}$ over all $2^k$ addresses is unambiguous -- each input matches exactly one member per output value -- and has width $k+1 = \mathrm{C}$.
Binary tree navigation total \(k\) Sandwiched: $\mathrm{C}(f) \le \mathrm{UC}(f) \le \mathrm{D}(f)$, with both ends $k$ here. Concretely the $2^k$ leaves of the walk tree are already an unambiguous certificate family.
TRIBES total \(n\) putative A parity obstruction. An unambiguous $b$-cover partitions $f^{-1}(b)$ into subcubes of sizes $2^{n-c_i}$, so if $|f^{-1}(b)|$ is odd some $c_i$ must equal $n$. Here $|f^{-1}(0)| = (2^w-1)^s$ is a power of an odd number, hence odd, and $|f^{-1}(1)| = 2^n - (2^w-1)^s$ is odd too. So $\mathrm{UC}^0 = \mathrm{UC}^1 = n$, far above $\mathrm{C} = \Theta(n/\log n)$ and $\mathrm{C}^1 = \Theta(\log n)$.
AND-OR tree (depth 2) total \(N = n^2\) putative Squeezed by $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$ with $\deg = \mathrm{D} = n^2$; see the \(\mathrm{SP}(f)\) entry. Note how far this is from $\mathrm{C} = n$: the AND-OR tree is the standard $\mathrm{UC}$-vs-$\mathrm{C}$ gap.
NAND tree (balanced AND-OR formula) total \(N\) putative Squeezed by $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D} = N$; see \(\mathrm{SP}(f)\). Against $\mathrm{C} = \Theta(\sqrt N)$ this is the largest possible $\mathrm{UC}$-vs-$\mathrm{C}$ gap.
Recursive MAJORITY-of-3 total \(N = 3^d\) putative An unambiguous $1$-certificate family of width $w$ writes $f$ as a sum of $\le w$-variable conjunctions with no cancellation, so $\deg(f) \le \mathrm{UC}(f)$. Every read-once formula has $\deg = N$, which forces $\mathrm{UC} = \mathrm{SP} = \mathrm{D} = N$ -- even though $\mathrm{C} = N^{0.63}$. Verified by exact set-partition search at $d = 1,2$.
Kushilevitz's function (iterated) total \(N\) Squeezed between $\mathrm{C} = N$ and $\mathrm{D} = N$, since $\mathrm{C} \le \mathrm{UC} \le \mathrm{SP} \le \mathrm{D}$.
Rubinstein's function total \(N\) putative Squeezed by $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D} = N$; see \(\mathrm{SP}(f)\).
Ambainis-Sun function total \(\Theta(N)\) Squeezed by $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$; see \(\mathrm{SP}(f)\).
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) Squeezed by $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D} = \Theta(n^2)$; see \(\mathrm{SP}(f)\).
Meiburg's tournament-subcube function total \(\ge 14011^{\,d}\) putative Immediate from $\mathrm{UC} \ge \mathrm{C} \ge \mathrm{bs}$.
Pointer functions total \(\widetilde\Omega(\sqrt n)\) Variant $f_{2m,m}$: $\mathrm{UC}\ge\mathrm{SP}\ge\mathrm{C}=\widetilde\Omega(\sqrt n)$. No matching upper bound is claimed -- an unambiguous cover of the pointer function is not known to be as cheap as an ordinary certificate.
Cheat-sheet functions total \(\widetilde\Omega(\sqrt n)\) Squeeze: $\mathrm{UC}\ge\mathrm{SP}\ge\mathrm{C}=\widetilde\Omega(\sqrt n)$. Only the $1$-side is known to be unambiguously certifiable at that cost, which is why $\mathrm{UC}_{\min}$ is pinned above but $\mathrm{UC}$ is not.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^{3/2})\) Squeeze: $\mathrm{UC}\ge\mathrm{C}$; equivalently $\mathrm{D}\le\mathrm{UC}^2$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Theta(n^2)\) Squeeze: $\mathrm{C}\le\mathrm{UC}\le\mathrm{D}$.
Gilmer-Saks-Srinivasan functions total \(\Theta(n^2)\) Squeeze: $\mathrm{C}\le\mathrm{UC}\le\mathrm{D}$, both $\Theta(n^2)$.
Random-indicator gadget total \(n\) Squeeze: $\mathrm{C}\le\mathrm{UC}\le\mathrm{D}$, both $n$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Theta(n)\) Squeeze: $\mathrm{C}\le\mathrm{UC}\le\mathrm{D}$. It is the one-sided $\mathrm{UC}_1$ that is small here; the two-sided quantity is maximal, which is exactly why [GPW18] needs the AND-composed variant for the $\mathrm{SP}$ separation.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Theta(n^{2/3})\) Squeeze: $\mathrm{C}\le\mathrm{UC}\le\mathrm{D}$.
Ambainis' exact-quantum function total \(3^d\) Squeeze: $\mathrm{C}\le\mathrm{UC}\le\mathrm{D}$.
FORRELATION partial \(\Theta(n)\) Squeezed: $\mathrm{C} \le \mathrm{SP} = \mathrm{UC} \le \mathrm{D}$, and both ends are $\Theta(n)$.
k-FORRELATION partial \(O(kn)\) At most $\mathrm{D} = O(kn)$; equal to $\mathrm{SP}$.
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{UC} \le \mathrm{D}$, with both ends $N/2+1$. (The leaves of the tree above are an unambiguous family of exactly this width.)
Bernstein-Vazirani partial \(n\) putative Squeezed between $\mathrm{C} = n$ and $\mathrm{D} = n$.
Unique search partial \(n\) putative $\mathrm{UC} = \mathrm{SP}$, and the partition above is exactly an unambiguous certificate cover.
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} = \Theta(1)$ and $\mathrm{D}$. Unambiguity is not free here: the constant-size certificates overlap heavily, since many cells of the ball certify the same value.
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)\) At most $\mathrm{D} = O(n)$; equal to $\mathrm{SP}$.
Surjectivity total \(\Theta(n)\) Squeezed between $\mathrm{C}(f) \le \mathrm{UC}(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\) $\mathrm{UC}=\mathrm{SP}$ exactly, and the partition of the \(\mathrm{SP}(f)\) entry is already unambiguous on each side separately -- input $x^{(k)}$ is consistent with the certificate $\{x_k=0,x_{k+1}=1\}$ and with no other.
Inner product mod 2 total \(n\) putative The natural decision tree -- for each $i$ read $x_i$, and read $y_i$ only if $x_i=1$ -- is a subcube partition, hence an unambiguous certificate family, of width $\max_x (m + |x\wedge y|) = n$. And $\mathrm{UC} \ge \mathrm{C} = n$.
Minsky-Papert one-in-a-box total \(N = m^3\) putative Pinned by the same $\deg \le \mathrm{SP} \le \mathrm{UC} \le \mathrm{D}$ collapse; see \(\mathrm{SP}(f)\). A second, self-contained proof: $|f^{-1}(1)| = (2^{m^2}-1)^m$ is odd, and an unambiguous $1$-certificate family partitions $f^{-1}(1)$ into subcubes of sizes that are powers of two, so one of them must be a single point -- a certificate of full width $N$. Against $\mathrm{C} = m^2$ this is a $\mathrm{UC}$-vs-$\mathrm{C}$ gap of $N^{1/3}$.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{C}(f) \le \mathrm{UC}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$, with $\mathrm{C} = \Theta(m)$ and $\mathrm{D} = O(m)$ here.
Scorpion graphs total \(\Theta(m)\) Sandwiched: $\mathrm{C}(f) \le \mathrm{UC}(f) \le \mathrm{SP}(f) \le \mathrm{D}(f)$, with $\mathrm{C} = \Theta(m)$ and $\mathrm{D} = O(m)$ here.
Graph connectivity total \(\binom{m}{2} = N\) putative Pinned by the same collapse; see \(\mathrm{SP}(f)\). Note the contrast with $\mathrm{C}_{\min} = m-1$: a spanning tree is a perfectly good certificate, but no unambiguous family can be narrow anywhere near everywhere.