---
title: "最优无歧义 DNF 与 Alon-Saks-Seymour 猜想的新证明"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2608.02533v1"
permalink: "https://feed.astralor.com/items/itm_ad551f46d68bd91b64982bb8"
published: "2026-08-03T17:26:54.000Z"
score: 76
channel: "ai"
tags: ["Alon-Saks-Seymour 猜想","Clique vs Independent Set","提升定理","无歧义 DNF","证书复杂度","通信复杂度"]
---

# 最优无歧义 DNF 与 Alon-Saks-Seymour 猜想的新证明

## AI 点评

> 这篇论文最值得关注的地方在于它把多个看似独立的最优下界统一到了一个组合构造之下，证明功力非常扎实。如果你是做通信复杂度、布尔函数复杂度或学习理论的人，这里的结果几乎都值得直接引用；哪怕是单纯想看看复杂度类之间的优雅联系，这篇文章也很有阅读价值。

## 速览

本论文构造了宽度为 O(n) 但 0-证书复杂度为 Ω(n²) 的无歧义 DNF，并利用其特殊结构证明了一个常尺寸 gadget 的提升定理，将证书复杂度的分离无损地转化为通信复杂度分离。这导致对 Alon-Saks-Seymour 猜想的最优反驳，以及 Clique 与 Independent Set 问题的最优通信下界，比 Balodis 等人此前的结果改进了多个双对数因子。进一步应用包括：查询复杂度中证书复杂度与近似度之间的四次分离，以及多类概念类的样本压缩下界 Ω(√log c)。

## 关键点

- 构造宽度 O(n) 但 0-证书复杂度 Ω(n²) 的无歧义 DNF，实现最优分离。
- 证明常尺寸 gadget 的提升定理，将证书复杂度分离无损转化为通信复杂度分离。
- 最优反驳 Alon-Saks-Seymour 猜想，并给出 Clique vs Independent Set 问题的最优通信下界。
- 额外应用：查询复杂度中证书复杂度与近似度的四次分离，及多类概念类的样本压缩下界 Ω(√log c)。

## 全文

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.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_ad551f46d68bd91b64982bb8