Pabbaraju’s certificate–sensitivity separator
Log-free $\mathrm{C}=\Omega(\mathrm{s}^3)$.
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
| Measure | Value | Notes |
|---|---|---|
| \(\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
-
\(\mathrm{C}(f_n) = \Omega(\mathrm{s}(f_n)^3)\)