Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR21-016 | 16th February 2021 10:29

#### Unambiguous DNFs from Hex

TR21-016
Authors: Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari
Publication: 16th February 2021 14:53
We exhibit an unambiguous $k$-DNF formula that requires CNF width $\tilde{\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).