🤖 machine learning

Optimal Unambiguous DNFs and Alon-Saks-Seymour

This paper constructs unambiguous DNFs with specific complexity properties to prove a constant-sized gadget lifting theorem, which yields an optimal refutation of the Alon-Saks-Seymour conjecture and improves communication lower bounds for the Clique versus Independent Set problem, while also establishing optimal separations in query complexity and new lower bounds in learning theory.

Original authors: Chirag Pabbaraju

Published 2026-08-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Chirag Pabbaraju

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a giant, complex puzzle, but you are only allowed to look at a few pieces at a time. In the world of computer science, this is a bit like trying to understand how hard a problem is to solve. Scientists use "complexity measures" to count how much effort, time, or information is needed to crack a code or solve a logic problem. Think of these measures as different rulers: one measures how many clues you need to be sure of an answer (called "certificate complexity"), while another measures how "wiggly" or complicated the shape of the problem is (called "degree" or "communication complexity").

For decades, researchers have been trying to figure out the relationship between these different rulers. It's like asking: "If a puzzle is hard to prove is true, does that automatically mean it's also hard to describe with simple math?" Sometimes, the answer is yes, but often, there are sneaky puzzles that look easy with one ruler but are actually nightmares with another. The big question has been: just how big can the gap be between these different ways of measuring difficulty? If we find a puzzle where the gap is massive, it tells us that our current tools for solving problems might be missing something fundamental. This isn't just about abstract math; it helps us understand the limits of computers, how much data we need to learn from, and even how to color maps or organize networks efficiently.

The Paper's Big Discovery: The Ultimate "Tricky" Puzzle

In this paper, the author, Chirag Pabbaraju, constructs a brand-new type of logic puzzle called an "unambiguous DNF." To visualize this, imagine a giant wall of light switches. A standard logic puzzle might say, "The light turns on if any of these specific combinations of switches are flipped." The tricky part here is "unambiguous." In this new puzzle, if the light turns on, there is exactly one specific combination of switches that caused it. No two combinations can ever do the same job. It's like a lock that only opens with one specific key, and if you find that key, you know for sure no other key could have opened it.

