  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 Alon--Saks--Seymour problem
in graph theory (posed in 1991), which asks: How large a gap can there be
between the chromatic number of a graph and its biclique partition number? Our
result is also known to imply several other improved separations in query and
communication complexity.

Computational Complexity