这篇论文用特制的DNF把Alon-Saks-Seymour猜想彻底推翻，还把Clique vs Independent Set的通信下界拉到最优，复杂度理论党别错过。
论文构造了一族无歧义DNF，宽度为O(n)，但0-证书复杂度达到Ω(n^2)。借助常数大小的提升引理，将证书复杂度分离转化为通信复杂度分离，得到Clique vs Independent Set问题的最优通信下界，并最优反驳了Alon-Saks-Seymour猜想。相比Balodis等人（FOCS 2021）的结果，通信下界改进多个双对数因子。该构造还给出证书复杂度与近似度之间的四次分离，以及c个标签上多类概念类的样本压缩下界Ω(√log c)。
Optimal Unambiguous DNFs and Alon-Saks-Seymour
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.