Optimal Unambiguous DNFs and Alon-Saks-Seymour
2026-08-03 • Computational Complexity
Computational ComplexityDiscrete MathematicsMachine Learning
AI summaryⓘ
The authors build special logical formulas (DNFs) that are simple in one way but surprisingly complex in another. They use these formulas to connect two different types of problems, showing that difficulty in one translates directly to the other without losing strength. This solves a longstanding question in graph theory and improves known results in communication complexity. Additionally, their approach helps demonstrate new limits in how efficiently certain functions can be approximated and how much data is needed to learn complex patterns.
Disjunctive Normal Form (DNF)Certificate ComplexityCommunication ComplexityAlon-Saks-Seymour ConjectureClique vs Independent Set ProblemQuery ComplexityApproximate DegreeSample CompressionMulticlass Concept ClassesLifting Theorem
Authors
Chirag Pabbaraju
Abstract
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.