@inproceedings{33a3c707a4384139a4db6aa7f98de16a,
title = "Unambiguous DNFs and Alon-Saks-Seymour",
abstract = "We exhibit an unambiguous k-DNF formula that requires CNF width tildeΩ(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.",
keywords = "Alon-Saks-Seymour, Communication complexity, Query complexity, Unambiguous DNF",
author = "Kaspars Balodis and Shalev Ben-David and Mika Goos and Siddhartha Jain and Robin Kothari",
note = "Publisher Copyright: {\textcopyright} 2022 IEEE.",
year = "2022",
doi = "10.1109/FOCS52979.2021.00020",
language = "English",
isbn = "9781665420556",
volume = "2022-February",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
publisher = "IEEE",
pages = "116--124",
booktitle = "Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021",
}