---
title: "Optimal Unambiguous DNFs and the Alon-Saks-Seymour Conjecture Revisited"
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 conjecture","Clique versus Independent Set","Lifting theorem","Unambiguous DNF","Certificate complexity","Communication complexity"]
---

# Optimal Unambiguous DNFs and the Alon-Saks-Seymour Conjecture Revisited

## AI commentary

> The most striking aspect of this paper is how it unifies several seemingly independent optimal lower bounds under a single combinatorial construction, with solid proof techniques. If you work in communication complexity, Boolean function complexity, or learning theory, these results are almost directly citable; even if you just appreciate elegant connections between complexity models, this paper is worth reading.

## At a glance

This paper constructs unambiguous DNFs of width O(n) with 0-certificate complexity Ω(n²), and uses their special structure to prove a lifting theorem with a constant-sized gadget that losslessly translates the certificate complexity separation into a communication complexity separation. This yields an optimal refutation of the Alon-Saks-Seymour conjecture and an optimal communication lower bound for the Clique versus Independent Set problem, improving upon previous results by Balodis, Ben-David, Göös, Jain and Kothari by several doubly logarithmic factors. Further applications include an optimal quartic separation between certificate complexity and approximate degree in query complexity, and a sample compression lower bound of Ω(√log c) for multiclass concept classes over c labels.

## Key points

- Constructs unambiguous DNFs of width O(n) with 0-certificate complexity Ω(n²), achieving an optimal separation.
- Proves a lifting theorem with a constant-sized gadget that losslessly translates certificate complexity separation into communication complexity separation.
- Optimally refutes the Alon-Saks-Seymour conjecture and provides an optimal communication lower bound for Clique versus Independent Set.
- Additional applications: quartic separation between certificate complexity and approximate degree, and a sample compression lower bound of Ω(√log c) for multiclass concept classes.

## Full text

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.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_ad551f46d68bd91b64982bb8