Search papers, labs, and topics across Lattice.
This paper constructs unambiguous Disjunctive Normal Forms (DNFs) with width \(O(n)\) and \(0\)-certificate complexity \(\Omega(n^2)\), establishing a significant separation in complexity. By leveraging a lifting theorem with a constant-sized gadget, the authors translate this separation into a communication complexity context, yielding an optimal refutation of the Alon-Saks-Seymour conjecture and improving communication lower bounds for the Clique versus Independent Set problem. Additionally, the results extend to query complexity and learning theory, showcasing a quartic separation between certificate complexity and approximate degree, as well as a sample compression lower bound for multiclass concept classes.
Unambiguous DNFs can achieve a certificate complexity separation that leads to groundbreaking improvements in communication complexity results, including the Clique versus Independent Set problem.
We construct unambiguous DNFs having width $O(n)$ but $0$-certificate complexity $惟(n^2)$. By utilizing the special structure of these DNFs, we prove a lifting theorem with a constant-sized gadget that lifts the DNF to a communication problem, while losslessly translating the separation in certificate complexity to a separation in communication complexity. This leads to an optimal refutation of the Alon-Saks-Seymour conjecture, as well as an optimal communication lower bound for the Clique versus Independent Set problem, improving the previous results of Balodis, Ben-David, G枚枚s, Jain and Kothari (FOCS 2021, SICOMP 2023) by several doubly logarithmic factors. As further applications of our construction to query complexity and learning theory, we exhibit: (a) a family of Boolean functions that has an optimal quartic separation between certificate complexity and approximate degree, and (b) a sample compression lower bound of $惟(\sqrt{\log c})$ for multiclass concept classes over $c$ labels.
