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

Minimum unambiguous certificate complexity

The cheaper of the two one-sided unambiguous certificate complexities.

Definition

$\mathrm{UC}_{\min}(f) = \min\{\mathrm{UC}^0(f),\ \mathrm{UC}^1(f)\}$ [BHT17, Sec. 2.5]: an unambiguous cover is demanded on only one side of the function, whichever side is cheaper. It is not a min over inputs -- $\mathrm{UC}_{\min}$ is still worst-case within the side it picks. It is the quantity in the $\mathrm{C}(f)=\Omega(\mathrm{UC}_{\min}(f)^{1.22})$ separation of [BHT17], which in turn drives the best known $\lambda$-vs-$\mathrm{C}$ separation.

Basic facts

  • $\mathrm{D}(f) \le \mathrm{UC}_{\min}(f)^2$ and $\mathrm{C}(f) \le \mathrm{UC}_{\min}(f)^2$ [BHT17, Sec. 2.7.2]; the communication-complexity analogue is due to Yannakakis and the query-side proof to Goos.
  • $\mathrm{fbs}(f) \le 2\,\mathrm{UC}_{\min}(f) - 1$ [BHT17, Thm 9], and the factor $2$ cannot be removed. This is exactly why the unambiguous-certificate route cannot produce a super-quadratic $\mathrm{bs}$-vs-$\mathrm{s}$ separation.
  • $\mathrm{UC}_{\min}(f) \le \mathrm{UC}(f)$, but $\mathrm{UC}_{\min}$ is not above $\mathrm{C}$ -- only above $\mathrm{fbs}$.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{UC}_{\min}(f)\). “\(\mathrm{UC}_{\min}(f)\) in terms of it” is the pair with \(\mathrm{UC}_{\min}(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}_{\min}(f)\) in terms of it It in terms of \(\mathrm{UC}_{\min}(f)\)
