ECCC-Report TR21-016https://eccc.weizmann.ac.il/report/2021/016Comments and Revisions published for TR21-016en-usSat, 05 Jun 2021 19:29:03 +0300
Revision 1
| Unambiguous DNFs and Alon-Saks-Seymour |
Kaspars Balodis,
Shalev Ben-David,
Mika Göös,
Siddhartha Jain,
Robin Kothari
https://eccc.weizmann.ac.il/report/2021/016#revision1We 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.Sat, 05 Jun 2021 19:29:03 +0300https://eccc.weizmann.ac.il/report/2021/016#revision1
Paper TR21-016
| Unambiguous DNFs from Hex |
Shalev Ben-David,
Mika Göös,
Siddhartha Jain,
Robin Kothari
https://eccc.weizmann.ac.il/report/2021/016We 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).Tue, 16 Feb 2021 14:53:50 +0200https://eccc.weizmann.ac.il/report/2021/016