Q The Query Complexity Zoo
\(\mathrm{AIKuD}\)

Ambainis–Iraids–Kokainis unambiguous DNF

Log-free optimal separation $\mathrm{C}=\Theta(\mathrm{R}_{\mathrm{RP}}^2)$.

total separating-total arity: $n^2$ bits (even $n$)

Description

Partition $n^2$ bits into $n$ blocks $x_i$. Fix lists $P_j\in[n]^{8n}$ satisfying Lemma 3.1. For a half-sized set $S$, put $m_j(S)=\min\{a:P_j(a)\in S\}$ and $A_{ij}(S)=\{P_i(a):1\le a\le m_j(S)\}$. Term $T_{i,S}$ fixes block $i$ to the characteristic vector of $S$ and requires $x_j(p)=0$ for $j\ne i$ and $p\in A_{ij}(S)$. Accept iff a term is satisfied. The lists guarantee term width at most $9n$; terms are pairwise incompatible.

Formal definition

Fix even $n$, $k=n/2$, and lists $P_j\in[n]^{8n}$ satisfying Lemma 3.1 of [AIK26]. Put $m_j(S)=\min\{a:P_j(a)\in S\}$ and $A_{ij}(S)=\{P_i(a):1\le a\le m_j(S)\}$. $$T_{i,S}(x)=\left(\bigwedge_{p\in S}x_i(p)\right) \left(\bigwedge_{p\notin S}\neg x_i(p)\right) \left(\bigwedge_{j\ne i}\bigwedge_{p\in A_{ij}(S)}\neg x_j(p)\right), \qquad f_n(x)=\bigvee_{i\in[n],\,|S|=k}T_{i,S}(x).$$

Measure values

MeasureValueNotes
\(\mathrm{C}(f)\) Certificate complexity \(\Theta(n^2)\) Theorem 2.2. AIK26
\(\mathrm{C}^0(f)\) 0-certificate complexity \(\Theta(n^2)\) Lemma 3.4 and the input-size ceiling. AIK26
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(\Theta(n)\) Theorem 2.2 and the universal C = O(R²) bound. AIK26
\(\mathrm{R}_{\mathrm{RP}}(f)\) One-sided randomized queries with certain rejection \(\Theta(n)\) Theorem 2.2; accepts only after a term is verified. AIK26
\(\chi(f)\) Conflict complexity \(\Theta(n)\) putative Derived: AIK26 gives C=Θ(n²), R=Θ(n). The chain χ≤χ̄=O(LR)=O(R) gives χ=O(n); C≤bs² and χ≥(bs+1)/2 give χ=Ω(n). Thus C=Θ(χ²), refuting χ=Ω(C). AIK26 Nisan91 Li18 BBGM22
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity \(O(n)\) Every 1-input satisfies exactly one term of width ≤9n. AIK26
\(\mathrm{C}^1(f)\) 1-certificate complexity \(O(n)\) The satisfied term is a certificate. AIK26
\(\deg(f)\) Exact degree \(O(n)\) A disjoint DNF equals the sum of its term indicators, each of degree ≤9n. AIK26

Separations its values prove — computed, not recorded

Read straight off the table above by comparing two values: no relation record states these, and where one does and says more, the record wins and the pair is not listed here. 5 in total.

Cited as a witness by