\(\mathrm{UC}(f)\) Unambiguous certificate complexity total1,1 partial1,1 open pair → total2,2 partial∞ derived open pair →
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity total∞ partial∞ derived open pair → total1,2 partial1,? derived open pair →
\(\mathrm{C}(f)\) Certificate complexity total2,2 partial2,? derived open pair → total2,2 partial∞ derived open pair →
\(\mathrm{fbs}(f)\) Fractional block sensitivity total2,3 partial∞ derived open pair → total1.3333,2 partial∞ derived open pair →
\(\mathrm{D}(f)\) Deterministic query complexity total1,1 partial1,1 derived open pair → total2,2 partial∞ 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 \(n\) putative Corrected. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is the one-sided version, not a minimum over inputs. $\mathrm{UC}^0 = n$ because $0^n$ is the only $0$-input and its certificate must fix every bit. $\mathrm{UC}^1 = n$ too: an unambiguous $1$-cover partitions the $2^n-1$ ones-inputs into subcubes of sizes $2^{n-c_i}$, and an odd total forces some $c_i = n$. Consistent with the two general bounds $\mathrm{D} \le \mathrm{UC}_{\min}^2$ and $\mathrm{fbs} \le 2\,\mathrm{UC}_{\min}-1$ [BHT17], both of which the old value $1$ violated. BHT17
AND total \(n\) putative Corrected, mirroring \(\mathrm{OR}_n\): $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is one-sided, not a minimum over inputs. $\mathrm{UC}^1 = n$ since $1^n$ is the only $1$-input, and $\mathrm{UC}^0 = n$ since an unambiguous $0$-cover partitions an odd number ($2^n-1$) of inputs into subcubes. The old value $1$ violated both $\mathrm{D} \le \mathrm{UC}_{\min}^2$ and $\mathrm{fbs} \le 2\,\mathrm{UC}_{\min}-1$ [BHT17]. BHT17
PARITY total \(n\) Every certificate of every input is the whole assignment.
MAJORITY total \(\Theta(n)\) Sandwiched: $\mathrm{C}_{\min}(f) \le \mathrm{UC}_{\min}(f) \le \mathrm{UC}(f)$, with $\mathrm{C}_{\min}(f) = (n+1)/2$ and $\mathrm{UC}(f) = \Theta(n)$ here.
Threshold total \(\Theta(n)\) putative Immediately from $\mathrm{fbs}(f) \le 2\,\mathrm{UC}_{\min}(f)-1$ [BHT17] with $\mathrm{fbs} = \max\{k,\,n-k+1\}$, together with $\mathrm{UC}_{\min} \le \mathrm{UC} = \Theta(n)$. A self-contained route gives the same bound with better constants. Unambiguous covers restrict: intersecting each subcube of a cover with a subcube $\rho$ leaves an unambiguous cover of $f|_\rho$ of no larger width, so $\mathrm{UC}^b(f|_\rho) \le \mathrm{UC}^b(f)$. Fixing $k-1$ ones turns $\mathrm{THR}^n_k$ into $\mathrm{OR}_{n-k+1}$ and fixing $n-k$ zeros turns it into $\mathrm{AND}_k$; for both of these each side has an odd number of inputs ($2^m-1$, or the single point), so some subcube of any unambiguous cover has full codimension. Hence $\mathrm{UC}^0, \mathrm{UC}^1 \ge \max\{k,\,n-k+1\}$ and $\mathrm{UC}_{\min} = \Theta(n)$ -- the threshold family cannot witness anything for the [BHT17] $\mathrm{C}$-vs-$\mathrm{UC}_{\min}$ question. BHT17
Symmetric functions (general) total \(\Theta(n)\) Squeezed: $\mathrm{fbs}(f) \le 2\,\mathrm{UC}_{\min}(f) - 1$ [BHT17] forces $\mathrm{UC}_{\min} = \Omega(n)$ since $\mathrm{fbs} = \Theta(n)$ here, and $\mathrm{UC}_{\min} \le \mathrm{UC} = \Theta(n)$. So symmetric functions are useless for the $\mathrm{C}$-vs-$\mathrm{UC}_{\min}$ separation of [BHT17]. BHT17
EXACT-HALF total \(\Theta(n)\) putative Lower: $\mathrm{fbs} \le 2\,\mathrm{UC}_{\min}-1$ [BHT17] with $\mathrm{fbs} = n$ gives $\mathrm{UC}_{\min} \ge (n+1)/2$. Upper: $\mathrm{UC}_{\min} \le \mathrm{UC}^1 = n$, the $1$-inputs being isolated points, which the partition into singletons covers unambiguously. The exact constant is open here; note that no unambiguous $0$-cover can use only minimum $0$-certificates, since two all-ones certificates of size $n/2+1$ must overlap in a coordinate and their subcubes then share the input $1_{S \cup T}$. BHT17
ODD-MAX-BIT total \(\Theta(n)\) Squeezed: $\mathrm{fbs}(f) \le 2\,\mathrm{UC}_{\min}(f)-1$ [BHT17] forces $\mathrm{UC}_{\min} \ge \tfrac12(\lfloor n/2\rfloor+2) = \Omega(n)$, and $\mathrm{UC}_{\min} \le \mathrm{UC} = \Theta(n)$. Note the contrast with $\mathrm{C}_{\min} = 1$: the one-sided unambiguous measure is not a minimum over inputs and does not collapse. BHT17
ADDRESS / multiplexer total \(k+1\) Between $\mathrm{C}_{\min} = k+1$ and $\mathrm{UC} = k+1$.
Binary tree navigation total \(k\) Sandwiched: $\mathrm{C}_{\min}(f) \le \mathrm{UC}_{\min}(f) \le \mathrm{UC}(f)$, with both ends $k$ here -- navigation is completely certificate-uniform, so none of the four certificate variants can separate.
TRIBES total \(n\) putative Both sides are $n$ by the parity argument on the \(\mathrm{UC}(f)\) line, so the one-sided minimum does not help. TRIBES is therefore useless as a witness for the [BHT17] $\mathrm{C}$-vs-$\mathrm{UC}_{\min}$ question, despite its very lopsided certificate complexities. BHT17
AND-OR tree (depth 2) total \(N = n^2\) putative An unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as a sum of indicators of disjoint subcubes of codimension $\le w$, with no cancellation, so $\deg \le \mathrm{UC}^0$ and $\deg \le \mathrm{UC}^1$, i.e. $\deg \le \mathrm{UC}_{\min} \le \mathrm{UC}$. Here $\deg = \mathrm{UC} = n^2$, so even the cheaper side of the unambiguous cover costs the full $N$ -- against $\mathrm{C}_{\min} = n$.
NAND tree (balanced AND-OR formula) total \(N\) putative An unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as a sum of indicators of disjoint subcubes of codimension $\le w$, so $\deg \le \mathrm{UC}^0$ and $\deg \le \mathrm{UC}^1$, i.e. $\deg \le \mathrm{UC}_{\min}$. On a read-once formula $\deg = \mathrm{D} = N$, so even the cheaper side is full -- against $\mathrm{C}_{\min} = \Theta(\sqrt N)$, a quadratic $\mathrm{UC}_{\min}$-vs-$\mathrm{C}_{\min}$ gap.
Recursive MAJORITY-of-3 total \(N = 3^d\) putative An unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as a sum of indicators of disjoint subcubes of codimension $\le w$, with no cancellation, so $\deg \le \mathrm{UC}^0$ and $\deg \le \mathrm{UC}^1$, i.e. $\deg \le \mathrm{UC}_{\min} \le \mathrm{UC}$. Here $\deg = \mathrm{UC} = N$, so both unambiguous sides cost the full $N$ against $\mathrm{C} = \mathrm{C}_{\min} = N^{0.63}$.
Kushilevitz's function (iterated) total \(\Omega(N^{0.6131}),\ O(N)\) putative Not pinned. Lower: an unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as a sum of indicators of disjoint subcubes of codimension $\le w$, so $\deg \le \mathrm{UC}^0$ and $\deg \le \mathrm{UC}^1$, i.e. $\mathrm{UC}_{\min} \ge \deg = 3^k$. Upper: $\mathrm{UC}_{\min} \le \mathrm{UC} = N$. Unlike the read-once functions in this file, $\deg \ne \mathrm{D}$ here, so the squeeze leaves a genuine $N^{0.39}$ window.
Rubinstein's function total \(N\) putative An unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as a sum of indicators of disjoint subcubes of codimension $\le w$, with no cancellation, so $\deg \le \mathrm{UC}^0$ and $\deg \le \mathrm{UC}^1$, i.e. $\deg \le \mathrm{UC}_{\min} \le \mathrm{UC}$. Here $\deg = \mathrm{UC} = N$, so both sides are pinned -- against $\mathrm{C}_{\min} = \sqrt N$.
Ambainis-Sun function total \(\Theta(N)\) putative An unambiguous $b$-certificate family of width $w$ writes $f$ (for $b=1$) or $1-f$ (for $b=0$) as a sum of indicators of disjoint subcubes of codimension $\le w$, so nothing cancels and $\deg(f) \le \min\{\mathrm{UC}^0,\mathrm{UC}^1\} = \mathrm{UC}_{\min}$. Here $\deg = (3k+2)^2 = \Theta(N)$ and $\mathrm{UC} = \Theta(N)$, so both sides are pinned.
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) putative An unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as a sum of indicators of disjoint subcubes of codimension $\le w$, with no cancellation, so $\deg \le \mathrm{UC}^0$ and $\deg \le \mathrm{UC}^1$, i.e. $\deg \le \mathrm{UC}_{\min} \le \mathrm{UC}$. Here $\deg = \mathrm{UC} = \Theta(n^2)$, so both sides are pinned -- against $\mathrm{C}_{\min} = n$.
Meiburg's tournament-subcube function total \(\ge 118.3^{\,d}\) putative An unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as the sum of the indicators of disjoint subcubes of codimension $\le w$, with no cancellation, so $\deg(f) \le \mathrm{UC}^0$ and $\deg(f) \le \mathrm{UC}^1$, hence $\deg \le \mathrm{UC}_{\min}$. With $\deg \ge \sqrt{\mathrm{bs}} \ge 118.3^{\,d}$ from the \(\deg(f)\) entry this is the bound; the alternative route $\mathrm{D} \le \mathrm{UC}_{\min}^2$ gives the same $\sqrt{14011^{\,d}}$.
Pointer functions total \(\widetilde\Omega(\sqrt n)\) Squeeze: $\mathrm{D}=O(\mathrm{UC}_{\min}^2)$ [BHT17] against $\mathrm{D}=\widetilde\Omega(n)$, which holds on every variant. BHT17
Cheat-sheet functions total \(\widetilde\Theta(\sqrt n)\) Upgraded to a two-sided bound: the upper bound below, plus $\mathrm{D}\le\mathrm{UC}_{\min}^2$ [BHT17] against $\mathrm{D}=\widetilde\Theta(n)$. The same uniqueness makes the $1$-certificates of $\mathrm{BKK}_{\mathrm{CS}}$ unambiguous, giving $\mathrm{Q}=\widetilde\Omega(\mathrm{UC}_{\min}^2)$ [BHT17, Cor. 2, attributed to AKK16]. This is the input to the \(f_{\mathrm{BHT}}\) amplification. BHT17
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^{3/2})\) Squeeze: $\mathrm{D}=O(\mathrm{UC}_{\min}^2)$ [BHT17] against $\mathrm{D}=\widetilde\Omega(n^3)$. Note this is the output of the amplification, not the $\mathrm{UC}_{\min}$ of the base function that sets the scale variable. BHT17
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Theta(n)\) Upper: $\mathrm{UC}_{\min}\le\mathrm{UC}_1\le 3\,\mathrm{C}(\mathrm{Eah}_n)\log^2 N=\widetilde O(n)$ [BBGJK21, Claim 17] -- read one certificate per copy plus the whole indexed cell. Lower: $\mathrm{D}\le\mathrm{UC}_{\min}^2$ [BHT17] against $\mathrm{D}=\widetilde\Omega(n^2)$. BBGJK21
Gilmer-Saks-Srinivasan functions total \(\Omega(n)\) Squeeze: $\mathrm{D}\le\mathrm{UC}_{\min}^2$ [BHT17] against $\mathrm{D}=\Theta(n^2)$ (equally, $\mathrm{UC}_{\min}\ge\min\{\mathrm{C}^0,\mathrm{C}^1\}=n$). Unlike \(f_{\mathrm{GPW}}\) there is no matching upper bound: the $1$-certificates here are not unambiguous, since several copies can be $1$ at once. BHT17
Goos-Pitassi-Watson partition-number function total \(\widetilde\Theta(\sqrt n)\) Upper $\mathrm{UC}_{\min}\le\mathrm{UC}_1=\widetilde O(\sqrt n)$; lower from $\mathrm{D}\le\mathrm{UC}_{\min}^2$ [BHT17] against $\mathrm{D}=\widetilde\Omega(n)$. The quadratic $\mathrm{D}$-vs-$\mathrm{UC}_{\min}$ gap is therefore optimal up to logarithms.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Theta(n^{1/3})\) Upper $\mathrm{UC}_{\min}\le\mathrm{UC}_1=\widetilde O(n^{1/3})$; lower from $\mathrm{D}\le\mathrm{UC}_{\min}^2$ [BHT17] against $\mathrm{D}=\widetilde\Omega(n^{2/3})$.
Ambainis' exact-quantum function total \(\Theta(3^d)\) Squeeze: an unambiguous certificate family is in particular a certificate family, so $\mathrm{UC}_{\min}\ge\min\{\mathrm{C}^0,\mathrm{C}^1\}=(3^d+1)/2$; and $\mathrm{UC}_{\min}\le\mathrm{UC}=3^d$. Both sides of this function are expensive to certify even ambiguously, so the [BHT17] route to a low-sensitivity function gets no traction here.
FORRELATION partial \(\Theta(n)\) Squeezed between $\mathrm{C}_{\min} = \Theta(n)$ and $\mathrm{UC} = \Theta(n)$. Note this is the one-sided minimum $\min\{\mathrm{UC}^0,\mathrm{UC}^1\}$, and both sides are already $\Theta(n)$ here.
k-FORRELATION partial \(O(kn)\) At most $\mathrm{UC}$.
Simon's problem partial \(O(2^{n/2})\) Squeezed between $\mathrm{C}_{\min} = 2$ and $\mathrm{UC} = \Theta(2^{n/2})$, and nothing sharper is available. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is worst-case within the cheaper side, not a minimum over inputs: the cheap two-query collision certificates on the "periodic" side are massively ambiguous, since a periodic $g$ contains $2^{n-1}$ of them, and disambiguating them by "first collision in lex order" costs the full $\Theta(2^{n/2})$ again.
Deutsch-Jozsa partial \(O(N)\) Squeezed between $\mathrm{C}_{\min} = 2$ and $\mathrm{UC} = N/2 + 1$. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is worst-case within the cheaper side, not a minimum over inputs, so the width-$2$ certificates on the balanced side do not give $O(1)$: a balanced input has $N^2/4$ disagreeing pairs, and an unambiguous family must still name one of them, which is the same obstruction that forces $\mathrm{UC} = \Omega(N)$.
Bernstein-Vazirani partial \(n\) putative Squeezed between $\mathrm{C}_{\min} = n$ and $\mathrm{UC} = n$.
Unique search partial \(1\) putative The $1$-certificates of that cover have width $1$, so $\mathrm{UC}^1 = 1$. With $\mathrm{D} = n$ this shows the total-function bound $\mathrm{D} \le \mathrm{UC}_{\min}^2$ [BHT17] is total-only.
Gap-Majority partial \(\Theta(n)\) putative Squeezed between $\mathrm{C}_{\min}$ and $\mathrm{UC}$, both $\Theta(n)$.
Gap-Majority at constant gap partial \(\Theta(n)\) putative Between $\mathrm{C}_{\min}$ and $\mathrm{UC}$.
Approximate index partial \(O(\sqrt{k\log k})\) Between $\mathrm{C}_{\min} = \Theta(1)$ and $\mathrm{UC}$.
Collision problem partial \(O(n)\) Squeezed between $\mathrm{C}_{\min} = 2$ and $\mathrm{UC} = n/2 + 1$. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is worst-case within the cheaper side, not a minimum over inputs: a two-to-one $g$ has $n/2$ collision pairs, so the width-$2$ collision certificates overlap heavily and no unambiguous family of constant width covers that side.
Element distinctness total \(O(n)\) Squeezed between $\mathrm{C}_{\min} = 2$ and $\mathrm{UC} = n$. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is worst-case within the cheaper side, not a minimum over inputs, so the width-$2$ collision certificates (which live on the $0$-side under the convention $\mathrm{ED}_n = 1$ on all-distinct inputs) do not give $O(1)$: an input with many repeats has many such pairs and the family must disambiguate them.
Ambainis-Belovs function partial \(O(n)\) At most $\mathrm{UC} = O(n)$.
Surjectivity total \(\Omega(n/\log n),\ O(n)\) $\mathrm{UC}^b\ge\mathrm{C}^b$ on each side, so $\mathrm{UC}_{\min}\ge\min\{\mathrm{C}^0,\mathrm{C}^1\}=\Theta(n/\log n)$, and $\mathrm{UC}_{\min}\le\mathrm{UC}=\Theta(n)$. Which side is cheaper is exactly the open part: the $0$-certificates are the short ones. BHT17
Triangle finding total \(\Theta(m^2)\)· putative $\mathrm{UC}^0\ge\mathrm{C}^0=\binom m2$, so the question is the $1$-side. For the input consisting of a single triangle $T$, any certificate must fix a triangle to $1$ and can only fix edges of $T$, so its $1$-part is exactly $T$. For two distinct triangles $T$ and $U$ the graph $T\cup U$ then lies in both certificates unless one of them fixes an edge of the other to $0$; orienting each such pair, some triangle beats at least half the others, and since each edge lies in $m-2$ triangles its $0$-set has size $\Omega(m^2)$. Hence $\mathrm{UC}^1=\Theta(m^2)$ too, and the ceiling is $\mathrm{UC}=\binom m2$. BHT17
Ordered search partial \(2\) $\mathrm{UC}_{\min}=\min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ [BHT17], and both sides are $2$ by the family of the \(\mathrm{UC}(f)\) entry; the floor is $\mathrm{C}_{\min}$ on the relevant side. BHT17
Inner product mod 2 total \(n/2\) putative That same partition gives the input $x = 0^m$ a certificate of size $m$, and no certificate anywhere is smaller than $\mathrm{C}_{\min} = m$.
Minsky-Papert one-in-a-box total \(N = m^3\) putative The parity argument recorded for \(\mathrm{UC}(f)\) works on both sides, so the one-sided relaxation buys nothing. $|f^{-1}(1)| = (2^{m^2}-1)^m$ is odd, and $|f^{-1}(0)| = 2^{N} - (2^{m^2}-1)^m$ is even minus odd, hence also odd. An unambiguous $b$-certificate family partitions $f^{-1}(b)$ into subcubes of sizes $2^{N-w_i}$; an odd total forces some $w_i = N$. So $\mathrm{UC}^0 = \mathrm{UC}^1 = N$ and $\mathrm{UC}_{\min} = N = m^3$, against $\mathrm{C} = m^2$. This is an extreme point of $\mathrm{C} \ge \mathrm{UC}_{\min}^{1.22}$-type separations in the opposite direction: here $\mathrm{UC}_{\min}$ is as far above $\mathrm{C}$ as $\mathrm{D} \le \mathrm{UC}_{\min}^2$ allows it to be useful at all.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{C}_{\min} \le \mathrm{UC}_{\min} \le \mathrm{UC}$, with $\mathrm{C}_{\min} = m-1$ and $\mathrm{UC} = \Theta(m)$ here.
Scorpion graphs total \(\Theta(m)\) Sandwiched: $\mathrm{C}_{\min} \le \mathrm{UC}_{\min} \le \mathrm{UC}$, with $\mathrm{C}_{\min} = m-1$ and $\mathrm{UC} = \Theta(m)$ here.
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) putative The one-sided relaxation buys nothing, but for a softer reason than on \(\mathrm{MP}_m\): the $0$-side is genuinely cheap to cover unambiguously and it is still $\Theta(N)$. Cover: for each connected vertex set $S \ni v_1$ with $S \ne V$, take the certificate that specifies every edge inside $S$ together with all $|S|(m-|S|)$ cross edges absent. Each disconnected graph matches exactly one of these -- $S$ is forced to be the component of $v_1$ -- so $\mathrm{UC}^0 \le N$, and $\mathrm{UC}^0 \ge \mathrm{C}^0 = \Theta(m^2)$. The lower bound on the min is $\mathrm{fbs} \le 2\,\mathrm{UC}_{\min} - 1$ (\(\mathrm{fbs}(f)\) vs \(\mathrm{UC}_{\min}(f)\)) with $\mathrm{fbs} = \Theta(m^2)$.
Ambainis–Iraids–Kokainis unambiguous DNF total \(O(n)\) Every 1-input satisfies exactly one term of width ≤9n. AIK26
Pabbaraju’s optimal unambiguous DNF total \(O(n)\) Theorem 1 gives UC¹=O(n). Pabbaraju26