Q The Query Complexity Zoo
\(\overline f_{\mathrm{AIK}}\)

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

MeasureValueNotes
\(\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

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.