arXiv paper: Optimal Unambiguous DNFs and Alon-Saks-Seymour

A new arXiv paper by Chirag Pabbaraju presents unambiguous DNFs with width O(n) but 0-certificate complexity Ω(n²). Using their structure, the paper gives a constant-sized-gadget lifting theorem that preserves this certificate-complexity gap in communication complexity. The resulting bounds are described as an optimal refutation of the Alon–Saks–Seymour conjecture and an optimal communication lower bound for Clique versus Independent Set, improving results from Balodis, Ben-David, Göös, Jain and Kothari by several doubly logarithmic factors. The construction also yields an optimal quartic separation between certificate complexity and approximate degree, plus an Ω(√log c) sample-compression lower bound for multiclass concept classes with c labels.