Unambiguous DNFs and Alon-Saks-Seymour


We exhibit an unambiguous k-DNF formula that requires CNF width Ω̃(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.

Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)