The author proves that they can build these puzzles so that they look incredibly simple to describe (they have a small "width," meaning the rules aren't very long), but they are terrifyingly hard to prove are off. Specifically, the paper shows that for these puzzles, the effort needed to prove the light is off is roughly the square of the effort needed to describe the rules. Before this, the best known examples had a gap that was slightly smaller, bogged down by extra "logarithmic" factors (think of these as tiny, annoying friction losses in a machine). This paper removes that friction entirely, showing the gap is a perfect, clean square.

Why This Matters: Shattering Old Beliefs

This discovery acts like a master key that unlocks several other doors in computer science. The author uses a clever trick called a "lifting theorem" to translate these logic puzzles into a game played by two people, Alice and Bob, who are trying to solve a problem together while only sending each other short messages.

1. The Graph Coloring Riddle (Alon-Saks-Seymour Conjecture)
There was a famous guess in math called the Alon-Saks-Seymour conjecture. It suggested that if you can break a network of connections (a graph) into a certain number of simple "clique" pieces, you shouldn't need too many colors to paint the nodes so no two connected nodes share a color. Previous work had already shown this guess was wrong, but the counter-examples were huge and messy.
Using the new "unambiguous DNF" puzzles, the author creates a counter-example that is optimal. They build a graph that requires a massive number of colors, yet can be broken down into a surprisingly small number of pieces. The size of this graph is the smallest possible to prove the point. It's like finding the smallest, lightest brick that can still topple a giant tower. The paper proves the gap between the number of pieces and the number of colors is as large as mathematically possible.

2. The "Clique vs. Independent Set" Game
This is a communication game where Alice holds a group of friends who all know each other (a clique), and Bob holds a group of strangers who don't know each other (an independent set). They want to know if they have any mutual friends. The paper shows that for certain groups, the amount of information they need to exchange to solve this is much higher than anyone thought possible, hitting the theoretical maximum limit.

3. Learning from Fewer Examples
Finally, the paper looks at machine learning. If you are teaching a computer to recognize many different types of objects (multiclass learning), how many examples do you need to compress the data into a small memory? The author shows that if you have a lot of different labels (categories), you need significantly more memory than previously thought—specifically, the memory size grows with the square root of the logarithm of the number of labels. This settles a debate about whether having more categories makes learning exponentially harder or just a little harder.

The Bottom Line

The paper doesn't just suggest these results; it provides rigorous mathematical proofs. It constructs specific, concrete examples of puzzles and graphs that force these limits. By removing the "logarithmic" noise that plagued previous attempts, the author has shown that the gaps between different ways of measuring computer difficulty are not just large—they are as large as they can possibly be. This refutes old guesses, tightens our understanding of what computers can and cannot do, and provides the most efficient "proof of concept" for these limits ever found.

=== SUMMARY ===

Technical Summary: Optimal Unambiguous DNFs and Alon-Saks-Seymour

1. Problem Statement and Context

This paper addresses three interconnected puzzles in computational complexity and combinatorics, originally posed by Balodis, Ben-David, G"o"os, Jain, and Kothari [2023]. These puzzles concern the separation between various complexity measures and their implications for graph theory and communication complexity.

Puzzle I (Unambiguous DNFs): Can there exist a family of Boolean functions where the 0-certificate complexity $C_0(f)$ is significantly larger than the unambiguous 1-certificate complexity $UC_1(f)$ ? Specifically, can $C_0(f) \ge \Omega(UC_1(f)^\alpha)$ for $\alpha > 1$ ? Previous work established $\alpha \approx 2$ up to polylogarithmic factors ( $\log^6 n$ ).

Puzzle II (Partial Functions): Can there exist a partial function $f$ and an undefined input $x$ where both the 0-certificate complexity $C_0(f, x)$ and 1-certificate complexity $C_1(f, x)$ are $\Omega(C(f)^\alpha)$ ? Previous bounds were $\alpha \approx 2$ up to $\log^2 n$ factors.

Puzzle III (Intersecting Hypergraphs): Can there exist an intersecting hypergraph $G$ and a coloring $c$ such that every $c$ -monochromatic hitting set has size $\Omega(r(G)^\alpha)$ , where $r(G)$ is the rank? Previous bounds were $\alpha \approx 2$ up to $\log^2 n$ factors.

These puzzles are linked to the Alon-Saks-Seymour conjecture, which posits that the chromatic number $\chi(G)$ of a graph is bounded by its biclique partition number $bp(G)$ plus one ( $\chi(G) \le bp(G) + 1$ ). This conjecture was disproven by Huang and Sudakov [2012], but the best known separation was suboptimal, involving doubly logarithmic factors: $\chi(G) \ge \exp(\Omega(\frac{\log^2 bp(G)}{(\log \log bp(G))^7}))$ .

Similarly, the Clique versus Independent Set (CIS) problem seeks a lower bound on the co-nondeterministic communication complexity. The best known lower bound was $\Omega(\frac{\log^2 n}{(\log \log n)^7})$ , while the upper bound is $O(\log^2 n)$ .

The paper aims to resolve these puzzles optimally, removing all polylogarithmic factors, and consequently providing an optimal refutation of the Alon-Saks-Seymour conjecture and an optimal lower bound for the CIS problem.

2. Methodology and Key Contributions

2.1 Construction of Optimal Unambiguous DNFs

The author constructs a family of unambiguous DNFs $f: \{0, 1\}^{n^2} \to \{0, 1\}$ with term-width $O(n)$ but 0-certificate complexity $\Omega(n^2)$ . This establishes $C_0(f) = \Omega(UC_1(f)^2)$ , resolving Puzzle I optimally.

Construction Details:

Set-Pair System: The DNF is derived from a "signed" set-pair system $\{(P_T, N_T)\}_T$ over a universe $U$ of size $n^2$ , partitioned into $n$ buckets $B_1, \dots, B_n$ of size $n$ .
Terms: Each term $T = (i, S)$ $T = (i, S)$ corresponds to a conjunction $C_T = (\bigwedge_{u \in P_T} x_u) \wedge (\bigwedge_{v \in N_T} \neg x_v)$ $C_{T} = (⋀_{u \in P_{T}} x_{u}) \land (⋀_{v \in N_{T}} \neg x_{v})$ .
- Positive Set ( $P_T$ ): For a bucket $B_i$ and a subset $S \subseteq B_i$ of size $n/2$ , $P_T = S$ .
- Negative Set ( $N_T$ ): Includes the complement $B_i \setminus S$ and "cross-bucket" sets $A_{i,j}(S)$ for $j \neq i$ .
Unambiguity: The construction ensures pairwise incompatibility: for any distinct terms $T, T'$ , either $P_T \cap N_{T'} \neq \emptyset$ or $P_{T'} \cap N_T \neq \emptyset$ . This guarantees that if one term is satisfied, all others are falsified.
Probabilistic Method: The cross-bucket sets $A_{i,j}(S)$ are constructed using random bijections (hashing) from buckets to $[n]$ . The probabilistic method ensures that with positive probability, the total size of negative sets remains $O(n)$ while maintaining the incompatibility condition.
Certificate Complexity: The 0-certificate complexity is lower-bounded by the hitting number of the family of positive sets $\{P_T\}$ . Since any hitting set must intersect every subset of size $n/2$ in every bucket, the hitting number is $\Omega(n^2)$ .

2.2 Constant-Gadget Lifting Theorem

To translate the separation in certificate complexity to communication complexity, the author derives a lifting theorem using a constant-sized gadget ( $k=3$ ), improving upon the standard lifting theorem of G"o"os et al. [2016] which uses a gadget of size $\Theta(\log n)$ .

The Gadget:
The gadget $g: \{0, 1\}^3 \times \{0, 1\}^3 \to \{0, 1\}$ is a cyclic function defined on $\mathbb{Z}_8$ :
$g(x, y) = 0 \iff y - x \in \{-1, 0, 1\} \pmod 8$
Otherwise, $g(x, y) = 1$ .

Spectral Analysis:
The lifting proof relies on analyzing the spectrum of a matrix $M$ associated with the lifted function $h = f \circ g^{n^2}$ .

The matrix $M$ is constructed as a sum of Kronecker products of matrices $W_0$ and $W_1$ , derived from the gadget $g$ .
The author proves that the minimum eigenvalue $\lambda_{\min}(M)$ is bounded below by $-d \cdot \rho^{n^2}$ for some $\rho < 1$ .
This spectral bound implies that any cover of the 0-entries of the communication matrix by monochromatic rectangles must have size $\exp(\Omega(n^2))$ .
This yields $\log \text{Cov}_0(h) = \Omega(n^2)$ , while $\log \text{Par}_1(h) = O(n)$ , achieving a quadratic separation without polylogarithmic losses.

2.3 Applications to Other Complexity Measures

Using the optimal unambiguous DNFs and the framework of Aaronson et al. [2016], the paper derives further separations:

Certificate Complexity vs. Approximate Degree: The author constructs a total Boolean function $G$ with $C(G) \ge \exp(\Omega(\tilde{\deg}(G)^4))$ . This closes the gap between the known upper bound $C(f) \le \exp(O(\tilde{\deg}(f)^4))$ and the previous lower bound of cubic separation. The construction involves a partial function $H$ with high certificate complexity but low-degree verifiable certificates, which is then totalized.
Certificate Complexity vs. Exact Degree and Sensitivity: The construction implies $C(f) \ge \Omega(\deg(f)^2)$ and $C(f) \ge \Omega(s(f)^3)$ , removing polylogarithmic factors from previous results.

2.4 Multiclass Sample Compression

The paper applies the graph construction to learning theory, specifically sample compression for multiclass concept classes.

Using the graph $G$ from the Alon-Saks-Seymour refutation (which has $2^{\Theta(n^2)}$ vertices and $\chi(G) = 2^{\Omega(n^2)}$ ), the author constructs a multiclass concept class with Natarajan dimension 1.
They show that any sample compression scheme for this class must have size $\Omega(\sqrt{\log c})$ , where $c$ is the number of labels. This resolves an open question by Pabbaraju [2024] regarding whether compression size must grow with the number of labels.

3. Key Results

Optimal Unambiguous DNFs (Theorem 1): Existence of unambiguous DNFs with $UC_1(f) = O(n)$ and $C_0(f) = \Omega(n^2)$ .
Constant-Gadget Lifting (Theorem 2): A lifting theorem using a 3-bit cyclic gadget that lifts the certificate complexity separation to a communication complexity separation with $\log \text{Cov}_0(h) = \Omega(n^2)$ .
Optimal Refutation of Alon-Saks-Seymour (Theorem 3): Existence of a graph family with $bp(G) = 2^{O(n)}$ and $\chi(G) = 2^{\Omega(n^2)}$ , satisfying $\chi(G) \ge \exp(\Omega(\log^2 bp(G)))$ . This matches the known upper bounds up to constants in the exponent.
Optimal CIS Lower Bound (Corollary 1.3): Existence of a Clique versus Independent Set problem with co-nondeterministic communication complexity $\Omega(\log^2 n)$ , matching Yannakakis's upper bound.
Quartic Separation (Theorem 4): Existence of Boolean functions with $C(f) \ge \exp(\Omega(\tilde{\deg}(f)^4))$ .
Sample Compression Lower Bound (Theorem 5): For multiclass concept classes with Natarajan dimension 1, the sample compression size is $\Omega(\sqrt{\log c})$ .

4. Significance and Claims

The paper claims to provide optimal resolutions to the three puzzles posed by Balodis et al. [2023], completely eliminating the polylogarithmic factors that previously limited the tightness of these separations.

Alon-Saks-Seymour: The result provides the strongest possible refutation of the conjecture, showing that the gap between chromatic number and biclique partition number is exponential in the square of the logarithm of the biclique partition number. The author notes that the size of the graphs constructed is itself optimal up to constant factors in the exponent, as a graph with chromatic number $\chi$ must have at least $\chi$ vertices.
Communication Complexity: The work establishes the first optimal lower bound for the Clique versus Independent Set problem, matching the long-standing upper bound.
Learning Theory: The sample compression result demonstrates that even for classes with low Natarajan dimension, the number of labels can force a polylogarithmic growth in the required sample compression size, partially resolving the open question posed by Pabbaraju [2024].

The author emphasizes that the constant-gadget lifting theorem is a crucial technical innovation. While general lifting theorems exist, they typically require gadgets of size $\Theta(\log n)$ , which introduces the doubly logarithmic factors in the final bounds. By exploiting the specific structure of the constructed unambiguous DNFs, the author derives a lifting theorem that works with a constant-sized gadget, thereby "shaving" the last remaining logarithmic factors.

The paper does not claim to solve the general log-rank conjecture but notes that their result improves the known quadratic lower bound for the log-rank conjecture by removing polylogarithmic factors. Similarly, while the sample compression bound is $\Omega(\sqrt{\log c})$ , the author acknowledges this is a partial resolution to the question of whether the bound must grow with $c$ , as the upper bound is polynomial in $c$ .