REVIEW 5 minor 30 references
Optimal Unambiguous DNFs and Alon-Saks-Seymour
T0 review · 0 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash
Pith's one-line read This paper constructs unambiguous DNFs of width O(n) with 0-certificate complexity Ω(n^2), and proves a constant-gadget lifting theorem that yields an optimal refutation of the Alon–Saks–Seymour conjecture.
desk verdict Strong paper: optimal quadratic separation for unambiguous DNFs and an optimal ASS refutation, with detailed proofs; the only real caveat is an imported lemma in Appendix B. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is a signed set-pair system (P_T, N_T) with pairwise incompatibility, giving unambiguous DNFs. The lifting uses a constant-sized cyclic gadget g on Z_8: g(x,y)=0 iff y−x∈{−1,0,1} mod 8, whose associated Cayley graph has a known Fourier eigenbasis. The paper forms a matrix M as a sum of Kronecker products of 8×8 matrices W_0 and W_1, and shows that its minimum eigenvalue is at least −d·ρ^{n^2/5000}; that spectral bound, via the 'bounded independent sets' lemma, forces log Cov0(h) to be Ω(n^2).
What would settle it
For a fixed small n (say n=8), explicitly construct the DNF and compute its exact 0-certificate complexity and term width; if C0(f) is not Ω(n^2), the core separation fails. Alternatively, compute the minimum eigenvalue of the matrix M for the cyclic gadget and compare it with −d·ρ^{n^2/5000}; a violation at any explicit n invalidates Theorem 2.
Extended reading notes
Core claim
The paper's central discovery is an explicit set-pair system—each DNF term gets a positive set and a negative set with a pairwise incompatibility condition—that guarantees unambiguity. Randomly chosen bijections between bucket pairs keep the total term width O(n) with high probability, while any 0-certificate must hit every positive set, forcing size Ω(n^2). The special structure of these DNFs supports a constant-gadget lifting theorem: the cyclic gadget g(x,y)=0 iff y−x∈{−1,0,1} mod 8 lifts the function to a communication problem h with log Cov0(h)=Ω(n^2), while log Par1(h)=O(n). The proof analyzes the spectrum of a sum of Kronecker products of 8×8 matrices, showing the minimum eigenvalue i
Load-bearing premise
The final graph-theoretic theorem depends on a cited lemma (Appendix B) that converts a communication-complexity separation into a graph with the promised biclique partition and chromatic numbers; should that lemma carry hidden constant-factor or logarithmic losses, the optimal refutation would not follow.
Editorial extensions
If this is right
- Refutes Alon–Saks–Seymour optimally: infinitely many graphs have bp(G)=2^{O(n)} and χ(G)=2^{Ω(n^2)}, so χ(G) ≥ exp(Ω(log^2 bp(G))), matching the known upper bound up to constants.
- Gives an optimal Ω(log^2 n) co-nondeterministic communication lower bound for the Clique versus Independent Set problem, matching the known upper bound.
- Settles the unambiguous DNF puzzle: C0(f) = Ω(UC1(f)^2) with no polylogarithmic loss, the best possible exponent.
- Yields C(f) = Ω~(gdeg(f)^4), closing the gap between certificate complexity and approximate degree up to polylogarithmic factors.
- Produces multiclass concept classes of Natarajan dimension 1 with sample-compression size Ω(√log c).
Reading between the lines
- The same set-pair construction might give log-free separations for other pairs of query-complexity measures, such as sensitivity versus block sensitivity or decision tree depth, where polylog factors are currently tolerated.
- The constant-gadget lifting theorem is deliberately specific to these DNFs; a general version would imply similar optimal gaps for arbitrary functions and would likely require substantially different spectral machinery.
- Because the witness graph has essentially the minimum possible number of vertices for its chromatic number, the construction may be a natural starting point for improved biclique-partition lower bounds on other graph parameters.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper constructs unambiguous DNFs of width O(n) over n^2 variables whose 0-certificate complexity is Ω(n^2), giving an optimal resolution of Balodis et al.'s Puzzle I up to constant factors (Theorem 1). It then proves a lifting theorem for these DNFs with a constant-sized cyclic gadget (Theorem 2), showing that the lifted communication problem has log Cov0 = Ω(n^2). Combining this with an external reduction (Cheung et al., Lemma 3.5), it obtains an optimal refutation of the Alon-Saks-Seymour conjecture: graphs with 2^{Θ(n^2)} vertices, bp(G)=2^{O(n)}, and χ(G)=2^{Ω(n^2)} (Theorem 3), and consequently an optimal Ω(log^2 n) lower bound for Clique vs. Independent Set. The same DNF construction is used to prove a quartic separation between certificate complexity and approximate degree (Theorem 4), a cubic certificate-vs-sensitivity separation, and a multiclass sample-compression lower bound of Ω(√log c) for Natarajan dimension 1 classes (Theorem 5). Appendix A supplies matching upper bounds for Puzzles II and III.
Significance. If correct, the paper resolves the Alon-Saks-Seymour problem up to constant factors in the exponent, matching the known upper bound of Mubayi–Vishwanathan and Fox; this is a major result in communication complexity and graph theory. The paper is unusually detailed: Theorem 1's set-pair proof is elementary and complete; Theorem 2's spectral analysis is worked out fully, including the Fourier eigenvalues of the cyclic gadget, the |q_r|≤3/5 bound, and the delicate symmetric-polynomial estimates of Lemma 4.2; Theorem 4's verifier is specified concretely; and Theorem 5's reduction is explicit. The central derivation is not circular: the ASS separation is never used to fix constants, and the main constructions are derived from first principles. The only external dependency is the Cheung et al. conversion in Appendix B, which is standard and robust to constant/log losses; I see no correctness risk in relying on it, though the manuscript would be more self-contained with the lemma stated.
minor comments (5)
- [Appendix B / Theorem 3] The proof of Theorem 3 imports Cheung et al. [2023, Lemma 3.5] without stating the lemma, and then uses the consequences bp(G) ≤ Par1(h)^2 and χ(G) ≥ sqrt(Cov0(h)). Please state the lemma explicitly and, if space permits, reproduce its proof or at least give the exact conditions and constants. I regard this as an exposition issue rather than a correctness gap: the conversion is standard, and even constant or log-factor losses would preserve the final exponential separation.
- [§4 / Corollary 4.1] The bound log Par1(f∘g^n) ≤ O(k·UC1(f)) is used as 'known' without proof or citation. It is easy to justify: partition each gadget value matrix into at most 2^{2k} rectangles, and combine with the fact that an unambiguous DNF of width w has at most 2^w terms. Please add this one-line argument, since the bound is load-bearing for Corollary 4.1 and Theorem 3.
- [§1.1 / §5] Corollaries 1.1 and 1.2 are derived by citing implications from Balodis et al. [2023]. The partial function H constructed in Section 5 is essentially a direct proof of Corollary 1.1, but the connection is not stated. Please explicitly point out that this H has min{C^0(H,z), C^1(H,z)} ≥ Ω(n^2) and C(H) ≤ O(n), and either prove Corollary 1.2's implication or state the exact reduction used.
- [§1.1, after Corollary 1.1] The sentence 'it is a priori not clear that a separation better than the one in Corollary 1.1 by polylogarithmic factors cannot exist' is confusing, since Corollary 1.1 contains no polylog factors. Rephrase to explain that the cited puzzle reductions lose polylog factors, so the direct upper bound in Appendix A is needed to certify optimality.
- [§5, verifier description] The notation C^0/C^1 is used for 'not-0'/'not-1' certificate complexity in the partial-function section, but in the verifier description the same terms '0-certificate' and '1-certificate' refer to certificates for the actual values H=0 and H=1. These two usages should be clearly distinguished, e.g., by calling the latter 'value certificates', to avoid ambiguity.
Circularity Check
No load-bearing circularity; the main derivation is self-contained.
full rationale
The core derivation is not circular. Theorem 1 is an explicit probabilistic construction of a signed set-pair system, and the pairwise incompatibility, term-width bound, and hitting-number lower bound are all proved directly from that construction rather than from the desired separation. Theorem 2 is an independent spectral proof: the cyclic gadget is defined, the eigenvalues of the W0/W1 matrices are computed, Lemma 4.2 is established by explicit elementary-symmetric-polynomial estimates, and the eigenvalue bound is converted into a rectangle-cover lower bound without assuming the conclusion. Theorem 3 relies on Cheung et al. [2023, Lemma 3.5] as an external conversion from communication separations to Alon-Saks-Seymour graphs; this is not a self-citation and does not assume the target separation, and the exponential margins make the argument robust to constant or log-factor losses. The bound log Par1(f∘g^n) ≤ O(k·UC1(f)) is a standard structural fact, not a restatement of the target result. The self-citations that appear — Pabbaraju [2024] for the multiclass sample-compression framework and Larsen et al. [2026] for Cayley-spectrum context — are supporting references rather than load-bearing inputs: the sample-compression proof uses the new graph from Theorem 3 and does not feed the desired lower bound back into the derivation, and the spectral analysis is carried out in the paper itself rather than imported. No fitted parameter is renamed as a prediction, no uniqueness theorem from the authors' prior work is used to force a choice, and no known result is merely renamed. External dependencies and the limitation stated in Remark 1 are correctness risks, not circularity.
Assumptions & free parameters
free parameters (5)
- k = ⌊n/2⌋ =
⌊n/2⌋
- 1/4 scaling in W0 =
1/4
- n/128 threshold in Lemma 4.2 =
n/128
- γ = 1/5000 =
1/5000
- C (union-bound constant) =
sufficiently large constant
assumptions (12)
- standard math Maclaurin's inequality for elementary symmetric polynomials
- standard math Jensen's inequality
- standard math Variational characterization of the minimum eigenvalue
- standard math Circulant matrices are diagonalized by Fourier vectors over Z_8
- standard math Probabilistic method with union bound and Markov's inequality
- domain assumption Nisan–Szegedy approximate-degree bound for AND
- domain assumption Cheung et al. Lemma 3.5: communication separation to ASS graph
- domain assumption Göös 2015 upper bound C0(f) ≤ UC1(f)^2
- domain assumption log Par1(f∘g^n) ≤ O(k·UC1(f))
- domain assumption Alon et al. 2022 theorems on partial concept classes, VC dimension 1, and disambiguation-to-coloring
- domain assumption Pabbaraju 2024 facts on DS dimension and sample compression of disambiguated classes
- domain assumption Ben-David et al. 2017 desensitization lemma
invented entities (1)
-
Constant-sized cyclic gadget g(x,y)=0 iff y−x ∈ {−1,0,1} mod 8
Cite this review
Pith. "Pith review of Optimal Unambiguous DNFs and Alon-Saks-Seymour." pith.science (2026). https://pith.science/paper/KGDTXKZ2
@misc{pith2026260802533,
author = {Pith},
title = {Pith review of: Optimal Unambiguous DNFs and Alon-Saks-Seymour},
year = {2026},
howpublished = {\url{https://pith.science/paper/KGDTXKZ2}},
note = {Machine review of arXiv:2608.02533}
}
abstract
We construct unambiguous DNFs having width $O(n)$ but $0$-certificate complexity $\Omega(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\"{o}\"{o}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 $\Omega(\sqrt{\log c})$ for multiclass concept classes over $c$ labels.
Reference graph
Works this paper leans on
-
[1]
SIAM Journal on Computing , pages=
Unambiguous DNFs and Alon--Saks--Seymour , author=. SIAM Journal on Computing , pages=. 2023 , publisher=
2023
-
[2]
Computational complexity , volume=
On the degree of Boolean functions as real polynomials , author=. Computational complexity , volume=. 1994 , publisher=
1994
-
[3]
8th Innovations in Theoretical Computer Science Conference (ITCS 2017) , pages=
Low-Sensitivity Functions from Unambiguous Certificates , author=. 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) , pages=. 2017 , organization=
2017
-
[4]
SIAM Journal on Computing , volume=
Rectangles are nonnegative juntas , author=. SIAM Journal on Computing , volume=. 2016 , publisher=
2016
-
[5]
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , pages=
Online Learning and Disambiguations of Partial Concept Classes , author=. 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , pages=. 2023 , organization=
2023
-
[6]
International Conference on Algorithmic Learning Theory , pages=
Multiclass learnability does not imply sample compression , author=. International Conference on Algorithmic Learning Theory , pages=. 2024 , organization=
2024
-
[7]
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages=
A theory of PAC learnability of partial concept classes , author=. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2022 , organization=
2021
-
[8]
independent set , author=
Lower bounds for clique vs. independent set , author=. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages=. 2015 , organization=
2015
Show all 30 references
-
[9]
Combinatorica , volume=
A counterexample to the Alon-Saks-Seymour conjecture and related problems , author=. Combinatorica , volume=. 2012 , publisher=
2012
-
[10]
the electronic journal of combinatorics , pages=
Bipartite coverings and the chromatic number , author=. the electronic journal of combinatorics , pages=
-
[11]
arXiv preprint arXiv:2605.28915 , year=
A note on the Alon-Saks-Seymour problem , author=. arXiv preprint arXiv:2605.28915 , year=
-
[12]
Tech report 91-14, DIMACS, Rutgers University , year=
Recent results on some not-so-recent hypergraph matching and covering problems , author=. Tech report 91-14, DIMACS, Rutgers University , year=
-
[13]
Proceedings of the twentieth annual ACM symposium on Theory of computing , pages=
Expressing combinatorial optimization problems by linear programs , author=. Proceedings of the twentieth annual ACM symposium on Theory of computing , pages=
-
[14]
European Journal of Combinatorics , volume=
Clique versus independent set , author=. European Journal of Combinatorics , volume=. 2014 , publisher=
2014
-
[15]
Discrete Applied Mathematics , volume=
Some improved bounds on communication complexity via new decomposition of cliques , author=. Discrete Applied Mathematics , volume=. 2014 , publisher=
2014
-
[16]
Discrete Applied Mathematics , volume=
Ordered biclique partitions and communication complexity problems , author=. Discrete Applied Mathematics , volume=. 2015 , publisher=
2015
-
[17]
approximate degree and quantum implications of Huang’s sensitivity theorem , author=
Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem , author=. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=
-
[18]
1986 , publisher=
Relating data compression and learnability , author=. 1986 , publisher=
1986
-
[19]
Machine Learning , volume=
On learning sets and functions , author=. Machine Learning , volume=. 1989 , publisher=
1989
-
[20]
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages=
Separations in query complexity using cheat sheets , author=. Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages=
-
[21]
computational complexity , volume=
Lifting dichotomies , author=. computational complexity , volume=. 2025 , publisher=
2025
-
[22]
Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=
Communication lower bounds via critical block sensitivity , author=. Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=
-
[23]
The pattern matrix method , author=. SIAM J. Comput. , volume=
-
[24]
arXiv preprint arXiv:2012.03415 , year=
On query-to-communication lifting for adversary bounds , author=. arXiv preprint arXiv:2012.03415 , year=
2012 arXiv
-
[25]
arXiv preprint arXiv:2208.00029 , year=
Communication complexity of collision , author=. arXiv preprint arXiv:2208.00029 , year=
-
[26]
Luca Trevisan , title =
-
[27]
2018 , publisher=
A brief introduction to spectral graph theory , author=. 2018 , publisher=
2018
-
[28]
Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages=
The Sample Complexity of Replicable Realizable PAC Learning , author=. Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages=
-
[29]
partition number , author=
Deterministic communication vs. partition number , author=. SIAM Journal on Computing , volume=. 2018 , publisher=
2018
-
[30]
Gao and B
Z. Gao and B. D. McKay and R. Naserasr and B. Stevens , title =. Australasian Journal of Combinatorics , volume =. 2016 , pages =
2016
Reviewed August 4, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.