Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR21-016 | 5th June 2021 19:29

Unambiguous DNFs and Alon-Saks-Seymour

RSS-Feed




Revision #1
Authors: Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari
Accepted on: 5th June 2021 19:29
Downloads: 205
Keywords: 


Abstract:

We exhibit an unambiguous $k$-DNF formula that requires CNF width $\tilde{\Omega}(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.



Changes to previous version:

Improved the separation to near-quadratic, which is optimal.


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
Downloads: 354
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