Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

#### Unambiguous DNFs and Alon-Saks-Seymour

Revision #1
Authors: Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari
Accepted on: 5th June 2021 19:29
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
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).