Complement of the Ambainis–Iraids–Kokainis DNF
Logarithm-free quadratic $\mathrm{C}$ versus certain-acceptance one-sided $\mathrm{R}^1$ separation.
total composed arity: $N=n^2$ bits
Description
Take the Boolean complement of \(\mathrm{AIKuD}\). The AIK one-sided algorithm rejects every negative DNF input with certainty and accepts positive inputs with probability at least 2/3. Flipping its answer gives an algorithm with certain acceptance on every positive input of the complement, matching this catalog’s \(\mathrm{R}^{1}(f)\) convention.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{C}(f)\) Certificate complexity | \(\Theta(n^2)\) | Certificate complexity is invariant under output complementation; Theorem 2.2. AIK26 |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Theta(n)\) | Bounded-error randomized complexity is invariant under output complementation. AIK26 |
| \(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity | \(\Theta(n)\) | R¹(¬f)=R_RP(f) under the catalog conventions. Theorem 2.2 gives the upper bound; C=O(R²) gives the matching lower bound. AIK26 |
Cited as a witness by
-
\(\mathrm{C}(\overline f_n)=\Theta(\mathrm{R}^{1}(\overline f_n)^2)\)
Notes
The paper calls its certain-rejection measure $\mathrm{R}_1$; this catalog calls it \(\mathrm{R}_{\mathrm{RP}}(f)\). The legacy \(\mathrm{R}^{1}(f)\) entry fixes the other output side. The original and complementary DNF witnesses therefore settle both one-sided columns without identifying the two measures on the same function.