Unambiguous DNFs from Hex

Abstract

We exhibit an unambiguous k-DNF formula that requires CNF width Ω˜(k^1.5). Our construction is inspired by the board game Hex and it is vastly simpler than previous ones, which achieved at best an exponent of 1.22. Our result is known to imply several other improved separations in query and communication complexity (e.g., clique vs. independent set problem) and graph theory (Alon–Saks–Seymour problem).