Pith. sign in

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 →

arxiv 2608.02533 v1 pith:KGDTXKZ2 submitted 2026-08-03 cs.CC cs.DMcs.LG

classification cs.CCcs.DMcs.LG MSC 68Q1705C1505C6568Q11
keywords unambiguousDNFscertificatecomplexityAlon–Saks–Seymourconjecturebicliquepartitionchromaticnumbercommunicationapproximatedegreesamplecompression
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

To refute the Alon–Saks–Seymour conjecture, one needs Boolean functions that are easy to write as unambiguous DNFs but hard to certify as zero. This paper constructs exactly such functions: a DNF of width O(n) whose 0-certificate complexity is Ω(n^2), the largest possible quadratic gap. It then proves a lifting theorem with a constant-sized 'cyclic' gadget, converting the DNF separation into a communication problem with log Cover0 = Ω(n^2) and log Partition1 = O(n). Feeding this through a standard graph-conversion lemma yields graphs with biclique partition number 2^{O(n)} and chromatic number 2^{Ω(n^2)}, matching the general upper bounds and thus refuting the conjecture optimally. The same construction also gives an optimal Ω(log^2 n) lower bound for the Clique versus Independent Set problem, a quartic certificate-complexity versus approximate-degree separation, and a √log c sample-compression lower bound for multiclass concept classes.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

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)
  1. [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.
  2. [§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.
  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.
  4. [§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. [§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

0 steps flagged · score 0.0 of 10

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 5 free parameters · 12 assumptions · 1 invented entities

The central proof introduces a new DNF construction with hand-chosen constants (k, 1/4, n/128 thresholds) but no data fitting. The main external dependencies are published theorems from TCS (Nisan-Szegedy, Cheung et al., Göös, Alon et al., Pabbaraju, Ben-David et al.); one of these is stated without citation. No empirical or physical entities are introduced.

free parameters (5)
  • k = ⌊n/2⌋ = ⌊n/2⌋
    Size of positive sets chosen to make the hitting number Ω(n²) while keeping term width O(n); any constant fraction of n would work.
  • 1/4 scaling in W0 = 1/4
    Chosen so all nonzero-frequency eigenvalues c_r of W0 are positive, making division by c_{ξ_u} safe in the spectral computation.
  • n/128 threshold in Lemma 4.2 = n/128
    Hand-picked so the coefficient-ratio induction closes; it only affects the constant in the final exponent.
  • γ = 1/5000 = 1/5000
    Arithmetic outcome of the bad/good block counting; not fitted to data but a hand-derived constant.
  • C (union-bound constant) = sufficiently large constant
    Existential constant in the probabilistic-method argument ensuring term width ≤ Cn.
assumptions (12)
  • standard math Maclaurin's inequality for elementary symmetric polynomials
    Used in Lemma 4.2(a) to bound |P| by (1−(1−θ)^ℓ/n)^k.
  • standard math Jensen's inequality
    Used to lower-bound the sum of good-block contributions by G(0.12)^{L_G/G}.
  • standard math Variational characterization of the minimum eigenvalue
    Used in Lemma 4.1 to relate independent sets to λ_min of the matrix M.
  • standard math Circulant matrices are diagonalized by Fourier vectors over Z_8
    Used in Section 4.4 to compute the eigenvalues of W0, W1 and their Kronecker sums.
  • standard math Probabilistic method with union bound and Markov's inequality
    Used in Section 3 to choose bijections with Σ_j m_{i,j}(S) = O(n).
  • domain assumption Nisan–Szegedy approximate-degree bound for AND
    External theorem used in Section 5 to approximate the AND over O(n) decision-tree evaluations by a degree O(√(n polylog n)) polynomial.
  • domain assumption Cheung et al. Lemma 3.5: communication separation to ASS graph
    External lemma invoked in Appendix B to convert log Cov0 and log Par1 into a graph with bp and χ bounds; not proved in this paper.
  • domain assumption Göös 2015 upper bound C0(f) ≤ UC1(f)^2
    Used to argue that the quadratic separation is optimal and that UC1(f)=Θ(n) for the constructed DNF.
  • domain assumption log Par1(f∘g^n) ≤ O(k·UC1(f))
    Stated as 'known' in Corollary 4.1 and Appendix B without proof or citation; used for the upper bound on biclique partition number.
  • domain assumption Alon et al. 2022 theorems on partial concept classes, VC dimension 1, and disambiguation-to-coloring
    External results used in Section 6 for the sample-compression lower bound.
  • domain assumption Pabbaraju 2024 facts on DS dimension and sample compression of disambiguated classes
    External results used in Section 6; one is co-authored by the present paper's author.
  • domain assumption Ben-David et al. 2017 desensitization lemma
    External lemma used in Appendix C for the sensitivity lower bound.
invented entities (1)
  • Constant-sized cyclic gadget g(x,y)=0 iff y−x ∈ {−1,0,1} mod 8
    purpose: Lifts the constructed unambiguous DNFs to communication problems while preserving a quadratic certificate-complexity separation.
    This is a new mathematical gadget introduced in Section 4; its support is the paper's own spectral proof, not external evidence.

how reviews work

0 comments
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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 3 linked inside Pith

  1. [1]

    SIAM Journal on Computing , pages=

    Unambiguous DNFs and Alon--Saks--Seymour , author=. SIAM Journal on Computing , pages=. 2023 , publisher=

  2. [2]

    Computational complexity , volume=

    On the degree of Boolean functions as real polynomials , author=. Computational complexity , volume=. 1994 , publisher=

  3. [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=

  4. [4]

    SIAM Journal on Computing , volume=

    Rectangles are nonnegative juntas , author=. SIAM Journal on Computing , volume=. 2016 , publisher=

  5. [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=

  6. [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=

  7. [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=

  8. [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=

Show all 30 references
  1. [9]

    Combinatorica , volume=

    A counterexample to the Alon-Saks-Seymour conjecture and related problems , author=. Combinatorica , volume=. 2012 , publisher=

  2. [10]

    the electronic journal of combinatorics , pages=

    Bipartite coverings and the chromatic number , author=. the electronic journal of combinatorics , pages=

  3. [11]

    arXiv preprint arXiv:2605.28915 , year=

    A note on the Alon-Saks-Seymour problem , author=. arXiv preprint arXiv:2605.28915 , year=

  4. [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=

  5. [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=

  6. [14]

    European Journal of Combinatorics , volume=

    Clique versus independent set , author=. European Journal of Combinatorics , volume=. 2014 , publisher=

  7. [15]

    Discrete Applied Mathematics , volume=

    Some improved bounds on communication complexity via new decomposition of cliques , author=. Discrete Applied Mathematics , volume=. 2014 , publisher=

  8. [16]

    Discrete Applied Mathematics , volume=

    Ordered biclique partitions and communication complexity problems , author=. Discrete Applied Mathematics , volume=. 2015 , publisher=

  9. [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=

  10. [18]

    1986 , publisher=

    Relating data compression and learnability , author=. 1986 , publisher=

  11. [19]

    Machine Learning , volume=

    On learning sets and functions , author=. Machine Learning , volume=. 1989 , publisher=

  12. [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=

  13. [21]

    computational complexity , volume=

    Lifting dichotomies , author=. computational complexity , volume=. 2025 , publisher=

  14. [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=

  15. [23]

    The pattern matrix method , author=. SIAM J. Comput. , volume=

  16. [24]

    arXiv preprint arXiv:2012.03415 , year=

    On query-to-communication lifting for adversary bounds , author=. arXiv preprint arXiv:2012.03415 , year=

  17. [25]

    arXiv preprint arXiv:2208.00029 , year=

    Communication complexity of collision , author=. arXiv preprint arXiv:2208.00029 , year=

  18. [26]

    Luca Trevisan , title =

  19. [27]

    2018 , publisher=

    A brief introduction to spectral graph theory , author=. 2018 , publisher=

  20. [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=

  21. [29]

    partition number , author=

    Deterministic communication vs. partition number , author=. SIAM Journal on Computing , volume=. 2018 , publisher=

  22. [30]

    Gao and B

    Z. Gao and B. D. McKay and R. Naserasr and B. Stevens , title =. Australasian Journal of Combinatorics , volume =. 2016 , pages =

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.