arXiv cs.LG
· Papers
Optimal Unambiguous DNFs and Alon-Saks-Seymour
arXiv:2608.02533v1 Announce Type: cross Abstract: We construct unambiguous DNFs having width $O(n)$ but $0$-certificate complexity $Omega(n^2)$. By utilizing the special structure of these DNFs, we prove a lifting theorem with a constant-sized gadget that lifts the DNF to a communication problem, while losslessly tran