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

Pabbaraju’s certificate–sensitivity separator

Log-free $\mathrm{C}=\Omega(\mathrm{s}^3)$.

total separating-total

Description

Apply the sensitivity-reducing transformation of [BHT17] and the construction in Appendix C of [Pabbaraju26] to the optimal one-sided unambiguous-DNF separator Pabbaraju’s optimal unambiguous DNF. Corollary 1.3 gives $\mathrm{C}\ge\Omega(\mathrm{s}^3)$ without the logarithmic loss in the earlier construction. The full definition is in that appendix.

Formal definition

Let $f$ be Pabbaraju’s optimal unambiguous DNF and $u=\mathrm{UC}^1(f)=\Theta(n)$. Let $f'(x,y,z)$ accept iff $f(x)=f(y)=f(z)=1$ and all three inputs satisfy the same unique DNF term. Define $$F_n=\mathrm{OR}_{3u}\circ f'.$$ Appendix C of [Pabbaraju26] proves $\mathrm{s}(F_n)\le3u$ and $\mathrm{C}^0(F_n)=3u\mathrm{C}^0(f')\ge3u\mathrm{C}^0(f)=\Omega(u^3)$.

Measure values

MeasureValueNotes
\(\mathrm{s}(f)\) Sensitivity \(O(n)\) Appendix C: s(F)≤3u, u=Θ(n). Pabbaraju26
\(\mathrm{C}(f)\) Certificate complexity \(\Omega(n^3)\) Appendix C: C⁰(F)≥3u C⁰(f)=Ω(n³). Pabbaraju26

Cited as a witness by