Unambiguous DNFs and Alon-Saks-Seymour

Kaspars Balodis, Shalev Ben-David, Mika Göös +2

We exhibit an unambiguous k-DNF formula that requires CNF width $\tilde{\Omega }(k^2)$, which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the…