Publication

Unambiguous DNFs and Alon-Saks-Seymour

Mika Tapani Göös
2022
Conference Papers

Abstract

We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over 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.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Unambiguous DNFs and Alon-Saks-Seymour

Chat with Graph Search

Towards an Understanding of Hydraulic Sensitivity: Graph Theory Contributions to Water Distribution Analysis

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al

The Power of Two Matrices in Spectral Algorithms for Community Recovery