Q The Query Complexity Zoo
PabbarajuDNF

Pabbaraju’s optimal unambiguous DNF

$\mathrm{C}^0=\Omega(n^2)$ and $\mathrm{UC}^1=O(n)$, without logarithmic losses.

total separating-total arity: $n^2$ bits

Description

The unambiguous DNF of Theorem 1 on $n$ blocks of $n$ bits. Terms select a block and a half-sized positive set, and signed set-pair systems specify the cross-block negative literals (Section 3). Every term has width $O(n)$, distinct terms are incompatible, and the all-zero input needs $\Omega(n^2)$ bits to certify rejection.

Formal definition

Fix disjoint blocks $B_1,\ldots,B_n$ of size $n$ and $k=\lfloor n/2\rfloor$. For every unordered pair $\{i,j\}$ choose bijections $\pi_i^{ij}:B_i\to[n]$, $\pi_j^{ij}:B_j\to[n]$ with $\sum_{j\ne i}\min_{u\in S}\pi_i^{ij}(u)=O(n)$ uniformly over $i$ and $k$-subsets $S\subseteq B_i$; [Pabbaraju26, Section 3] proves such choices exist. Put $a_{ij}(S)=\min_{u\in S}\pi_i^{ij}(u)$ and $A_{ij}(S)=\{v\in B_j:\pi_j^{ij}(v)\le a_{ij}(S)\}$. $$f_n(x)=\bigvee_{i,\,S\subseteq B_i,\,|S|=k} \left(\bigwedge_{u\in S}x_u\right) \left(\bigwedge_{v\in(B_i\setminus S)\cup\bigcup_{j\ne i}A_{ij}(S)}\neg x_v\right).$$

Measure values

MeasureValueNotes
\(\mathrm{C}^0(f)\) 0-certificate complexity \(\Omega(n^2)\) Theorem 1. Pabbaraju26
\(\mathrm{C}(f)\) Certificate complexity \(\Theta(n^2)\) C≥C₀ and C≤n². Pabbaraju26
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(O(n)\) Theorem 1 gives UC¹=O(n). Pabbaraju26
\(\deg(f)\) Exact degree \(O(n)\) Corollary 1.2: exact representation by the sum of disjoint term indicators. Pabbaraju26

Cited as a witness by