构造出宽度线性但0-证书复杂度二次的无歧义DNF，解决经典猜想
Optimal Unambiguous DNFs and Alon-Saks-Seymour
- 设计特殊结构的无歧义DNF，实现证书复杂度到通信复杂度的保真提升
- 证明了证书复杂度Ω(n²)与通信复杂度Ω(n²)的最优分离，击穿Alon-Saks-Seymour猜想
- 适用于研究通信复杂度、查询复杂度和学习理论的下界分析
我们构造出宽度为O(n)但0-证书复杂度为Ω(n²)的无歧义DNF。利用这些DNF的特殊结构，证明了一个常数大小小工具的提升定理，将DNF提升为通信问题时能无损传递证书复杂度的分离。这导致对Alon-Saks-Seymour猜想的最优反例，以及对团与独立集问题的最优通信下界，相比此前Balodis等人的结果改进了若干双对数因子。作为进一步应用，我们展示了：(a) 一类布尔函数，其证书复杂度与近似度数之间存在最优四次方分离；(b) 多类概念类在c个标签下的样本压缩下界为Ω(√(log c))。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。