Optimal Unambiguous DNFs and Alon-Saks-Seymour

The gist Optimal Unambiguous DNFs and Alon-Saks-Seymour constructs unambiguous DNFs with width O(n) but 0-certificate complexity Ω(n 2), leading to an optimal refutation of the Alon-Saks-Seymour conjecture and improved lower bounds for communication complexity problems like Clique versus Independent Set.

Optimal Unambiguous DNFs

The paper introduces a construction of unambiguous DNFs having width O(n) but 0-certificate complexity Ω(n 2), which is achieved by utilizing a special structure based on a set-pair system T over a universe U with U = n squared, where each term CT is defined as CT = u∈PT xu ∧ v∈NT ¬xv (6). The crucial advantage of this formulation allows for the construction of a sufficient condition for unambiguity in terms of a pairwise incompatibility constraint on the set-pair system T. By choosing specific positive sets PT and negative sets NT, the authors ensure that every term is satisfied by at most one input x, which proves f is an unambiguous DNF. The 0-certificate complexity C0(f) is shown to be at least the hitting number of the family of positive sets P, where τ (P) = H ≥ n(n/2 + 1) = Ω(n 2).

Optimal Solutions to Puzzles I, II and III

The construction yields optimal solutions for the three puzzles studied by Balodis et al. [2023], with no polylogarithmic factors The construction provides a family of partial functions f such that there exists an input x ∈ f−1(∗) satisfying min C0(f, x), C1(f, x) ≥ Ω(n 2), while the certificate complexity C(f) ≤ O(n). This result is derived by applying the implication Puzzle I → Puzzle II given in [Balodis et al., 2023] together with Theorem 1 The resulting separation for partial functions is min C0(f, x), C1(f, x) ≥ Ω(C(f) 2), which improves over the bound in (2) by a log2(n) factor.

Application: Alon-Saks-Seymour and Clique versus Independent Set

The separation derived from the unambiguous DNFs is applied to the Alon-Saks-Seymour conjecture, leading to an optimal refutation of this conjecture. Theorem 3 shows that there exists a graph G having 2Θ(n 2) vertices that admits a biclique partition of size 2O(n) but has chromatic number 2omega(n 2), which implies χ(G) ≥ exp Ω log2(bp(G)). This matches the upper bounds of Mubayi and Vishwanathan [2009], Fox [2026] up to constants in the exponent. Furthermore, this separation leads to an optimal Ω log2(n) lower bound for the Clique versus Independent Set problem's co-nondeterministic communication complexity.

Constant-gadget Lifting

The paper demonstrates a constant-sized gadget lifting theorem that translates the DNF separation into a communication problem with a constant-sized gadget. Theorem 2 establishes the existence of a gadget function g: 3×3 → 1 such that for all large enough n, for the DNF f constructed in Theorem 1, denoting by h the lifted communication problem f◦g n 2: 3n squared × 3n squared → 1 it holds that log Cov0(h) = Ω(n 2). This allows for an optimal refutation of the Alon-Saks-Seymour conjecture and a lower bound of D(h) ≥ Ω(log rank(h)) squared.

Quartic Separation between Certificate Complexity and Approximate Degree

The construction yields a quartic separation between certificate complexity and approximate degree. Theorem 4 proves that there exists a family of Boolean functions f with C(f) ≥ Ω(e deg(g f) 4). This is achieved by constructing a total function G for which C(G) ≥ Ω(n 2), and showing that its approximate degree deg g G ≤ O(√n). The proof involves using the cheat-sheet framework to certify a partial function H that is hard to certify, leading to the desired quartic separation.

Lower Bound for Multiclass Sample Compression

The paper provides a lower bound on sample compression schemes for multiclass concept classes. Theorem 5 proves that there is a family of multiclass concept classes having Natarajan dimension 1, for which the size of any valid sample compression scheme as a function of the number of labels c is at least Ω√log c. This lower bound is established by using the graph G from Theorem 3, where the chromatic number is lower-bounded in terms of the number of labels.

Optimality of Corollaries 1.1 and 1.2

The paper provides direct upper bounds showing that the separations in Corollary 1.1 and Corollary 1.2 are optimal up to constant factors. Claim A.2 proves that for any intersecting hypergraph G = (V, E) and for any coloring c: V → 0, there exists a c-monochromatic hitting set that has size at most r(G) squared.

Proof of Corollary 1.5

