Unambiguous DNFs from Hex
Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari · arXiv (Cornell University) · 2021
We exhibit an unambiguous k-DNF formula that requires CNF width Omega~(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).