Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR21-016 | 16th February 2021 10:29

Unambiguous DNFs from Hex

RSS-Feed




TR21-016
Authors: Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari
Publication: 16th February 2021 14:53
Downloads: 214
Keywords: 


Abstract:

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).



ISSN 1433-8092 | Imprint