The proof of Corollary 1.5 shows that there exists a family of Boolean functions f with C(f) ≥ Ω(s(f) 3). This is achieved by applying a desensitizing transformation to the unambiguous DNF from Theorem 1, resulting in a function F = OR3u◦ f' where s(F) ≤ 3u and C0(F) ≥ 3u · C0(f) = Ω(s(f) 3). This result is based on the work of Ben-David et al. [2017].

Conclusion

The paper concludes by showing that the minimum eigenvalue of the matrix M satisfies λmin ≥ -dρn 2/5000, which establishes Theorem 2 with a lower bound of −dρn squared on the smallest eigenvalue of M. This result is achieved by analyzing the Fourier spectrum and bounding elementary symmetric polynomials using Lemma 4.2. The analysis confirms that every eigenvalue λξ corresponding to the eigenvectors χξ is at least −dρn 2/5000, establishing Theorem 2.

Remark 1 (General Constant-gadget Lifting)

The paper notes that the constant-gadget lifting theorem applies specifically to unambiguous DNFs from Theorem 1, and the analysis does not yet extend to all Boolean functions. The analysis crucially uses the form of the DNF from Theorem 1 in defining the matrix M and expressing its eigenvalues as elementary symmetric polynomials.

Acknowledgements

The paper acknowledges support from Moses Charikar’s and Greg Valiant’s Simons Investigator Awards, and a Google PhD Fellowship. The authors also thank Greg Valiant for encouraging them to think about multiclass sample compression again.

References

The paper lists numerous references including works by Aaronson et al. [2], Ben-David et al. [1], G¨o¨os [1], and Balodis et al. [1]. The reference list is extensive, covering topics from communication complexity to query complexity and learning theory.

Optimality of Corollaries 1.1 and 1.2

The paper gives direct upper bounds showing that the separations in Corollary 1.1 and Corollary 1.2 are optimal up to constant factors. Claim A.2 proves that for any intersecting hypergraph G = (V, E) and for any coloring c: V → 0, there exists a c-monochromatic hitting set that has size at most r(G) squared.

Proof of Theorem 3

The proof of Theorem 3 relies on the lifting theorem to lift the unambiguous DNF separation to a separation in communication complexity. The resulting function h satisfies log Cov0(h) ≥ Ω(n 2), log Par1(h) ≤ O(n), allowing for the application of Lemma 3.5 from Cheung et al. [2023] to convert h into a graph G having 2Θ(n 2) vertices, satisfying bp(G) ≤ Par1(h) squared ≤ 2O(n), and χ(G) ≥ p Cov0(h) ≥ 2Ω(n 2).

Proof of Corollary 1.5

The proof of Corollary 1.5 is essentially contained in the proofs of Lemma 12 and Theorem 1 in Ben-David et al. [2017].

1. textbfImproved Refutation of Alon-Saks-Seymour Conjecture (Clique vs. Independent Set): We can construct graphs G with a chromatic number 2omega(n 2) and a biclique partition number 2O(n), providing a concrete family of graphs satisfying χ(G) ≥ exp omega log2(bp(G)) with fewer vertices, specifically requiring only 2Θ(n 2) vertices instead of the previous lower bounds like 4n 4log3 n in related literature.

2. textbfOptimal Communication Lower Bound for Clique vs. Independent Set: We can establish a co-nondeterministic communication complexity lower bound of at least omega(log2(n)) for the CISG problem on graphs G, matching the upper bound of Yannakakis [1988] up to constant factors, by leveraging the optimal unambiguous DNF separation and a constant-gadget lifting theorem.

3. textbfEnhanced Separation between Certificate Complexity and Approximate Degree: We can exhibit a family of Boolean functions f with C(f) ≥ omega(e deg(g f) 4), closing the gap between the upper bound C(f) ≤ Oe(deg(f) 3) and the lower bound derived from unambiguous DNFs, which is achieved via a quartic separation proof structure.

4. textbfSuper-Sample Compression Lower Bound: We can prove that for multiclass concept classes having Natarajan dimension 1, the size of any valid sample compression scheme must be at least omega(√log c), providing a partial resolution to the open question regarding whether this lower bound must grow with the number of labels c.

5. textbfImproved Sensitivity Lower Bound: We can construct functions f with C(f) ≥ omega(s(f) 3), which is stronger than previously known bounds, by utilizing the desensitizing transformation applied to the unambiguous DNF and showing that its OR-sum F has a certificate complexity of 3u · C0(f') ≥ 3u · C0(f) = omega(s(F) 3).

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 c) for multiclass concept classes over c labels.