Optimal Unambiguous DNFs and Alon-Saks-Seymour

Optimal Unambiguous DNFs and Alon-Saks-Seymour Chirag Pabbaraju∗ August 4, 2026

Abstract

arXiv:2608.02533v1 [cs.CC] 3 Aug 2026

We construct unambiguous DNFs having width O(n) but 0-certificate complexity Ω(n2 ). By utilizing the special structure of these DNFs, we prove a lifting theorem with a constantsized 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 Ω( log c) for multiclass concept classes over c labels.

∗

Stanford University. Email: cpabbara@cs.stanford.edu.

1

1

Introduction

We begin by describing three puzzles studied in the work of Balodis, Ben-David, Göös, Jain, and Kothari [2023] to set up the context. Unambiguous DNFs. A DNF (Disjunctive Normal Form) f = C1 ∨ · · · ∨ Cm is a Boolean function that is the disjunction of terms Ci , where each Ci = xi1 ∧ · · · ∧ ¬xiℓ is a conjunction of literals (i.e., a variable or its negation). The DNF has term-width ℓ if every Ci is a conjunction on at most ℓ literals. The DNF is unambiguous if whenever f = 1, exactly one term evaluates to 1. For any Boolean function on n variables, a partial assignment ρ ∈ {0, 1, ∗}n is a 0-certificate for x ∈ f −1 (0) if ρ is consistent with x (i.e., ρi = xi wherever ρi ̸= ∗), and for any x′ ∈ {0, 1}n consistent with ρ, it holds that f (x′ ) = 0. We define the domain of ρ to be dom(ρ) = {i : ρi ̸= ∗}, and the size of the certificate ρ to be |ρ| = |dom(ρ)|. The 0-certificate complexity of f at x, denoted C0 (f, x), is the size of the smallest 0-certificate for x. The 0-certificate complexity of f , denoted C0 (f ), is defined to be maxx∈{0,1}n C0 (f, x). The definitions for 1-certificates and 1-certificate complexity C1 (f ) are analogous. Finally, the certificate complexity of f , denoted C(f ), is defined as C(f ) = max(C0 (f ), C1 (f )). The unambiguous 1-certificate complexity of a function f , denoted UC1 (f ), is the smallest ℓ such that f is equivalent to an unambiguous DNF having term-width ℓ. It was shown by Göös [2015] that for any function f , it holds that C0 (f ) ≤ UC1 (f )2 . The first puzzle in Balodis et al. [2023] asks how large the separation can be in the opposite direction: Puzzle I.

For α > 1, does there exist a family of Boolean functions f with C0 (f ) ≥ Ω(UC1 (f )α )?

Motivations for studying this puzzle arise from its implications to the Alon-Saks-Seymour conjecture [Kahn, 1991] and the classical Clique versus Independent Set problem [Yannakakis, 1988] in communication complexity (see Section 1.2 below). In light of the upper bound on C0 (f ) above, the best possible exponent α for Puzzle I can be α = 2. Indeed, the exponent was confirmed to be 2 — up to polylogarithmic factors — by Balodis et al. [2023], who constructed a family of functions 2 e f satisfying C0 (f ) ≥ Ω(UC 1 (f ) ). More precisely, the separation shown in their work was (see Theorem 3.2 in Cheung, Hatami, Hatami, and Hosseini [2023]):   UC1 (f )2 C0 (f ) ≥ Ω . (1) log6 (n) Partial Functions. The notion of certificates described above naturally extends to partial functions f , where f (x) may be undefined at some values of x (i.e., f (x) = ∗). Namely, a (Boolean) partial function is a map f : {0, 1}n → {0, 1, ∗}. In addition to the 0 and 1 certificate complexities of f defined above, we can also define the 0 (read “not-0”) and 1 (read “not-1”) certificate complexities of f . Namely, a partial input ρ ∈ {0, 1, ∗}n is a 0-certificate for f at x, if ρ is consistent with x, and for every x′ consistent with ρ, it holds that f (x′ ) ̸= 0. The 0-certificate complexity of f at x, denoted C0 (f, x), is the size of the smallest 0-certificate for x. The 0-certificate complexity of f , denoted C0 (f ), is defined as maxx∈{0,1}n : f (x)̸=0 C0 (f, x). We similarly define the 1-certificate complexity C1 (f ). The second puzzle studied in Balodis et al. [2023] pertains to the separation between C0 (f ), C1 (f ) and C(f ):

2

Puzzle II. For α > 1, does there exist a family of partial functions f together with an x ∈ f −1 (∗) such that both C0 (f, x) and C1 (f, x) are at least Ω(C(f )α )? Balodis et al. [2023] constructed a family of partial functions f , for which the separation above is witnessed up to polylogarithmic factors with α = 2. Concretely, they showed   C(f )2 . (2) min {C0 (f, x), C1 (f, x)} ≥ Ω log2 (n) Intersecting Hypergraphs. The third and final puzzle from Balodis et al. [2023] is purely graph-theoretic. First, the definitions again: a hypergraph G = (V, E) is said to be intersecting if e ∩ e′ ̸= ∅ for every e, e′ ∈ E. The rank r(G) of a hypergraph is the size of its largest edge. A subset U ⊆ V is said to be c-monochromatic with respect to a coloring function c : V → {0, 1} if c(u) is the same for every u ∈ U . Finally, a set S ⊆ V is a hitting set for E if S ∩ e ̸= ∅ for every e ∈ E. Puzzle III. For α > 1, does there exist a family of intersecting hypergraphs G = (V, E) together with a coloring c : V → {0, 1} such that every c-monochromatic hitting set has size at least Ω(r(G)α )? For this problem, Balodis et al. [2023] constructed a family of intersecting hypergraphs G and coloring functions c such that every c-monochromatic hitting set has size at least   r(G)2 Ω . (3) log2 (n) In summary, Balodis et al. [2023] give solutions to each of Puzzles I, II and III with exponent α = 2, up to polylogarithmic factors. In fact, Balodis et al. [2023] explicitly only give a solution for Puzzle II, and thereafter derive implications showing that all the three puzzles are equivalent up to polylogarithmic factors. Therefore, since the exponent α = 2 is optimal for Puzzle I, it is also the optimal exponent for Puzzles II and III, at least up to polylogarithmic factors. To our knowledge, the bounds in (1), (2) and (3) are the best-known bounds for the three puzzles.

1.1

Optimal Solutions to Puzzles I, II and III

Our first contribution is to give optimal solutions to all the three puzzles above which are completely devoid of any polylogarithmic factors. Theorem 1 (Unambiguous DNFs). For any n ≥ 2, there exists an unambiguous DNF f : 2 {0, 1}n → {0, 1} satisfying C0 (f ) = Ω(n2 ).

UC1 (f ) = O(n),

By reparameterizing, we obtain that C0 (f ) = Ω(UC1 (f )2 ), which improves over the bound in (1) by a log6 (n) factor, and gives an optimal resolution of Puzzle I up to constant factors, given that the upper bound C0 (f ) ≤ UC1 (f )2 of Göös [2015] holds for every f . Using the implication Puzzle I → Puzzle II given in [Balodis et al., 2023, Section 5.2], together with Theorem 1 above, we get: 2

Corollary 1.1 (Partial Functions). For any n ≥ 2, there exists a partial function f : {0, 1}2n → {0, 1, ∗}, such that there exists an input x ∈ f −1 (∗) satisfying min {C0 (f, x), C1 (f, x)} ≥ Ω(n2 ), 3

C(f ) ≤ O(n).

Reparameterizing, we obtain that min {C0 (f, x), C1 (f, x)} ≥ Ω(C(f )2 ), which improves over the bound in (2) by a log2 (n) factor. While a quadratic separation here is optimal due to the equivalence of the three puzzles, the reductions between the puzzles obtained in Balodis et al. [2023] lose polylogarithmic factors; thus, it is a priori not clear that a separation better than the one in Corollary 1.1 by polylogarithmic factors cannot exist. Nevertheless, in Section A, we show that a direct upper bound min {C0 (f, x), C1 (f, x)} ≤ C(f )2 always holds. Thus, our result above is an optimal resolution of Puzzle II up to constant factors. Finally, using the implication Puzzle II → Puzzle III given in [Balodis et al., 2023, Section 5.3], together with Corollary 1.1 above, we also have the following: Corollary 1.2 (Intersecting Hypergraphs). For any n ≥ 2, there exists an intersecting hypergraph G = (V, E) with |V | = 4n2 + 2, r(G) = O(n) and a coloring c : V → {0, 1} such that every c-monochromatic hitting set has size at least Ω(n2 ). By converting parameters, we obtain a family of intersecting hypergraphs G and colorings c for which every c-monochromatic hitting set has size at least Ω(r(G)2 ), improving the bound in (3) by a log2 (n) factor. Again, we show that this separation is optimal up to constant factors, by giving a direct matching upper bound in Section A.

1.2

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

As mentioned above, Puzzle I is motivated (among other reasons) by its application to the AlonSaks-Seymour conjecture and the Clique versus Independent Set problem. The Alon-Saks-Seymour conjecture, first referenced in Kahn [1991], is concerned with two combinatorial quantities of a graph G: the chromatic number χ(G) and biclique partition number bp(G). The chromatic number of G is the smallest number of colors that can be assigned to the vertices in G, such that no two adjacent vertices are assigned the same color. The biclique partition number of G is the smallest number of bicliques that the edge set of G can be partitioned into. Alon, Saks and Seymour conjectured that these quantities are related as χ(G) ≤ bp(G) + 1. While Gao, McKay, Naserasr, and Stevens [2016] confirmed this conjecture for all graphs having bp(G) ≤ 9, in a celebrated result, Huang and Sudakov [2012] disproved it by constructing a family of graphs satisfying χ(G) ≥ Ω(bp(G)6/5 ). This separation has since been improved in a series of works, namely: Göös [2015], who showed χ(G) ≥ exp(Ω(log1.12 (bp(G)))), Ben-David, Hatami, and Tal [2017], who showed χ(G) ≥ exp(Ω(log1.22 (bp(G)))), and finally Balodis et al. [2023], who showed 2 e χ(G) ≥ exp(Ω(log (bp(G)))). In particular, the precise bound shown by Balodis et al. [2023] (which is made explicit in Cheung et al. [2023, Theorem 1.11]1 , and to our knowledge, is the best-known separation so far) was    log2 (bp(G)) χ(G) ≥ exp Ω . (4) (log log(bp(G)))7 Importantly, the bound in (4) is optimal up to the doubly logarithmic factors, since on the upper bound side, it is known that χ(G) ≤ exp(O(log2 (bp(G)))) for all graphs [Mubayi and Vishwanathan, 2009, Fox, 2026]. The way that Balodis et al. [2023] obtain the near-optimal separation in (4) is by applying a lifting theorem of Göös, Lovett, Meka, Watson, and Zuckerman [2016] to the family of functions they 1

At first glance, Theorem 1.11 in Cheung et al. [2023] appears to imply the weaker separation χ(G) ≥   2 (bp(G)) exp Ω (logloglog(bp(G))) . However, combining their Theorems 3.2 and 3.3 gives an additional Ω(log n) factor in 8 log Cov0 beyond the bound stated in their Corollary 3.4, yielding the bound shown in (4).

4

2 e construct that witnesses C0 (f ) ≥ Ω(UC 1 (f ) ). The lifting operation converts a Boolean function into a two-party communication problem h by composing through a gadget g. The classical result of Göös et al. [2016] constructs a gadget of size k = Θ(log n) that translates a lower bound on the 0certificate complexity C0 (f ) of any Boolean function f into a lower bound on the 0-monochromatic rectangle covering number Cov0 (h) of the lifted communication problem h (see Section 4 for a definition of Cov0 (h)). Directly applying this all-purpose lifting theorem to our optimal unambiguous 6 DNFs constructed in Theorem   12 improves  the bound in (4) by a (log log(bp(G))) factor in the log (bp(G)) exponent to χ(G) ≥ exp Ω log log(bp(G)) . However, this still leaves the gap of a log log(bp(G)) factor to the upper bound. While the lifting theorem of Göös et al. [2016] is extremely powerful, in that it applies to every Boolean function, the fact that it uses a gadget of size k = Θ(log n) is precisely what leads to the superfluous doubly logarithmic factor in the final separation between chromatic number and biclique partition number. One way to shave this last remaining factor is to derive a lifting theorem that uses only a constant-sized gadget, while retaining the guarantee of the lifting theorem of Göös et al. [2016] — not necessarily for all Boolean functions, but even just for the unambiguous DNFs from Theorem 1. Such constant-gadget lifting theorems are notoriously hard to come by; see for example the recent work by Alekseev et al. [2025], which provides a detailed examination of lifting theorems. Nevertheless, by exploiting the special structure of our unambiguous DNFs, we are able to derive precisely the required constant-gadget lifting theorem.

Theorem 2 (Constant-gadget Lifting). There exists a gadget function g : {0, 1}3 ×{0, 1}3 → {0, 1}, such that for all large enough n, for the DNF f constructed in Theorem 1, denoting by h the lifted 2 2 2 communication problem f ◦ g n : {0, 1}3n × {0, 1}3n → {0, 1}, it holds that log Cov0 (h) = Ω(n2 ). The gadget g that we use in the lifting theorem above is a simple cyclic gadget g(x, y) = 0 ⇐⇒ y − x ∈ {−1, 0, 1}

mod 8,

where we identify x, y ∈ {0, 1}3 by elements in Z8 in the natural way. We defer a detailed discussion of the gadget to the overview of results (Section 2). Applying this lifting theorem to our unambiguous DNFs, and following the rest of the reduction given in Cheung et al. [2023], we obtain an optimal refutation of the Alon-Saks-Seymour conjecture. Theorem 3 (Optimal Refutation of Alon-Saks-Seymour). For infinitely many n, there exists a 2 graph G having 2Θ(n ) vertices that admits a biclique partition of size 2O(n) but has chromatic 2 number 2Ω(n ) . Consequently, there exists an infinite family of graphs G satisfying

χ(G) ≥ exp Ω log2 (bp(G)) . (5) This matches the upper bounds of Mubayi and Vishwanathan [2009], Fox [2026] up to constants in the exponent. Notably, the theorem above also uniformly improves all the parameters from Theorem 1.11 in Cheung et al. [2023]. In particular, the form of their result is similar to Theorem 3 above, but in 3 4 addition to a weaker separation, the number of vertices in their graph is 2Θ(n log n) , while our result 2 only requires 2Θ(n ) vertices. Observe that any graph having chromatic number χ has at least χ vertices. This means that the size of our graph in Theorem 3 which witnesses the optimal refutation of the Alon-Saks-Seymour conjecture is itself optimal up to constant factors in the exponent. We 5

find it remarkable that an optimal separation between the chromatic number and biclique partition number can be witnessed by graphs that effectively have the smallest number of vertices required to witness the separation! We next describe the Clique versus Independent Set problem [Yannakakis, 1988, Bousquet et al., 2014]. This is a two-party communication problem, wherein there is an underlying graph G = (V, E) on n vertices, Alice is given a clique x ⊆ V , Bob gets an independent set y ⊆ V , and their goal is output CISG (x, y) := 1[x ∩ y ̸= ∅]. Yannakakis [1988] showed that the co-nondeterministic communication complexity of this problem is O(log2 (n)). With respect to lower bounds, a lower bound of Ω(log(n)) on the co-nondeterministic communication complexity was obtained in the works of Huang and Sudakov [2012], Amano [2014], Shigeta and Amano [2015]. This was later improved to Ω(log1.12 (n)) in Göös [2015], Ω(log1.22 (n)) 2 e in Ben-David et al. [2017], and finally to a near-optimal Ω(log (n)) in Balodis et al. [2023]. In fact, the Alon-Saks-Seymour problem and the Clique versus  Independent Set problem are deeply related (log(bp(G)))a [Bousquet et al., 2014]: a separation χ(G) ≥ exp Ω (log log(bp(G)))b implies a co-nondeterministic   a (log(bp(G))) for some CISG on at most bp(G) vertices. So, keeping (4) in mind, lower bound Ω (log log(bp(G)))b   2 (n) the precise form of the lower bound of Balodis et al. [2023] is Ω (logloglog(n)) 7 . As a direct implication of (5), we obtain an optimal Ω(log2 (n)) lower bound for the Clique versus Independent Set problem, matching the upper bound of Yannakakis [1988] to constant factors. Corollary 1.3 (Clique versus Independent Set). There exists a family of CISG on n vertices for
2 which the co-nondeterministic communication complexity of CISG is at least Ω log (n) . Finally, we note that our constant-gadget lifting theorem also helps shave all the log factors from the quadratic lower bound of Göös et al. [2018] for the log-rank conjecture; see Corollary 4.2.

1.3

Application: Query Complexity

We now describe the implications of our optimal unambiguous DNF separation from Theorem 1 to query complexity. In particular, we derive improved separations between the certificate complexity of a Boolean function and other standard complexity measures. We start with the most significant result: an optimal separation between the certificate complexg (f ) of a Boolean ity and approximate degree of Boolean functions. The ε-approximate degree deg ε function on n variables is the smallest degree of an n-variate polynomial p : Rn → R such that g ) := deg g (f ). It is known that C(f ) ≤ O( g )4 ) e deg(f p(x) ∈ f (x) ± ε for all x ∈ {0, 1}n . Define deg(f 1/3 for every f (see Table 1 in Aaronson et al. [2021]), whereas Balodis et al. [2023] showed that there g )3 ). We close the gap between the upper e deg(f exists a family of functions f for which C(f ) ≥ Ω( and lower bounds (up to polylogarithmic factors). Theorem 4 (Certificate Complexity vs. Approximate Degree). There exists a family of Boolean g )4 ). e deg(f functions f with C(f ) ≥ Ω( We next state the more direct corollaries of our Theorem 1. Similar to approximate degree, define the exact degree deg(f ) of a Boolean function f to be the smallest degree of a polynomial e that equals f at all Boolean inputs. It is known that C(f ) ≤ O(deg(f )3 ) for all f [Aaronson et al., 2021]. the other hand, it turns out that deg(f ) ≤ UC1 (f ), and thus a lower bound of  On2  deg(f ) C(f ) ≥ Ω log6 (n) follows directly as a result of the separation for unambiguous DNFs (1) shown by Balodis et al. [2023]. Since our separation for unambiguous DNFs in Theorem 1 is log-free, we obtain: 6

Corollary 1.4 (Certificate Complexity vs. Degree). There exists a family of Boolean functions f with C(f ) ≥ Ω(deg(f )2 ). Our last corollary has to do with the sensitivity of a function. The sensitivity of x ∈ {0, 1}n with respect to an n-bit Boolean function f is the number of bits in x, which when flipped in isolation, flip the value of f (x). The sensitivity of f , denoted s(f ), is the maximum sensitivity of any x with respect to f . The result of Balodis et al. [2023] shows the existence of a family of s(f )3 e functions f for which C(f ) ≥ Ω log , whereas there is a global upper bound C(f ) ≤ O(s(f )5 ) 6 (n) [Aaronson et al., 2021]. Our result shaves the polylogarithmic factors in the lower bound of Balodis et al. [2023] (proof in Section C). Corollary 1.5 (Certificate Complexity vs. Sensitivity). There exists a family of Boolean functions f with C(f ) ≥ Ω(s(f )3 ).

1.4

Application: Multiclass Sample Compression

Our final application is to the problem of sample compression in learning theory [Littlestone and Warmuth, 1986]. Consider a class C of functions/concepts mapping a domain to a discrete label space of c labels. The sample compression problem asks for a pair of maps (κ, ρ), where κ is the compressor and ρ is the reconstructor. The compressor compresses a labeled sample S to a subsample S ′ , and the reconstructor reconstructs labels on S \ S ′ from the compressed sample S ′ . Relevant here is also a notion of complexity of the class C known as the Natarajan dimension [Natarajan, 1989], which governs the learnability of C. It is known that for any concept class having Natarajan dimension d, there exists a sample compression scheme, such that for any sample labeled by some concept in the class, it is possible to reconstruct labels on the entire sample from a compressed sample of size cO(d) ; moreover, the size of the compressed sample provably needs to be at least Ω(d) (e.g., see Pabbaraju [2024]). Note that if we keep the Natarajan dimension fixed, the lower bound on the sample compression size is constant, and does not grow with the number of labels. Pabbaraju [2024] asked as an open question if the lower bound on sample compression must grow with c, especially given that the upper bound in this regime is polynomial in c. Using the optimal small-size refutation of the AlonSaks-Seymour conjecture given by Theorem 3, we provide a partial resolution to this open question, by constructing a family of classes for which the size of any sample compression scheme must grow at least polylogarithmically with the number of labels. Theorem 5 (Sample Compression Lower Bound for Multiclass Concept Classes). 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 . Lastly, we remark that Theorem 3 also shaves the lower-order terms from the results of Alon et al. [2022] and Pabbaraju [2024] that depend on the Alon-Saks-Seymour refutation (i.e., the 1 − o(1) exponent in Theorems 7 and 11 in [Alon et al., 2022] and Theorem 1 in Pabbaraju [2024]).

2

Overview of Techniques

In this section, we sketch the main technical ideas used in the construction of unambiguous DNFs in Theorem 1, the constant-gadget lifting in Theorem 2, the quartic separation between certificate complexity and approximate degree in Theorem 4, and the sample compression lower bound in Theorem 5; the detailed proofs of these results are given in Sections 3 to 6. 7

Unambiguous DNFs. Our unambiguous DNFs arise from a simple yet carefully constructed set-pair system {(PT , NT )}T over a universe U , where each set-pair (PT , NT ) comprises a positive set PT ⊆ U and a negative set NT ⊆ U . Each pair will correspond to a term CT in the DNF of the form ^ ^ CT = xu ∧ ¬xv , (6) u∈PT

v∈NT

W

and the final DNF will be f = T CT . Recall that unambiguity requires that only one term be satisfied by any x for which f (x) = 1. The crucial advantage offered by formulating the DNF as a set-pair system is that we can formulate a sufficient condition for unambiguity in terms of a pairwise incompatibility constraint on the set-pair system. Namely, if we ensure that for every distinct pair (PT , NT ) and (PT ′ , NT ′ ), it holds that either PT ∩ NT ′ ̸= ∅ or PT ′ ∩ NT ̸= ∅, then whenever a term (PT , NT ) is satisfied, it is ensured that every other term (PT ′ , NT ′ ) is unsatisfied. So, we will aim to build a set-pair system that has such pairwise incompatibility; in addition, we want to ensure a quadratic separation between the 0-certificate complexity of f and the termwidth of f . We first consider the 0-certificate complexity. Note that by the form (6) of a term in our DNF, f (0|U | ) = 0, since the positive part of every term is falsified. Let us study the 0certificate complexity of 0|U | . For any certificate ρ consistent with 0|U | , observe that if dom(ρ) does not intersect every PT in our set-pair system, then we can take a PT that is disjoint with dom(ρ), and set all the variables in it to 1; this extends ρ to an input x that is consistent with ρ but f (x) = 1, which invalidates ρ from being a 0-certificate for 0|U | . Thus, any 0-certificate ρ for 0|U | must satisfy that dom(ρ) is a hitting set for the family of all positive sets, meaning that the 0-certificate complexity of f is at least the hitting number of the family of positive sets. A simple choice of the positive sets which ensures a large hitting number is as follows: consider the universe U = B1 ⊔ B2 ⊔ · · · ⊔ Bn to be the disjoint union of buckets Bi , where each |Bi | = n, and hence |U | = n2 . We include every subset of every Bi that has size n/2 as a positive set. That is, for every T = (i, S), where i ∈ [n] and S ⊆ Bi , |S| = n/2, we include a positive set PT = Pi,S = S. Then, any hitting set must include at least n/2 elements of every Bi , giving us a hitting number of Ω(n2 ). Our remaining goal is to suitably choose the negative sets NT , so that the term-width of every term, namely |PT | + |NT | is at most O(n), while also satisfying the pairwise incompatibility condition to ensure unambiguity. Our negative sets NT = Ni,S will have two components: the set Bi \Pi,S (i.e., the complement of the positive term within the bucket Bi ), together with a cross-bucket term Ai,j (S) for every j ̸= i. The first component ensures incompatibility with all the other terms that arise from the same bucket, whereas the second component ensures incompatibility with terms P arising from different buckets. It remains to choose the sets Ai,j (S) appropriately such that j̸=i |Ai,j (S)| = O(n) for every i and S. We use the probabilistic method for constructing these sets. For every (unordered) pair {i, j}, we randomly hash the buckets Bi and Bj independently to [n]. We include in Ni,S precisely those terms in bucket Bj that get hashed to a value which is at most the smallest value that an element from S gets hashed to. It is not too hard to verify that this guarantees the pairwise incompatibility property. Additionally, since |S| = n/2, the distribution of the smallest value that an element from S gets hashed to has an exponentially small tail. We can thus P union bound an exponentially small failure probability over all choices of i, S, and conclude that j̸=i |Ai,j (S)| = O(n) holds for every i, S with positive probability. This gives the desired set-pair system, and hence an unambiguous DNF that has a quadratic separation between term-width and 0-certificate complexity.

8

Constant-gadget Lifting. We will now sketch how, by exploiting the special structure of the unambiguous DNF constructed above, we are able to lift it to a communication problem with a constant-sized gadget. For the DNF f : {0, 1}|U | → {0, 1} above, where |U | = n2 , our goal is to construct a gadget g : {0, 1}k × {0, 1}k → {0, 1} where k = O(1), such that the communication problem h = f ◦ g |U | : {0, 1}k|U | × {0, 1}k|U | → {0, 1} satisfies log Cov0 (h) ≥ Ω(|U |). Here, Cov0 (h) denotes the 0-monochromatic covering number of h, i.e., the minimum number of 0-monochromatic rectangles required to cover all the 0-entries in the communication matrix of h,2 and f ◦ g |U | ((x1 , . . . , x|U | ), (y1 , . . . , y|U | )) = f (g(x1 , y1 ), . . . , g(x|U | , y|U | )), where each xi , yi ∈ {0, 1}k . We first recall that our DNF satisfies f (0|U | ) = 0. So, if the gadget g is such that g(x, x) = 0 for all x, then we get that the entire diagonal of the communication matrix of h is 0. This is useful, since any set of 0-monochromatic rectangles that cover all the 0-entries in the matrix must necessarily cover all the diagonal entries. Our objective then reduces to showing that any individual rectangle may cover only a small number of the diagonal entries. Towards this, suppose we could construct a non-negative matrix M N ×N , where N := 2k|U | , which has the property that M (x, y) > 0 =⇒ h(x, y) = 1. (The communication matrix of h itself has this property, but we later end up requiring additional properties of the matrix M that are not directly satisfied by the communication matrix itself.) Suppose also that every row in M has the same sum d > 0 — we might expect such a property to naturally hold if we choose a suitably symmetric gadget. Now let us interpret M as the adjacency matrix of an undirected graph GM over N vertices, where x and y are connected by an edge iff M (x, y) > 0. Fix any 0-cover F of h by 0-monochromatic rectangles, and let R be a rectangle in this cover. Now consider the set SR = {x P: (x, x) ∈ R} of diagonal entries in R — from the preceding paragraph, it must hold that N ≤ R |SR | ≤ |F | maxR |SR |. But observe that by virtue of R being a 0-monochromatic rectangle, for any x ̸= y ∈ SR , it holds that h(x, y) = 0, meaning that x and y are not connected by an edge in the graph GM . Thus, the set SR is an independent set in GM . We then aim to show that no independent set in GM is too large. For any independent set S in GM , let 1S be its indicator vector. Since the diagonal of M is 0 and S is an independent set, it holds that 1TS M 1S = 0. Consider decomposing 1S along the along-ones vector 1 and orthogonal to it as 1S = δ1 + z, where δ = |S|/N . A routine calculation shows that ∥z∥22 = δN (1 − δ),

z T M z = −δ 2 N d.

But by the variational form of the minimum eigenvalue λmin of M , we also have that z T M z ≥ λmin ∥z∥22 = λmin δN (1 − δ). Thus, if we could show that the minimum eigenvalue λmin of M is at least −dε for ε > 0, we would obtain an upper bound of εN on the size of any independent set S. Combining with the calculation from the previous paragraph, this would lower bound |F| as N ≤ |F|εN =⇒ |F | ≥ 1/ε. 2

In particular, the value of ε we will aim for is ε = 2−Ω(n ) , which will give us that log |F| = Ω(n2 ) — our desired lower bound. The communication matrix of h : X ×Y → {0, 1} is a Boolean matrix A|X |×|Y| with Ax,y = h(x, y). For b ∈ {0, 1}, a b-monochromatic rectangle in A is a set R = X × Y , where X ⊆ X , Y ⊆ Y such that h(x, y) = b for all (x, y) ∈ R. 2

9

Summarily, our entire task has been distilled into a concrete objective: construct a constantsized gadget g and associated matrix M which satisfies that M (x, y) > 0 =⇒ h(x, y) = 1; furthermore, M should be non-negative, symmetric, have a common row-sum d > 0, and also have the desired spectral property that its minimum eigenvalue λmin is not too negative — namely 2 at least −d · 2−Ω(n ) . To this end, we first tried several natural gadgets like the AND, XOR and AND/OR gadgets, but to no avail. Nevertheless, it turns out that a simple cyclic gadget g : {0, 1}3 × {0, 1}3 → {0, 1} over 3 bits works. Concretely, by identifying every x ∈ {0, 1}3 as the binary representation of an element in Z8 = {0, 1, . . . , 7} in the natural way, define ( 0 if y − x ∈ {−1, 0, 1} mod 8, g(x, y) = (7) 1 otherwise. That is, g outputs 0 only when y is either equal to x, or equal to one of the two neighbors of x around the cycle 0, 1, . . . , 7, 0. Note that the gadget is symmetric, namely g(x, y) = g(y, x). While there has been precedent for using such constant-sized modular gadgets in the literature — e.g., the versatile gadget g(x, y) = 1 ⇐⇒ x + y ∈ {2, 3} mod 4 [Sherstov, 2011, Göös and Pitassi, 2014, Anshu et al., 2020, Göös and Jain, 2022] — to the best of our knowledge, the precise cyclic gadget above has not been used specifically in the context of query-to-communication lifting. In particular, the matrix of the versatile gadget has an equal number of 0’s and 1’s (namely 2 each) in every row, whereas we do end up crucially using that the cyclic gadget has an unequal number (3 and 5) in our spectral analysis. Another reason to use the cyclic gadget is that the precise spectrum of the associated Cayley graph is well-understood [Trevisan, 2011, Nica, 2018, Larsen et al., 2026]. In slightly more detail, we obtain the desired matrix M as follows: we first define two simple 8 × 8 matrices W0 and W1 that satisfy Wb (x, y) > 0 ⇐⇒ g(x, y) = b for the cyclic gadget g. Then, for any i ∈ [n] and any S ⊆ Bi , |S| = n/2, with 1S being the indicator vector for the set S, consider defining the matrix Mi,S as the Kronecker product O Y Mi,S = W1S,u where Mi,S (x, y) = W1S,u (xu , yu ). (8) u∈U

u∈U

Here, 1S,u = 1[u ∈ S], and every xu , yu ∈ Z8 . That is, Mi,S has a “component” W1 at the index u in the Kronecker product if u ∈ S, and W0 otherwise. Finally, define M=

n X X

Mi,S .

i=1 S∈( Bi ) n/2

It can be readily verified that M is non-negative, symmetric and has a common row-sum d > 0. Furthermore, observe that if M (x, y) > 0, then it must be the case that Mi,S (x, y) > 0 for at least some (i, S), meaning that every term in the product in (8) is positive. By definition, this means that (g(xu , yu )u∈U ) = 1S , which means h((g(xu , yu ))u∈U ) = f (1S ) = 1, as desired. 2 All that remains is to argue that the minimum eigenvalue of M is at least −d · 2−Ω(n ) . As mentioned above, we can compute precise expressions for all the eigenvalues of the matrix M since it is derived from the cyclic gadget. Concretely, every eigenvalue can be written (up to a multiplicative factor) as an elementary symmetric polynomial of degree n/2. Bounding these symmetric polynomials ends up being the most technically involved part of the paper. To avoid overwhelming the reader further in this overview, we provide intuition for this analysis in the sections containing it, rather than delving into it here. 10

Quartic Separation between Certificate Complexity and Approximate Degree. The proof of Theorem 4 is based on the cheat-sheet framework of Aaronson et al. [2016], which was also used by Balodis et al. [2023] to establish their cubic separation between certificate complexity and approximate degree. The first ingredient in the construction is a partial function H that has a large 0 and 1 certificate complexity of Ω(n2 ). Such a function can be constructed by applying the Puzzle I → Puzzle II transformation from Balodis et al. [2023] to the unambiguous DNFs that we construct in Theorem 1. While the constructed partial function H is hard to certify to be ‘not-0’ and ‘not-1’, we show that it is nevertheless possible to certify that a given input z satisfies H(z) = 0 or H(z) = 1, by performing only a few “local checks” over a carefully encoded certificate description. That is, we specify both the encoding of a certificate description and the action of a verifier on this description. We argue that the verification process is sound and complete — any input that is verified to be a 0-input (1input) is actually a 0-input (1-input). Conversely, for every 0-input (1-input), there is a certificate description that gets verified by the verifier. Crucially, the verification process can be expressed as an AND of only O(n)-many (deterministic) decision tree evaluations of depth polylog(n). Since every decision tree can be exactly expressed by a polynomial having degree on the order of the depth of the decision tree, and the AND function on O(n) inputs can also be approximated by e √n) [Nisan and Szegedy, 1994], the entire verification process can be a polynomial of degree O( e √n). approximated by a polynomial of degree O( It is essential that the AND above is only over O(n) many local checks (so that it may be e √n) degree polynomial) for the final quartic separation that we desire, and approximated by an O( the special structure of our unambiguous DNFs turns out to be crucial for this property. To belabor the point, one could also have constructed the partial function above from the unambiguous DNFs derived in Balodis et al. [2023] instead. This partial function would also have large 0 and 1 certificate complexity; however, for this partial function, it is not clear how to encode a certificate description for 0/1 inputs that may be verified (soundly and completely) by performing only O(n)-many local checks. This is also precisely why Balodis et al. [2023] use a separate partial function that is based on the Hex board game for their separation between certificate complexity and approximate degree; while this Hex-based partial function does indeed allow for a certificate description that can be verified with O(n) local checks, its 0 and 1-certificate complexity is smaller (only Ω(n1.5 )), which eventually leads to their weaker cubic separation. Given that our unambiguous DNFs do have enough structure to construct the desired partial function, we next totalize this partial function using the aforementioned cheat-sheet framework. Namely, we consider r = Θ(log n) many inputs z (1) , . . . , z (r) to H. For each bit-string c ∈ {0, 1}r , which corresponds to a “cheat-sheet cell”, we consider r-many candidate certificate descriptions for the r inputs. The total function evaluates to 1 iff there is some bit-string c, such that for each i ∈ [r], the ith certificate description validly certifies input z (i) to be a ci -input. Using the fact that it is hard to certify the partial function H evaluating to 0 as well as 1, together with the completeness of the verifier, we can show that the total function constructed above has C(f ) ≥ Ω(n2 ). Thereafter, using the fact that each of the r verifications above may e √n) degree polynomial, we can show that the total function also has be approximated by an O( e √n). Combining these yields the claimed quartic separation. approximate degree at most O( Sample Compression. Our proof of Theorem 5 is largely inspired by the sample compression lower bound for multiclass concept classes shown in Pabbaraju [2024], which translates an AlonSaks-Seymour refutation into a multiclass concept class that is hard to compress. The strategy is as follows: first, a partial concept class (whose range is {0, 1, ∗}) having VC dimension 1 is constructed

11

from a graph witnessing a separation between chromatic number and biclique partition number. The class has a partial concept corresponding to every vertex in the graph. Then, a total multiclass concept class that disambiguates the partial concept class is constructed by having a total concept for every partial concept, where the total concept fills in the ∗ values with a unique label that is distinct from all other total concepts. Because the labels used for disambiguation are unique, the Natarajan dimension of this total concept class is equal to the VC dimension of the partial class. Since there is one disambiguating total concept that uses a unique label per partial concept in the class, and the number of partial concepts is equal to the number of vertices in the graph, the number of labels in the disambiguating class is on the order of the number of vertices in the graph. We thus apply this strategy to our small-sized graph from Theorem 3. Finally, we use the observation that a sample compression scheme for the total class implies a coloring of the vertices of the graph, where the number of colors scales with the size of the sample compression; because the chromatic number of the graph is lower-bounded in terms of the number of labels, we infer the desired lower bound. We note that applying the construction above to the graph given by Theorem 1.11 in Cheung e et al. [2023] would already have given a weaker sample compression lower bound of Ω((log c)1/4 ); our improvement on the size of the graph in Theorem 3 is crucial for the stronger lower bound of Theorem 5.

3

Optimal Unambiguous DNF Separation

In this section, we restate and give a complete proof of Theorem 1. Theorem 1 (Unambiguous DNFs). For any n ≥ 2, there exists an unambiguous DNF f : 2 {0, 1}n → {0, 1} satisfying C0 (f ) = Ω(n2 ).

UC1 (f ) = O(n),

Proof. For each n, we will derive the DNF f from a “signed” set-pair system T = {(PT , NT )}T that has several convenient properties. Signed set-pair system.

Fix the universe U to be U = B1 ⊔ B2 ⊔ · · · ⊔ Bn ,

where B1 = {1, . . . , n}, B2 = {n + 1, . . . , 2n}, . . . , Bn = {(n − 1)n + 1, . . . , n2 }. So, every |Bi | = n, and |U | = n2 . Later, we will have one variable xu in the DNF f for every element u ∈ U . Now, for every unordered pair {i, j}, let {i,j}

λi

{i,j}

: Bi → [n],

λj

: Bj → [n],

be bijections that will suitably be chosen later in order to ensure DNF term-width O(n). Fix k = ⌊n/2⌋, and for every S ⊆ Bi , |S| = k, and j ̸= i, define {i,j}

mi,j (S) = min λi x∈S

(x).

{i,j}

Namely, mi,j (S) is the smallest value of λi over S. Next, we define the “prefix set” Ai,j (S) to {i,j} comprise of all the elements in Bj that λj maps to a value that is at most mi,j (S), that is {i,j}

Ai,j (S) = {y ∈ Bj : λj 12

(y) ≤ mi,j (S)}.

Now, for every i ∈ [n] and S ⊆ Bi , |S| = k, define the “positive set” Pi,S and “negative set” Ni,S as [ Pi,S := S, Ni,S = (Bi \ S) ∪ Ai,j (S). j̸=i

Note that Pi,S ∩ Ni,S = ∅, since each Ai,j (S) ⊆ Bj , and Bj is disjoint from Bi . The desired signed set-pair system is then T = {(PT , NT )}T , where T = (i, S) ranges over all i ∈ [n] and S ⊆ Bi , |S| = k. Pairwise incompatibility. We now argue that for every distinct pair (i, S) and (j, S ′ ) (where S ⊆ Bi and S ′ ⊆ Bj ), it holds that Pi,S ∩ Nj,S ′ ̸= ∅

or

Pj,S ′ ∩ Ni,S ̸= ∅.

To see this, first suppose i = j, so that S ̸= S ′ . Then, observe that S ′ has at least one element in Bi \ S, and hence Pj,S ′ ∩ Ni,S ̸= ∅. Now suppose that i ̸= j, and let b = mj,i (S ′ ).

a = mi,j (S), {i,j}

If a ≤ b, then the element x ∈ S for which λi

(x) = a belongs to Aj,i (S ′ ); hence

Pi,S ∩ Nj,S ′ ̸= ∅. {i,j}

On the other hand, if a > b, then the element x ∈ S ′ for which λj hence

(x) = b belongs to Ai,j (S);

Pj,S ′ ∩ Ni,S ̸= ∅. Thus, we have shown that for any distinct (i, S) and (j, S ′ ), it holds that at least one of Pi,S ∩ Nj,S ′ and Pj,S ′ ∩ Ni,S is non-empty. {i,j}

Choosing the bijections. For every unordered pair {i, j}, choose both the bijections λi and {i,j} λj independently and uniformly at random. We will argue via the probabilistic method that there exists a choice of bijections satisfying that |Pi,S | + |Ni,S | = O(n) for every (i, S). To that end, fix any i ∈ [n], and S ⊆ Bi , |S| = k; note that |Pi,S | = |S| = k. We will now bound the probability of the bad event that |Ni,S | is large. For any j ̸= i, note that the set {i,j} {λi (x) : x ∈ S} is a uniformly random subset of [n] of size k, and the event mi,j (S) > t occurs only if all the members of this subset are larger than t; that is,
  n−t t k k
Pr[mi,j (S) > t] = n ≤ 1 − ≤ e−tk/n ≤ e−t/3 . n k Thus, we can choose λ > 0 small enough so that h i E eλmi,j (S) ≤ 2.

13

{i,j}

Now note that since λi for every j ̸= i is sampled independently, the different random variables mi,j (S) are independent. Therefore, by Markov’s inequality, we have that   X Pr  mi,j (S) > Cn ≤ 2n−1 e−λCn . j̸=i

The total number of (i, S) pairs is n nk ≤ n2n . Thus, choosing C to be an appropriately large constant, we can union bound P the bad event above over all these pairs, and obtain that with positive probability, it holds that j̸=i mi,j (S) ≤ Cn for every (i, S) pair. P In particular, this implies that there exists a good realization of all the bijections for which j̸=i mi,j (S) ≤ Cn for every (i, S) pair — we will choose this realization of the bijections for our signed set system. Next, observe that the size of any Ai,j (S) is exactly mi,j (S), and hence, for every (i, S), [

Ai,j (S) =

X

mi,j (S) ≤ Cn.

j̸=i

j̸=i

This means that |Pi,S | + |Ni,S | = k + n − k +

[

Ai,j (S) ≤ n + Cn = O(n),

j̸=i

as desired. Large hitting number for the positive sets. Consider the family of positive sets P = {Pi,S : i ∈ [n], S ⊆ Bi , |S| = k}. The hitting/transversal number τ (P) of this family is the size of the smallest subset of U that has non-empty intersection with every member of P. Let H be such a subset that realizes the hitting number. For any i ∈ [n], since H must intersect every Pi,S = S ⊆ Bi , |S| = k, it must be the case that |H ∩ Bi | ≥ n − k + 1 ≥ n/2 + 1. Since the above holds for every i ∈ [n], and all the Bi ’s are disjoint, we obtain that τ (P) = |H| ≥ n(n/2 + 1) = Ω(n2 ). Constructing the DNFs. We now define the unambiguous DNF f with respect to the signed set-pair system constructed above. Concretely, we will have a variable xu for every u ∈ U , so that 2 f maps {0, 1}n → {0, 1}. Let x = (xu )u∈U ; we define   _ ^ ^  xu ∧ ¬xv  , (9) f (x) = (i,S)

u∈Pi,S

v∈Ni,S

where the OR ranges over all i ∈ [n], S ⊆ Bi , |S| = k. Since |Pi,S | + |Ni,S | = O(n) for all (i, S) as argued above, the term-width of f is O(n). We now argue that f is an unambiguous DNF, which will imply that UC1 (f ) = O(n). Towards this, fix any x for which f (x) = 1; this must mean that at least one of the conjunctions is true. Namely, there exists (i, S) for which ^ ^ xu ∧ ¬xv = 1, u∈Pi,S

v∈Ni,S

14

which in turn fixes xu = 1 for every u ∈ Pi,S , and xu = 0 for every v ∈ Ni,S . Now consider any pair (j, S ′ ) that is distinct from (i, S). As argued above, (j, S ′ ) and (i, S) are pairwise incompatible, meaning that Pi,S ∩ Nj,S ′ ̸= ∅ or Pj,S ′ ∩ Ni,S ̸= ∅. But since the variables in Pi,S , Ni,S are pinned down, we have that xv = 1 for some v ∈ Nj,S ′ or xu = 0 for some u ∈ Pj,S ′ . In particular, this means that the conjunction corresponding to the pair (j, S ′ ) evaluates to false, i.e., ^ ^ xu ∧ ¬xv = 0. u∈Pj,S ′

v∈Nj,S ′

Thus, exactly one term in the DNF evaluates to true for any x satisfying f (x) = 1, meaning that f is an unambiguous DNF. 2 Finally, we argue that C0 (f ) = Ω(n2 ). Towards this, consider the input x = 0n , for which f (x) = 0. Observe that any 0-certificate ρx for x must necessarily set ρx,u = 0 for at least one u ∈ Pi,S for every pair (i, S). Otherwise, if ρx,u = ∗ for every u ∈ Pi,S for some pair (i, S), we could set all of these ∗ values to 1 and set any remaining ∗ values in Ni,S to 0, thus obtaining an x′ that is consistent with ρx but makes the conjunction corresponding to (i, S) true. This means that any 0-certificate ρx for x must have at least one non-∗ (set to 0) within every Pi,S . In particular, the set {u ∈ U : ρx,u ̸= ∗} has non-empty intersection with every member of the family of positive sets P, meaning that its size is at least the hitting number τ (P). We thus have that C0 (f ) ≥ C0 (f, x) ≥ τ (P) = Ω(n2 ). This completes the proof.

4

Constant-gadget Lifting

We now show how we can lift the separation between certificate complexities above to a communication problem. Crucially, we accomplish this lifting with a constant-sized gadget. For a gadget function g : {0, 1}k × {0, 1}k → {0, 1} and a Boolean function f : {0, 1}n → {0, 1}, let f ◦ g n : {0, 1}kn × {0, 1}kn → {0, 1} denote the communication problem that arises from lifting f with the gadget g, defined as f ◦ g n ((x1 , . . . , xn ), (y1 , . . . , yn )) = f (g(x1 , y1 ), . . . , g(xn , yn )), where each xi , yi ∈ {0, 1}k . We will construct a constant-sized gadget g such that upon lifting our unambiguous DNFs from Theorem 1 through the gadget g, one obtains a communication problem h that has large separation between two measures: Par1 (h) and Cov0 (h). Recall that Cov0 (h) is the minimum number of 0monochromatic rectangles required to cover all the 0-entries in the communication matrix of h. The quantity Par1 (h) is defined to be the minimum number of 1-monochromatic rectangles required to partition all the 1-entries in the communication matrix of h. We now restate and prove Theorem 2. Theorem 2 (Constant-gadget Lifting). There exists a gadget function g : {0, 1}3 ×{0, 1}3 → {0, 1}, such that for all large enough n, for the DNF f constructed in Theorem 1, denoting by h the lifted 2 2 2 communication problem f ◦ g n : {0, 1}3n × {0, 1}3n → {0, 1}, it holds that log Cov0 (h) = Ω(n2 ).

15

Since for any f : {0, 1}n → {0, 1} and any gadget g : {0, 1}k × {0, 1}k → {0, 1}, it is known that log Par1 (f ◦ g n ) ≤ O(k · UC1 (f )), we obtain the following corollary by combining Theorem 2 and Theorem 1. Corollary 4.1 (Communication Complexity Separation). For all large enough n, there exists a 2 2 communication problem h : {0, 1}3n × {0, 1}3n → {0, 1} for which log Cov0 (h) = Ω(n2 ).

log Par1 (h) = O(n),

Since the rank (over the reals) of the communication matrix of h is at most Par1 (h), and since every deterministic communication protocol for h having cost D(h) induces a cover of all its 0entries by at most 2D(h) rectangles, Corollary 4.1 also helps us shave all the log factors in the quadratic lower bound of Göös et al. [2018, Theorem 1.2] for the log-rank conjecture, which, to the best of our knowledge, was the previous best lower bound for the conjecture. Corollary 4.2 (Quadratic Lower Bound for Log-Rank). There exists a family of communication problems h for which
D(h) ≥ Ω (log rank(h))2 . In the rest of this section, we will systematically establish Theorem 2. We start by defining the gadget function g.

4.1

Cyclic Gadget

Fix Q = 23 , and let ZQ = {0, 1, . . . , Q − 1} be the additive group modulo Q. We identify every element of ZQ with its binary representation in {0, 1}3 . The gadget function g : {0, 1}3 × {0, 1}3 → {0, 1} is then defined as ( 0 if y − x ∈ {−1, 0, 1} mod Q, g(x, y) = (10) 1 otherwise. That is, g outputs 0 only when y is either x, or equal to one of the two neighbors of x around the cycle 0, 1, . . . , Q − 1, 0. Note that the gadget is symmetric, namely g(x, y) = g(y, x). We recall the notation from Section 3, where the universe U = [n2 ] = B1 ⊔ · · · ⊔ Bn , and U Bi = {(i − 1)n + 1, . . . , in}. The lifted communication problem h : ZU Q × ZQ → {0, 1} is then defined as h(x, y) = f ((g(xu , yu ))u∈U ). 2

Since g(x, x) = 0 for every x, and f (0n ) = 0, we have that h(x, x) = 0 for all x ∈ ZU Q.

4.2

Characterizing Matrix

We will now define a matrix M that is closely related to the communication matrix of h. The purpose of defining this matrix is that the spectrum of this matrix will govern log Cov0 (h). Namely, as we shall see in Section 4.3 ahead, in order to lower-bound log Cov0 (h), it will suffice to lowerbound the minimum eigenvalue of M . We will express M via the Kronecker product of Q × Q matrices that will serve as building blocks for M , and whose rows and columns we will index by ZQ . Let IQ and JQ be the Q × Q 16

identity matrix and all-ones matrix respectively. Let CQ be the adjacency matrix of the cycle over ZQ , i.e., CQ (x, y) = 1 ⇐⇒ x − y ∈ {−1, 1} Now define the two matrices W0 and W1 as  1 1/4 0 . . . 1/4 1 1/4 . . .  1  W0 = IQ + CQ =  ...  4  0 0 0 ... 1/4 0 0 ...  0 0 1 ... 1 0 0 0 . . . 1   W1 = JQ − IQ − CQ =  ...  1 1 1 . . . 0 0 1 1 ... 1

mod Q

 1/4 0      1/4 1 1/4 0 1/4 1  1 0 1 1     0 0 0 0 0 0

0 0

Both W0 and W1 are symmetric and non-negative. The sum of every row in W0 is equal to c0 := 1 +

3 1 1 + = , 4 4 2

(11)

and the sum of every row in W1 is equal to w0 := Q − 3.

(12)

(As will become clearer later, we use the subscript 0 to denote both these quantities because they correspond to the eigenvalues of the all-ones vector, which is the eigenvector at frequency 0 in the Fourier spectrum.) Most importantly, W0 (x, y) > 0 ⇐⇒ g(x, y) = 0, W1 (x, y) > 0 ⇐⇒ g(x, y) = 1.

(13)

The 1/4 scaling on CQ in the definition of W0 is deliberate, and will later ensure that all the eigenvalues of W0 corresponding to the Fourier spectrum are positive. Now, for any i ∈ [n] and for any S ⊆ Bi , |S| = k = ⌊n/2⌋, let b(i,S) ∈ {0, 1}U be defined as b(i,S) = 1S ,

i.e., b(i,S) = 1 ⇐⇒ u ∈ S. u

Then, let N = Q|U | , and define the N × N matrix Mi,S as O Mi,S = Wb(i,S) . u

(14)

u∈U

In particular, for x = (xu )u∈U and y = (yu )u∈U , where xu , yu ∈ ZQ , the entry Mi,S (x, y) is precisely Y Mi,S (x, y) = Wb(i,S) (xu , yu ). (15) u

u∈U

17

Note that every entry in Mi,S is non-negative. Exactly k = |S| terms in the product above correspond to W1 matrices. Since k ≥ 1, and the diagonal of W1 is 0, we get that the diagonal of Mi,S is 0. Also, since the row-sum of the Kronecker product is equal to the product of the row-sums |U |−k k of the individual matrices, we get that every row in every Mi,S sums to c0 w0 . Finally, define M as M=

n X X

Mi,S .

i=1 S∈(Bi ) k

By the properties of each Mi,S , M is non-negative, and has a zero diagonal. Every row in M sums to       n |U |−k k n |U | w0 k . (16) d := n c w0 = n c c0 k 0 k 0
Furthermore, if M (x, y) > 0, then it must be the case that for some i and some S ∈ Bki , Mi,S (x, y) > 0, meaning that every term in the product in (15) is positive. But this means, from (13), that for every u ∈ U , g(xu , yu ) = b(i,S) , u and hence, h(x, y) = f ((g(xu , yu ))u∈U ) = f (b(i,S) ) = f (1S ) = 1. In the above, we used the precise form (9) of the DNF f from Theorem 1, where the input 1S satisfies exactly the term corresponding to (i, S). We have thus established a crucial property of the matrix M , namely M (x, y) > 0 =⇒ h(x, y) = 1.

(17)

If we interpret M as the adjacency matrix of a graph, where x and y are connected by an edge iff M (x, y) > 0, then the above relation implies that a 0-entry in the communication matrix of h translates to the absence of an edge in M . This viewpoint will be helpful ahead. In summary, M is a real, symmetric, non-negative matrix. Its diagonal entries are zero, every row sums to d, and every positive entry in M corresponds to a 1-input for h.

4.3

Bounded Spectrum to Communication Lower Bound

We now show how a lower bound on the minimum eigenvalue of the matrix M translates to a lower bound on log Cov0 (h) for the lifted communication problem h. Towards this, as mentioned above, we will first interpret the matrix M as the adjacency matrix of a graph. Namely, we will consider an undirected graph GM on N vertices, where two vertices x and y are connected by an (unweighted) edge iff M (x, y) > 0. Recall that every row in M has a common sum d > 0. The following lemma states that no independent set in GM can be larger than εN , if every eigenvalue of M is at least −dε for some ε ≥ 0. Lemma 4.1 (Bounded Independent Sets). Let λmin be the minimum eigenvalue of M , and suppose that λmin ≥ −dε, for some ε ≥ 0. Then, every independent set S in the graph GM satisfies that   ε |S| ≤ N ≤ εN. 1+ε 18

Proof. Fix any independent set S in GM . Let 1 be the all-ones vector, and let 1S be the indicator vector of the set S (i.e., 1S,i = 1 iff i ∈ S). Let z be the component of 1S that is orthogonal to 1, and observe that 1S =

|S| 1 + z. N

For convenience, let δ := |S| N . We then have that ∥1S ∥22 = δN = δ 2 N + ∥z∥22 =⇒ ∥z∥22 = δN (1 − δ).

(18)

Now, by the variational form for the minimum eigenvalue of M , it holds that z T M z ≥ λmin ∥z∥22 ≥ −dεδN (1 − δ),

(19)

where we used our assumption on the minimum eigenvalue of M . On the other hand, note that since S is an independent set in GM , and M has a zero diagonal, X M (x, y) = 0. 1TS M 1S = x,y∈S

This gives us that z T M z = (1S − δ1)T M (1S − δ1) = δ 2 N d − 2δ1TS M 1 = δ 2 N d − 2δ 2 N d = −δ 2 N d.

(20)

Combining (19) and (20), we get that δ 2 N d − dεδN (1 − δ) ≤ 0. Now, if δ = 0, the claimed bound holds immediately. Otherwise, we can divide throughout by δN d to get ε δ − ε(1 − δ) ≤ 0 =⇒ δ ≤ ≤ ε. 1+ε

We conclude this subsection by arguing how bounded independent sets give us the desired lower bound on log Cov0 (h). Let R = X × Y be any 0-monochromatic rectangle in the communication matrix of h, where X, Y ⊆ ZU Q . Let SR be the diagonal elements in R, namely SR = {x ∈ ZU Q : (x, x) ∈ R} = X ∩ Y. For any x, y ∈ SR , it holds that (x, y) ∈ R since R is a rectangle, and hence h(x, y) = 0, since R is 0-monochromatic. From (17), it must then hold that M (x, y) = 0. We thus have that M (x, y) = 0 for every x, y ∈ SR , meaning that SR is an independent set in GM . From Lemma 4.1, this means that |SR | ≤ εN . So, let F be any collection of 0-monochromatic rectangles that cover every 0-entry in the communication matrix of h. Since h(x, x) = 0 for all x, the collection must cover all the Q|U | = N diagonal entries of the communication matrix. Therefore, by the union bound X 1 N≤ |SR | ≤ εN |F | =⇒ |F | ≥ . ε R∈F

19

Since the bound above holds for every 0-monochromatic rectangle cover, we have that Cov0 (h) ≥

1 =⇒ log Cov0 (h) ≥ log(1/ε). ε 2

Thus, if we can show that the minimum eigenvalue of M is lower-bounded by −dε for ε = ργn for some constants 0 < ρ < 1 and γ > 0, we will have obtained log Cov0 (h) ≥ γn2 log(1/ρ) = Ω(n2 ), which is the desired bound of Theorem 2. Therefore, the remaining pursuit is to show that the minimum eigenvalue of M is lower-bounded by a value that is not too negative and pretty close to 2 0, namely −dργn .

4.4

Fourier Spectrum

We will now compute the eigenvalues of the matrix M . For this, we will first precisely compute the eigenvalues of the matrices W0 and W1 , corresponding to eigenvectors in the Fourier spectrum. Concretely, for r ∈ ZQ , let χr ∈ CQ denote the vector at frequency r in the Fourier spectrum. The size of χr is Q, and for x ∈ ZQ , the xth entry of χr is defined as   2πirx rx , (21) χr (x) = ω = exp Q   where ω = exp 2πi is the primitive Qth root of unity, and satisfies that ω Q = 1, ω r ̸= 1 for Q P P r 1 ≤ r < Q, and Q−1 r=0 ω = 0. For r, s ∈ ZQ , note that ⟨χr , χs ⟩ = x∈ZQ χr (x)χs (x) is equal to Q if r = s, and 0 if r ̸= s. Thus, the Q-many χr vectors are mutually orthogonal and non-zero. We next argue that they form an eigenbasis for W0 and W1 . Recall that W0 and W1 are defined in terms of the identity matrix IQ , the all-ones matrix JQ and the cycle matrix CQ ; each of these matrices is a circulant matrix. Namely, the entry at position (x, y) depends only on y − x (modulo Q). For any circulant matrix A, where A(x, y) = a(y − x), every χr is an eigenvector, since X (Aχr )(x) = a(y − x)χr (y) y∈ZQ

=

X

a(t)χr (x + t) =

t∈ZQ

= χr (x)

X

a(t)χr (x)χr (t)

t∈ZQ

X

a(t)χr (t).

t∈ZQ

Thus, every χr is an eigenvector for W0 as well as W1 .3 For the identity P matrix IQ , each χr has eigenvalue 1. For the all-ones matrix JQ , each χr has eigenvalue equal to x∈ZQ χr (x), which is equal to Q if r = 0, and 0 if r ̸= 0. Finally, for the cycle matrix CQ , (CQ χr )(x) = χr (x − 1) + χr (x + 1) = (ω r + ω −r ) · χr (x) = 2 cos(2πr/Q)χr (x). 3

A similar calculation also appears in the recent work of Larsen et al. [2026] which uses spectral analysis over Cayley graphs to establish lower bounds in replicable learning.

20

In total, we obtain that the eigenvalues cr and wr for the matrices W0 and W1 , corresponding to the eigenvector χr , are equal to 1 cr = 1 + cos(2πr/Q), 2 ( Q−3 if r = 0, wr = −1 − 2 cos(2πr/Q) if r ̸= 0.

(22) (23)

As also alluded to earlier, χ0 is the all-ones vector, and hence has eigenvalue equal to the row-sums (namely c0 = 3/2 and w0 = Q − 3 from (11) and (12)) for W0 and W1 respectively. Note that every cr is positive; in particular, 21 ≤ cr ≤ 32 . The 1/4 scaling on the entries in CQ was useful precisely for this. |U | Now, for a frequency vector ξ = (ξu )u∈U ∈ ZQ , where every ξu ∈ ZQ , consider the tensor N N th entry of χ is product vector χξ = ξ u∈U χξu ∈ C , where for x = (xu )u∈U , xu ∈ ZQ , the x defined as ! Y 2πi X χξ (x) = χξu (xu ) = exp ξu x u . (24) Q u∈U

u∈U

Since {χr }r∈ZQ form a basis for CQ , the Q|U | = N many vectors {χξ }ξ∈Z|U | form a basis for CN . Q

We will nowN argue that these are eigenvectors for the matrix M . Indeed, for any tensor product matrix A = u∈U Au , where for each Au , χξu is an eigenvector with eigenvalue µu , it holds that X Y Au (xu , yu )χξu (yu ) (Aχξ )(x) = |U | y∈ZQ u∈U



 = =

Y

X 

Au (xu , yu )χξu (yu )

u∈U

yu ∈ZQ

Y

µu χξu (xu )

u∈U

! =

Y

µu

χξ (x).

u∈U

Thinking of A as Mi,S , where, recalling (14), each Au is either W0 or W1 , and χξu is an eigenvector for Au with eigenvalue either cξu or wξu , we get from the above that any χξ is an eigenvector for Mi,S with eigenvalue Y Y wξu cξu . u∈S

u∈S /

Since M is the sum of Mi,S over all (i, S), we get that χξ is an eigenvector for M with eigenvalue λξ , where ! n n X X Y Y Y X X Y wξ u λξ = wξu cξu = cξu . (25) c ξ u i=1 S∈(Bi ) u∈S i=1 S∈(Bi ) u∈S u∈U u∈S / k k In the above, dividing by cξu is safe since every cξu > 0. 21

The product term inside the double summation above is an elementary symmetric polynomial of degree k. Namely, let X Y ek (y1 , . . . , yt ) = yj j∈T T ∈([t] k)

denote the elementary symmetric polynomial of degree k in the variables y1 , . . . , yt . Note that 0 ek (αy1 , . . . , αyt ) = αk ek (y1 , . . . , yt ). Thus, if we define qr = wcrr /w /c0 , we have that Y

λξ =

cξu

u∈U

Y

=

cξu

=

i=1 ! n X

 ek ek

i=1

u∈U

Y

! n X

! cξu

u∈U

w0 c0

wξu cξu



!

u∈Bi

!   w0 qξu · c0 u∈Bi

k X n

  ek (qξu )u∈Bi .

i=1

Recalling the expression for the common row-sum d of M from (16), we obtain the following λ expression for the normalized eigenvalue dξ :   ! ! n e n ) (q X Y Y cξ k ξu u∈Bi λξ cξu 1 1X u
= = Pi , (26) n d c0 n c0 n k i=1 | i=1 u∈U u∈U {z } Pi

where we defined   ek (qξu )u∈Bi
Pi := . n

(27)

k

Next, let ℓi be the number of non-zero ξu values within Bi , and L be the number of non-zero ξu values overall. Namely, ℓi := |{u ∈ Bi : ξu ̸= 0}| ,

L := |{u ∈ U : ξu ̸= 0}| =

n X

ℓi .

(28)

i=1

Since q0 = 1, Pi may be written as
ek 1n−ℓi , (qξu )u∈Bi :ξu ̸=0
. Pi = n

(29)

k

In the above 1n−ℓi = (1, . . . , 1) . We next bound the values of qξu where ξu ̸= 0. For any r ∈ | {z } n − ℓi times

ZQ , r ̸= 0, and x = cos(2πr/Q) ∈ [−1, 1], we have that |qr | =

wr /w0 (3/2)|1 + 2x| = . cr /c0 (Q − 3)(1 + x/2)

22

(Using (22),(23))

The denominator above is always positive. Now, if x ≥ −1/2, we have that   (3/2)(1 + 2x) 3 (3/2)|1 + 2x| = =3 2− ≤ 3. 1 + x/2 1 + x/2 2+x

(since x ≤ 1)

On the other hand, if x < −1/2, we have that (3/2)|1 + 2x| −(3/2)(1 + 2x) = =3 1 + x/2 1 + x/2



3 −2 2+x

 ≤ 3.

(since x ≥ −1)

Thus, it always holds that (3/2)|1+2x| ≤ 3, which gives us that 1+x/2 |qr | ≤ θ :=

3 3 = . Q−3 5

(30)

Namely, the qξu values where ξu ̸= 0 are at most θ = 3/5 in absolute value. It thus remains to reason about polynomials of the form ek (1n−ℓi , t1 , . . . , tℓi ), where every |ti | ≤ θ. This is the focus of the next subsection.

4.5

Bounding the Polynomial

Before proceeding to the exact technical analysis, we provide some intuition on what kinds of polynomial bounds we’d like to derive. Recall first the expression for the normalized eigenvalue λξ /d from (26): ! n Y cξ λξ 1X u = Pi . d c0 n i=1

u∈U

Assume for the moment that L — the number of non-zero ξu values — is positive. Then, observe that  !   L Y cξ Y cξ c r u u ≤ max = ≤ ρL r∈ZQ : r̸=0 c0 c0 c0 u : ξu ̸=0

u∈U

for some ρ < P1, since for r ̸= 0, we have that cr /c0 < 1 (see (22)). Now, if λξ < 0, it must be the case that n1 ni=1 Pi < 0. Since the smallest that this fraction can be is −1, we get that Y cξ λξ u ≥− ≥ −ρL . d c0 u∈U

Pn 2 So, if we can show that L = i ℓi ≥ Ω(n ) whenever i=1 Pi < 0, we will have obtained our desired lower bound on λξ (if λξ is positive, the lower bound holds vacuously). If the number of blocks i for which ℓi > Ω(n) (“bad” blocks) is at least n/2, we immediately have that L ≥ Ω(n2 ). Otherwise, the number of blocks for which ℓi ≤ Ω(n) (“good” blocks) is larger than n/2. Here, we note that, since each of the ℓi entries in Pi that are not equal to 1 are at most θ in absolute value, we can show that |Pi | ≤ 2−Θ(ℓi ) . In particular, for the bad blocks, −Θ(n) . Suppose we could now show that any good block since ℓi > Ω(n), this means that |PP i| ≤ 2 −Θ(ℓ ) i satisfies Pi ≥ 2 > 0. Then, if i Pi is negative, it must be the case that the contribution of bad blocks (in magnitude) is strictly larger than the contribution of the good blocks. Combining this with the upper bound on |Pi | for bad blocks and the lower bound on Pi for good blocks then lets us conclude that L ≥ Ω(n2 ). This sketch leads us to proving the following lemma: P

23

Lemma 4.2 (Symmetric Polynomial Bound). Fix n ≥ 88, any ℓ satisfying 0 ≤ ℓ ≤ n, any n−ℓ t1 , . . . , tℓ ∈ [−θ, θ] where θ = 35 , and any k satisfying 0 ≤ k ≤ n/2. Let P = ek (1 n,t1 ,...,tℓ ) .4 Then: (k ) (a) If k ≥ n/3, then |P | ≤ (0.88)ℓ . (b) If ℓ ≤ n/128, then P ≥ (0.12)ℓ > 0. Part (a) of the lemma above follows from a straightforward application of Maclaurin’s inequality. Part (b) is much more involved, although it only requires elementary analysis, together with some careful definitions. Before delving into the technical details though, we will sketch the high-level argument here. The starting point is to view the elementary symmetric polynomial ek (y1 , . . . , yn ) in the context of its generating function. That is, it can be readily checked that ek (y1 , . . . , yn ) is precisely the coefficient of z k in n Y

(1 + yi z).

i=1

In particular, instantiating this with (y1 , . . . , yn ) = (1n−ℓ , t1 , . . . , tℓ ), we get that ek (1n−ℓ , t1 , . . . , tℓ ) is equal to the coefficient of z k in (1 + z)

n−ℓ

ℓ Y (1 + ti z). i=1

Let us consider the expression above at the boundary t1 = · · · = tℓ = −θ, which is equal to (1 + z)n−ℓ (1 − θz)ℓ . As it will turn out later, ek (1n−ℓ , t1 , . . . , tℓ ) is increasing in every ti , and hence, we may focus on lower-bounding it at this boundary. Namely, we wish to lower-bound ek (1n−ℓ , (−θ)ℓ ), which is equal to the coefficient of z k in (1 + z)n−ℓ (1 − θz)ℓ , by an exponentially small quantity in ℓ (up to
the multiplicative nk factor). This motivates defining the polynomial Fr (z) = (1 + z)n−ℓ (1 − θz)r =

X

(r)

Cj z j ,

j (r+1)

(r)

and aiming to show that Ck ≥ c · Ck for some c < 1, since by recursively invoking this (ℓ) inequality ℓ times, we will achieve our desired lower bound on ek (1n−ℓ , (−θ)ℓ ) = Ck . However, the polynomials Fr themselves satisfy the relation Fr+1 (z) = (1 − θz)Fr (z), which, upon comparing coefficients, gives (r+1)

Cj (r+1)

(r)

= Cj

(r)

(r)

− θCj−1 . (r)

(r)

So, in order to show that Ck ≥ c · Ck , it suffices to instead show that Cj ≥ c′ · Cj−1 for some c′ < 1, for all j ≤ k. These steps are precisely what the following analysis concretizes. 4

We use the convention that e0 (y1 , . . . , yt ) = 1.

24

Proof. We first establish part (a). Suppose k ≥ n/3: we have that |P | ≤

ek (1n−ℓ , |t1 |, . . . , |tℓ |)
n

(triangle inequality)

k ek (1n−ℓ , θℓ )
≤ n k

(where θℓ = (θ, . . . , θ)) | {z } ℓ times

k



ℓ 1 − (1 − θ) n   kℓ ≤ exp −(1 − θ) n   (θ − 1)ℓ ≤ exp 3

≤

(Maclaurin’s inequality) (1 + x ≤ ex for all real x) (since k ≥ n/3)

≤ (0.88)ℓ .

(substituting θ = 3/5)

We now move on to part (b), which we will establish in stages. Bounding a certain coefficient ratio. Let ℓ ≤ n/128, and define s := n − ℓ. Note that 127n/128 ≤ s ≤ n. Now, for any 0 ≤ r ≤ ℓ, define the univariate polynomial X (r) Fr (z) = (1 + z)s (1 − θz)r = Cj z j , (31) j≥0

r
Pj (r) s j−p is the coefficient of z j in F (z).5 We note that F (z) is a where Cj = r r p=0 p j−p (−θ) polynomial in z of degree s + r. Then, we have the following crucial claim which lower-bounds the (r) (r) ratio Cj /Cj−1 : Claim 4.3 (Coefficient Ratio). For any j satisfying 1 ≤ j ≤ k, (r)

Cj

4 (r) ≥ Cj−1 > 0. 5

Proof. We will induct on j, keeping r fixed. As the base case, consider j = 1. We have that (r) C0 = 1, and (r)

C1 = s − rθ = n − ℓ − rθ 8ℓ 8n ≥ n − ℓ − ℓθ = n − ≥n− 5 640 79n 4 4 (r) = ≥ = C0 . 80 5 5

(since ℓ ≤ n/128)

Thus, the base case holds. We now proceed to the inductive step. Suppose that the claim is true for j, where 1 ≤ j ≤ k −1; we will then prove the claim for j + 1, meaning 4 (r) (r) Cj+1 ≥ Cj . 5 5

We use the convention that

0 0

= 1 and

a b

= 0 for a < b.

25

Recall the definition (31) of the polynomial Fr (z), defined for all real z: X (r) Cj z j . Fr (z) = (1 + z)s (1 − θz)r = j≥0

Differentiating, we have that Fr′ (z) = −rθ(1 + z)s (1 − θz)r−1 + s(1 + z)s−1 (1 − θz)r . Multiplying on both sides by (1 + z)(1 − θz) and collecting terms gives (1 + z)(1 − θz)Fr′ (z) = (s − rθ − θ(s + r)z)Fr (z).

(32)

Since (32) is a polynomial identity which holds for all z, the coefficients of every z j must match on both sides. The coefficient of z j on the left side is (r)

(r)

(j + 1)Cj+1 + (1 − θ)jCj

(r)

− θ(j − 1)Cj−1 .

The coefficient of z j on the right side is (r)

(s − rθ)Cj

(r)

− θ(s + r)Cj−1 .

Equating, we get (r)

(r)

(j + 1)Cj+1 = (s − rθ − (1 − θ)j)Cj

(r)

− θ(s + r − j + 1)Cj−1 . (r)

(r)

n 5 Note that s+r−j+1 ≥ 127n 128 − 2 +1 > 0; furthermore, by the inductive hypothesis, 0 < Cj−1 ≤ 4 Cj , giving   5 (r) (r) (j + 1)Cj+1 ≥ s − rθ − (1 − θ)j − θ(s + r − j + 1) Cj . 4

It then remains to show that s − rθ − (1 − θ)j − 54 θ(s + r − j + 1) ≥ 4(j+1) 5 . Towards this, we have that 5 4(j + 1) s − rθ − (1 − θ)j − θ(s + r − j + 1) − 4  5     5 9 9 9 5 4 = 1 − θ s − rθ − j − θ − θ+ 4 4 5 4 4 5       5 127n 9nθ 9 9 5 4 ≥ 1− θ − −j − θ − θ+ 4 128 512 5 4 4 5        5 127n 9nθ 9 9 n 5 4 ≥ 1− θ − − − θ −1 − θ+ 4 128 512 5 4 2 4 5 n 11 = − ≥ 0, 80 10

n (since s ≥ 127n 128 , r ≤ ℓ ≤ 128 )

(since j ≤ k − 1 ≤ n/2 − 1) (substituting θ = 3/5)

where the last inequality holds true when n ≥ 88. Thus, the inductive step is complete, proving the claim.

26

The case where t1 = · · · = tℓ = −θ. We now establish the bound in part (b) in the special case where t1 = · · · = tℓ = −θ; later, we will show that this suffices for the general case. Note that in this case,
ℓ
Pk s k−p ek (1s , (−θ)ℓ ) p=0 p k−p (−θ)

= . (33) P = n n k

k

Now, for 0 ≤ r < ℓ, recall: Fr (z) = (1 + z)s (1 − θz)r =

X

(r)

Cj z j ,

j≥0

Fr+1 (z) = (1 + z)s (1 − θz)r+1 =

X

(r+1) j

Cj

z .

j≥0

Fix any j, where 1 ≤ j ≤ k. We have: (r) Cj =

 j   X s r (−θ)j−p , p j−p

(34)

p=0

and hence, (r) (r) Cj − θCj−1 =

       j−1   X s r r s r j−p (−θ) + + p j−p j−1−p j 0 p=0

    X  j−1   j   X s r+1 s r+1 s r+1 (r+1) j−p = (−θ) + = (−θ)j−p = Cj . p j−p j 0 p j−p p=0

p=0

(r)

(r)

But, from Claim 4.3, it also holds that 0 < Cj−1 ≤ 54 Cj ; thus, we get   1 (r) 5 (r) (r+1) Cj ≥ 1 − θ Cj = Cj . 4 4 The bound above holds also for j = 0. Iterating, we thus get that for every j satisfying 0 ≤ j ≤ k,  ℓ  ℓ   1 1 s (ℓ) (0) Cj ≥ Cj = . (35) 4 4 j Finally, recalling the expression (33) for P , we get
ℓ
Pk s k−p ek (1s , (−θ)ℓ ) p=0 p k−p (−θ)

P = = n n k k

(ℓ) 1 ℓ s C = nk
≥ 4 n
k k k  ℓ n−ℓ
 ℓ ℓ−1 1 Y n−k−p 1 k
= = n 4 4 n−p k p=0

 ℓ ℓ−1 1 Y n2 − p ≥ 4 n−p p=0  ℓ   1 63 ℓ ≥ 4 127

(using (34) and (35))

(since k ≤ n/2)

(p ≤ ℓ ≤ n/128 =⇒

≥ (0.12)ℓ . 27

n −p 63 2 n−p ≥ 127 )

The general case where t1 , . . . , tℓ ∈ [−θ, θ]. We will now conclude the proof of part (b) by arguing that for any k ≥ 0 and ℓ ≥ 0, it holds simultaneously for all n ≥ 88 satisfying k ≤ n/2 and ℓ ≤ n/128 that P =

ek (1n−ℓ , t1 , . . . , tℓ )
≥ (0.12)ℓ n k

whenever t1 , . . . , tℓ ∈ [−θ, θ]. We will establish this by induction on k + ℓ. For the base cases, (n) consider: (1) k = 0, whereby P = 1 (by convention), and (2) ℓ = 0, whereby also P = nk = 1. (k ) Thus, the base cases hold. So, let k, ℓ ≥ 1, and assume as our inductive hypothesis the following: for any ℓ′ , k ′ ≥ 0, where k ′ + ℓ′ < k + ℓ, it holds simultaneously for all n ≥ 88 satisfying ℓ′ ≤ n/128 and k ′ ≤ n/2 that ′

ek′ (1n−ℓ , t1 , . . . , tℓ′ ) ′
P = ≥ (0.12)ℓ , n ′

k′

whenever t1 , . . . , tℓ′ ∈ [−θ, θ]. We then wish to show that simultaneously for all n ≥ 88 satisfying ℓ ≤ n/128 and k ≤ n/2, it holds that P =

ek (1n−ℓ , t1 , . . . , tℓ )
≥ (0.12)ℓ n k

whenever t1 , . . . , tℓ ∈ [−θ, θ]. n−ℓ So, fix any n ≥ 88 satisfying ℓ ≤ n/128 and k ≤ n/2, and consider P = ek (1 n,t1 ,...,tℓ ) as a (k ) polynomial in t1 , . . . , tℓ . The partial derivative with respect to any tj is ek−1 (1n−ℓ , t1 , . . . , tj−1 , tj+1 , . . . , tℓ ) ∂P
= n ∂tj k =

k ek−1 (1(n−1)−(ℓ−1) , t1 , . . . , tj−1 , tj+1 , . . . , tℓ ) k ek−1 (1n−ℓ , t1 , . . . , tj−1 , tj+1 , . . . , tℓ )

= . · · n−1 n−1 n n k−1 k−1

Now focus on the term

ek−1 (1(n−1)−(ℓ−1) ,t1 ,...,tj−1 ,tj+1 ,...,tℓ )

(n−1 k−1 )

. We seek to invoke the inductive hypothesis

on this term: note that k ′ = k − 1 ≥ 0, ℓ′ = ℓ − 1 ≥ 0. Since ℓ ≥ 1 and ℓ ≤ n/128, we have n ≥ 128, and hence n − 1 ≥ 88. Furthermore, it holds that n n−1 n n−1 −1≤ , k−1≤ −1≤ . 128 128 2 2 So, by the inductive hypothesis, for any t1 , . . . , tj−1 , tj+1 , . . . , tℓ ∈ [−θ, θ], we have that the partial derivative with respect to tj is at least nk (0.12)ℓ−1 > 0. Summarily, we have that the partial derivative with respect to every tj is positive throughout the box [−θ, θ]ℓ . Thus, the minimum of P on this box is achieved at t1 = · · · = tℓ = −θ. However, from our analysis above of this special case, we have that the value of this minimum is at least (0.12)ℓ . This completes the inductive step, and the proof of part (b) of the lemma. ℓ−1≤

4.6

Concluding by Bounding the Minimum Eigenvalue

In what follows, we will take k = ⌊n/2⌋ when instantiating Lemma 4.2. The lemma implies that every Pi from (29) satisfies that |Pi | ≤ (0.88)ℓi ,

ℓi ≤ n/128 =⇒ Pi ≥ (0.12)ℓi > 0. 28

(36)

Let us call a block i ∈ [n] bad if ℓi > n/128, and good otherwise. Let R be the number of bad blocks. Recall the definition of L from (28), which is the number of non-zero ξu values. We will show that there is an absolute constant γ > 0 such that n X

Pi < 0 =⇒ L ≥ n2 /5000.

(37)

i=1

First, suppose that R ≥ n/2. In this case, by the definition of a bad block, we immediately have L=

n X

ℓi ≥

i=1

X

ℓi > Rn/128 ≥ n2 /256.

(38)

i bad

Otherwise, consider R < n/2. Let G = n − R > n/2 be the number of good blocks, and define X LG = ℓi . i good

Equation (36) gives a lower bound on Pi whenever i is good. Thus, X

Pi ≥

i good

X

LG

(0.12)ℓi ≥ G (0.12) G ,

(39)

i good

where the last inequality is Jensen’s inequality applied to the convex function x 7→ (0.12)x . On the other hand, for the bad blocks, we can use the upper bound from Lemma 4.2 part (a), as recorded in (36), and get X X n |Pi | ≤ (0.88)ℓi < R(0.88)n/128 < (0.88)n/128 , (40) 2 i bad

i bad

where we used P that R < n/2, and that ℓi > n/128 for bad blocks. Now, if ni=1 Pi < 0, then it must necessarily be the case that the contribution of bad blocks (in magnitude) is strictly larger than the contribution of the good blocks. That is, combining (39) and (40), it must hold that LG

G (0.12) G <

LG n (0.88)n/128 =⇒ (0.12) G < (0.88)n/128 . 2

(since G > n/2)

Taking logs, we get LG n log(1/0.88) n > ≥ G 128 log(1/0.12) 2500 Since G > n/2, this implies L ≥ LG > n2 /5000. Combining (38) and (41), we get that n X

Pi < 0 =⇒ L ≥ n2 /5000

i=1

as desired. 29

(41)

We now finally translate the bound above to a bound on the minimum eigenvalue of the matrix M . Recall from Equation (26) that every eigenvalue λξ of M satisfies ! n Y cξ λξ 1X u = Pi . d c0 n i=1

u∈U

Q

c ξu u∈U c0

> 0. Now, suppose that λξ < 0; then it must be the case that Note that Equation (37) then ensures that L ≥ n2 /5000. In this case,        Y cξ Y cξ Y cξ Y cξ cr L u u u u = = ≤ max r∈ZQ : r̸=0 c0 c0 c0 c0 c0 u∈U

u : ξu ̸=0

u : ξu =0

Pn

i=1 Pi < 0.

u : ξu ̸=0

=

1 + 12 cos(2π/Q) 3/2

!L ,

where we used the expression for cr from (22), and the fact that among r ∈ ZQ , r ̸= 0, 21 cos(2πr/Q) 1+ 1 cos(2π/Q)

is maximized at r = 1 and r = Q − 1. Defining ρ := 2 3/2 Y cξ u 0< ≤ ρL . c0

< 1, we thus have that

u∈U

Recall also from (36) that every |Pi | ≤ (0.88)ℓi ≤ 1, and hence n

−1 ≤

1X Pi ≤ 1. n i=1

We thus obtain that λξ = d =⇒

Y cξ

!

u

u∈U

c0

n2 /5000

λξ ≥ −dρ

n

Y cξ 1X 2 u Pi ≥ − ≥ −ρL ≥ −ρn /5000 n c0 i=1

u∈U

.

If λξ ≥ 0, the bound above holds automatically. Thus, we have shown that every eigenvalue λξ 2 corresponding to the eigenvectors χξ is at least −dρn /5000 ; since these eigenvectors form a basis, we have shown that the minimum eigenvalue λmin of M satisfies 2

λmin ≥ −dρn /5000 . But this is precisely what we wanted to show at the end of Section 4.3 to establish Theorem 2: a 2 lower-bound of −dργn on the smallest eigenvalue of M , where 0 < ρ < 1 and γ > 0. Since the above analysis establishes this for a value of ρ satisfying 0 < ρ < 1 and γ = 1/5000, we conclude the proof of Theorem 2. Remark 1 (General Constant-gadget Lifting). It is natural to wonder if the constant-gadget lifting theorem above could apply to all Boolean functions instead of just the unambiguous DNFs from Theorem 1, similar to the all-purpose lifting theorem of Göös et al. [2016]. The goal here would be to show that the constant-sized cyclic gadget lifts any function f having 0-certificate complexity C0 (f ) to a communication problem h satisfying log Cov0 (h) ≥ Ω(C0 (f )). In our limited attempts, we were unable to extend the analysis above to derive such a general lifting theorem. In particular, the analysis above appears to crucially use the form of the DNF from Theorem 1 in defining the matrix M , and in expressing its eigenvalues in the form of elementary symmetric polynomials. 30

5

Quartic Separation between Certificate Complexity and Approximate Degree

In this section, we restate and give a complete proof of Theorem 4. Theorem 4 (Certificate Complexity vs. Approximate Degree). There exists a family of Boolean g )4 ). e deg(f functions f with C(f ) ≥ Ω( Proof. At a high level, we construct the desired function by totalizing an appropriate partial function, that can be certified with only a few, low-degree checks, through the framework of cheat sheets [Aaronson et al., 2016]. A partial function H that is hard to certify. Let f be the unambiguous DNF given by Theorem 1. Recall that we constructed a universe U = B1 ⊔ . . . Bn , where each |Bi | = n (so |U | = n2 ), and a signed set-pair system T = {(PT , NT )}T , where T = (i, S) ranges over all i ∈ [n], and S ⊆ Bi , |S| = k = ⌊n/2⌋. We had that T is pairwise incompatible, and |PT | + |NT | = O(n) for every T . The definition of f was   _ ^ ^  f (x) = xu ∧ ¬xv  . (i,S)

u∈Pi,S

v∈Ni,S

Using a construction similar to the Puzzle I =⇒ Puzzle II in Balodis et al. [2023], we now construct a partial function H from f that is hard to certify. Instead of a single Boolean variable xu for every u ∈ U , we will have two Boolean variables xu and yu for every u ∈ U , and hence H will be a partial 2 function mapping {0, 1}2n to {0, 1, ∗}. We denote x = (xu )u∈U and y = (yu )u∈U . The partial function H is defined as (W u∈PT yu if f (x) = 1, meaning that a unique term T is satisfied, H(x, y) = (42) ∗ otherwise. We now argue that it is hard to certify H not evaluating to 0 or 1. Recall that we use 0 to denote the output set {1, ∗} (i.e., “not 0”) and 1 to denote the output set {0, ∗} (i.e., “not 1”). We will argue that the all-zeros input z = (x, y) = (0|U | , 0|U | ) has large 0 and 1 certificate complexity. Namely, we show that C0 (H, z) ≥ τ (P),

C1 (H, z) ≥ τ (P),

(43)

where τ (P) = Ω(n2 ) is the hitting number of the family of positive sets PT . First, note that H(z) = ∗, since f (0|U | ) = 0. Now, let ρ ∈ {0, 1, ∗}2|U | be any partial assignment consistent with z, and satisfying |ρ| < τ (P). Let Rx = {u ∈ U : the variable xu is not set to ∗ in ρ}.

(44)

Since |Rx | ≤ |ρ| < τ (P), the set Rx is disjoint with at least one PT . For such a T , we extend ρ at the variables xu for u ∈ PT as xu = 1, and then extend all the remaining ∗ values in ρ to be 0. Observe that this results in a z ′ which is consistent with ρ, but satisfies that H(z ′ ) = 0. Thus, ρ does not certify H to be “not 0” at z, implying that C0 (H, z) ≥ τ (P). 31

For lower-bounding C1 (H, z), let ρ ∈ {0, 1, ∗}2|U | again be any partial assignment consistent with z, satisfying |ρ| < τ (P). Let Rx be defined as in (44), and further define Ry as Ry = {u ∈ U : the variable yu is not set to ∗ in ρ}.

(45)

Since |Rx ∪ Ry | ≤ |Rx | + |Ry | ≤ |ρ| < τ (P), we have that Rx ∪ Ry is disjoint with at least one PT . For such a T , we extend ρ at the variables xu for u ∈ PT as xu = 1, extend yu0 for some fixed u0 ∈ PT as yu0 = 1, and then extend any other remaining ∗ values in ρ to be 0. Observe that this results in a z ′ which is consistent with ρ, but satisfies that H(z ′ ) = 1. Thus, ρ does not certify H to be “not 1” at z, implying that C1 (H, z) ≥ τ (P). Summarily, we obtain that min {C0 (H, z), C1 (H, z)} ≥ Ω(n2 ). A low-degree verifiable certificate description for H. For the partial function H constructed above, we nevertheless show how a given input z can be verified to evaluate to either 0 or 1 by evaluating O(n)-many low-degree polynomials over a suitably encoded certificate description, and then taking the AND of these evaluations. Our high-level approach here is similar to that used in [Balodis et al., 2023, Corollary 6]. We note that it is essential that we use only O(n) many low-degree evaluations, for the purposes of obtaining our final desired quartic separation. We first concretely specify the format of a certificate description. A certificate description comprises of the following components: (1) A block index i ∈ [n], and k integers a1 < · · · < ak (these are intended to be sorted indices in a positive term Pi,S = S). (2) For every block j ∈ [n], j ̸= i (listed in increasing order of j), an index tj ∈ U , and a value ℓj ∈ [n] {i,j} (tj is intended to be an element of S, so that λi (tj ) = ℓj certifies that mi,j (S) ≤ ℓj ). (3) A list Γ comprising of a total of N = O(n) entries, where N is the maximum term-width of the DNF in Theorem 1. Each entry in the list is a pair (j, r), and the entire list is intended to comprise of (j, 1), . . . , (j, ℓj ) for every j ∈ [n], j ̸= i, listed in increasing order of j, followed possibly by padding entries. (4) An integer t⋆ ∈ [k] in the case of a 1-certificate, or a padding entry in the case of a 0-certificate (intended to indicate the variable yat⋆ that is supposed to be 1 to certify H evaluating to 1.) 2

We now specify how, given an input z ∈ {0, 1}2n to the partial function H, and a certificate description K, the verifier either rejects or accepts the certificate. The verifier first checks whether the block index i in Step (1) above belongs to [n]. Thereafter, it checks whether all the k integers a1 , . . . , ak belong to Bi , and that a1 < a2 < . . . ak . This can be done by O(n)-many decision tree evaluations, that, e.g., query i and some at to check if at ∈ Bi , or query at and at+1 to check if at < at+1 . Thereafter, the verifier checks whether xat = 1 for every t ∈ [k], and that xu = 0 for every u ∈ Bi \ {a1 , . . . , ak }. Namely, these variables correspond to the variables in Pi,S and Ni,S respectively in the block Bi . This check can be done by iterating over all u ∈ Bi , checking whether u ∈ {a1 , . . . , ak } (e.g., by a binary search), and then checking 32

xu correspondingly. In total, this entire check is an AND of O(n)-many deterministic decision tree evaluations having depth polylog(n). Next, the verifier checks that the triplets (j, tj , ℓj ) in Step (2) above are listed in increasing order {i,j} of j for j ̸= i (where i is the value read at Step (1)), tj ∈ {a1 , . . . , ak }, and λi (tj ) = ℓj . The check tj ∈ {a1 , . . . , ak } can be done efficiently with a binary search. The rest of the checks can be done, for example, by having a polylog(n) decision tree for every j, which queries i and the triplets (j − 1, tj−1 , ℓj−1 ), (j, tj , ℓj ), checks that j has increased correctly, and thereafter, checks whether {i,j} {i,j} λi (tj ) = ℓj (note that the function λi may be hard-coded in the logic of the decision tree). Therefore, this check can also be performed as the AND of O(n)-many decision tree evaluations having depth polylog(n) each. The verifier must next verify whether the list Γ in Step (3) is a faithful representation of the triplets in Step (2). Namely, for each triplet (j, tj , ℓj ), j ̸= i considered in order, the corresponding list entries should be (j, 1), . . . , (j, ℓj ). Again, this entire check can be done as a conjunction of local checks performed on pairs of consecutive list entries. For example, if we consider a pair of entries Γs , Γs+1 , for which Γs = (j, r), we want that Γs+1 = (j, r + 1) if r < ℓj , and Γs+1 = (j + 1, 1), up to the boundary cases where j = i or j = 1 or j = n, which are also appropriately handled; e.g., the verifier must check that the last pair (either (n, ℓn ) or (n−1, ℓn−1 ) if i = n) is followed by a sequence of padding entries; if this is not the case, meaning that the N list slots are too few, the verifier {i,j} rejects. At the same time, the verifier also checks that (j, r) satisfies that u = (λj )−1 (r) ∈ Bj , and that xu = 0 — this verifies that all the variables in Ni,S outside the block Bi are also set to 0. In total, we again have that this entire operation is the AND of |Γ| = O(n) many, polylog(n)-depth decision tree evaluations. Finally, the verifier reads the last component in Step (4) of the certificate description. If this is a padding entry, indicating that the certificate description is for a 0-certificate, the verifier checks that all the variables yu for u ∈ {a1 , . . . , ak } satisfy that yu = 0. If this is not a padding entry, but an integer t⋆ , indicating that the certificate description is for a 1-certificate, then the verifier checks whether yat⋆ = 1. Again, this is an AND of O(n) many, polylog(n)-depth decision tree evaluations. Combining all of the above, we obtain that the entire verification process is an AND of O(n) many deterministic decision tree evaluations having depth polylog(n). Since each polylog(n)depth decision tree evaluation can be represented exactly by a polynomial of degree polylog(n), andpthe AND function on O(n) arguments can be ε-approximated by a polynomial of degree O( n log(1/ε)) [Nisan and Szegedy, 1994], we get that the composition — a polynomial of degree √ O( n · polylog(n, 1/ε)) — ε-approximates the verification. Soundness and Completeness of Verifier. Suppose the verifier accepts a certificate description. The structural checks in Step (1) ensure that i ∈ [n], and that S = {a1 , . . . , ak } ⊆ Bi , |S| = k. They also verify that all the variables in the positive term Pi,S are set to 1, and all the variables in the negative term Ni,S within the block Bi are set to 0. Next, if the checks in Step (2) pass, this confirms that mi,j (S) ≤ ℓj for every j ̸= i. Thereafter, the check in Step (3) ensures that there is a list entry (j, r) for every j ̸= i, 1 ≤ r ≤ ℓj . Since ℓj ≥ mi,j (S), the check on the relevant variables being 0 ensure that for every j ̸= i, the variables xu for u in the set {i,j}

Ai,j (S) = {y ∈ Bj : λj

(y) ≤ mi,j (S)}

are all set to 0. Together with the checks in Step (1) above, this establishes that all the variables in the negative term Ni,S are set to 0. This confirms that the DNF f (x) evaluates to 1. Finally, the check in Step (4) ensures that, if the certificate claims to be a 0-certificate, then indeed all the variables yu for u ∈ S are set to 0, which means that H(x, y) = 0; on the other hand, if the 33

certificate claims to be a 1-certificate, then yat⋆ = 1, and hence H(x, y) = 1. Thus, every certificate description accepted by the verifier validly certifies H, establishing its soundness. Now consider any input (x, y) for which H(x, y) = 0 or H(x, y) = 1. Let (i, S) be the term for which f (x) = 1, and let S = {a1 < . . . , ak } — these constitute Step (1) of the certificate description. {i,j} For Step (2), for each j ̸= i, we set tj to be the element u ∈ Bi which P attains λi (u) = mi,j (S), and set ℓj = mi,j (S). The construction of the DNF f guarantees that j̸=i mi,j (S) ≤ N ≤ O(n), and hence all required (j, r) entries fit into the list slots in Step (3). Finally, if H(x, y) = 1, set t⋆ to be such that yat⋆ = 1. Otherwise, if H(x, y) = 0, then every yu for u ∈ S is equal to 0. Thus, all the checks of the verifier pass, and the verifier accepts correctly, establishing the completeness of the verifier. Total function via cheat-sheet. We now use the cheat sheet mechanism due to Aaronson et al. [2016] which was also used in Balodis et al. [2023], in order to build a total function G from several copies of the partial function H, such that the 0-certificate complexity of the total function is large. Towards this, let L = 2r , where L > τ (P) but L = Θ(n2 ). An input to the total function G comprises: 1. r separate inputs z (1) , . . . , z (r) to H. 2. An array of L cells, each indexed by c ∈ {0, 1}r . Each cell comprises r certificate descriptions, one for each input to H above. We say that a cell c = (c1 , . . . , cr ) is valid for the inputs z (1) , . . . , z (r) , if for every a ∈ [r], the ath certificate description is accepted by the verifier as a ca -certificate for z (a) . Then, the total function G evaluates to 1 iff at least one cell c is valid for the inputs z (1) , . . . , z (r) , and 0 otherwise. Note that the function is total since it is defined for all inputs. Moreover, observe also that at most one cell can ever be valid for any inputs z (1) , . . . , z (r) . Otherwise, if there were two distinct cells c and d that were both valid, where ca ̸= da , then by the soundness of the verifier, H(z (a) ) would simultaneously be certified to be both 0 and 1, which is a contradiction. Lower-bounding C(G). Consider the input Z0 to G, where each of the r inputs to H are equal to (0|U | , 0|U | ), and all of the array bits are 0. Since H(z (a) ) = ∗ for every a, none of the cells are valid for the inputs, and thus G(Z0 ) = 0. We will now argue that Z0 has large 0-certificate complexity, namely C0 (G, Z0 ) ≥ τ (P) = Ω(n2 ). Towards this, let ρ be any partial assignment consistent with Z0 , and satisfying that |ρ| < τ (P). Because L > τ (P), there is at least one cell c such that every entry in ρ within the cell c is equal to ∗. Now consider any a ∈ [r], and let ρa be the restriction of ρ to the ath input z (a) . Since |ρa | ≤ |ρ| < τ (P), from the lower bound (43) for the partial function H above, we have that: • If ca = 0, then ρa is not a 0-certificate for z (a) , meaning that there is an extension za′ of ρa for which H(za′ ) = 0. • If ca = 1, then ρa is not a 1-certificate for z (a) , meaning that there is an extension za′ of ρa for which H(za′ ) = 1.

34

Extend ρa for every a ∈ [r] as above. By the completeness of the certificate description, there is then a valid certificate description certifying that H(za′ ) evaluates to ca for every a, which is accepted by the verifier. Since every entry within the cell c was ∗, we can fill the cell with all these r valid certificate descriptions. We then extend all the other remaining ∗ entries in ρ arbitrarily. We have thus extended ρ to an input Z1 consistent with ρ, for which cell c is valid, and hence G(Z1 ) = 1. Thus, ρ was not originally a 0-certificate for G at Z0 , giving that C(G) ≥ C0 (G, Z0 ) ≥ Ω(n2 ).

(46)

g Upper-bounding deg(G). We will now show that G has small approximate degree. For any cell r c ∈ {0, 1} , define Gc = 1 iff cell c is valid. Then, we have that _ Gc , G= c∈{0,1}r

and as argued above, this OR is unambiguous: at most one Gc can ever be 1. Now fix cell c. To evaluate Gc , i.e., verify if cell c is valid, we must verify r = O(log n) certificate descriptions. As shown above, each such verification is an AND over O(n) many decision tree evaluations of depth polylog(n); in total, the evaluation of Gc is an AND over O(n log n) many decision tree evaluations of depth polylog(n), and can hence be ε-approximated by a polynomial √ of degree at most O( n · polylog(n, 1/ε)). Now choose ε = 1/(3L); since L = Θ(n2 ), we get that e √n) such that there is a polynomial pc of degree O( |pc − Gc | ≤ 1/(3L) on all inputs. Then, define the polynomial p=

X

pc .

c∈{0,1}r

e √n). But now, observe that if G = 0, then every Gc = 0, and so The degree of p is still O( X X |p − G| = |p| ≤ |pc | = |pc − Gc | ≤ L · 1/(3L) = 1/3. c∈{0,1}r

c∈{0,1}r

On the other hand, if G = 1, then exactly one Gc = 1, and every other Gc = 0. Thus, |p − G| = |p − 1| =

X

(pc − Gc ) ≤

X

|pc − Gc | ≤ L · 1/(3L) = 1/3.

c∈{0,1}r

c∈{0,1}r

We therefore have that p 1/3-approximates G, meaning that √ g (G) = deg(G) g e n). deg ≤ O( 1/3 Concluding the quartic separation.

We have thus constructed a total function G for which √ g e n). C(G) ≥ Ω(n2 ), deg(G) ≤ O(

Thus, G enjoys the desired quartic separation 4 g e deg(G) C(G) ≥ Ω( ).

35

6

Lower Bound for Multiclass Sample Compression

In this section, we restate and prove the lower bound on sample compression schemes for multiclass concept classes. For a formal definition of a sample compression scheme, we refer the reader to Definition 6 in Pabbaraju [2024]. Theorem 5 (Sample Compression Lower Bound for Multiclass Concept Classes). 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 . Proof. We will show: for infinitely many n, there exists a multiclass concept class C that uses at 2 most 2O(n ) labels and has Natarajan dimension 1, such that any sample compression scheme for C must have size at least Ω(n). The theorem statement then follows by reparameterizing. Our proof is largely based on the sample compression lower bound for multiclass concept classes shown in Pabbaraju [2024]; we refer the reader to that proof, while giving the necessary details below. 2 Choose an n for which Theorem 3 holds: namely, there exists a graph G = (V, E) having 2Θ(n ) 2 vertices that admits a biclique partition of size 2O(n) but has chromatic number 2Ω(n ) . Fix a partition of G into at most 2O(n) bicliques. The domain X of the partial concept class P is the set of bicliques in this partition. Note that each biclique is determined by a set L of left vertices and a set R of right vertices, such that every vertex in L is connected to every vertex in R. Now, for each vertex v in G, we will have a partial concept pv , which maps a biclique Q = (L, R) in the partition as follows:   0 if v ∈ L, pv (Q) = 1 if v ∈ R,   ∗ otherwise. This partial class was shown by Alon et al. [2022] to have VC dimension 1. Now consider the following total concept class C: for every pv ∈ P, the class C has cv which maps any biclique Q as ( pv (Q) if pv (Q) ̸= ∗, cv (Q) = v otherwise. By construction, C disambiguates P (i.e., for every pv ∈ P, there is a total concept cv ∈ C consistent with pv ); furthermore, observe that it uses at most |V | + 2 labels. Pabbaraju [2024] shows that the class C has DS dimension 1, and since the Natarajan dimension is never larger than the DS dimension, its Natarajan dimension is also 1. Now let (κ, ρ) be any sample compression scheme for C of size k. Since C disambiguates P, (κ, ρ) is also a sample compression scheme for P. Notably, this means that the support of any partial concept pv (i.e., the domain points at which it is not ∗, but either 0 or 1) gets compressed by κ to a subsequence of size at most k, and applying the reconstructor ρ to this compressed subsequence recovers all the labels correctly on the support, meaning also that the reconstructor output disambiguates pv . This means that, if we were to iterate over all possible subsequences of the domain, all possible labelings of the subsequence by a concept in P, all possible side-information strings of size at most k, and collect the total concepts output by the reconstructor on all of these, then the resulting total concept class would disambiguate P. The number of reconstructor outputs we need to consider is at most |X |O(k) · 2k · 2k = 2O(kn) . 36

But Alon et al. [2022] also show that any disambiguating class for P determines a valid coloring of the vertices in G using a number of colors equal to the size of the disambiguating class. Since the 2 chromatic number of G is at least 2Ω(n ) , we thus have that 2

2O(kn) ≥ 2Ω(n ) =⇒ k ≥ Ω(n).

Acknowledgements Various ideas used in the paper were individually developed over numerous lengthy rounds of interaction with ChatGPT and Codex. This work is supported by Moses Charikar’s and Greg Valiant’s Simons Investigator Awards, and a Google PhD Fellowship. I would like to thank Greg Valiant for encouraging me to think about multiclass sample compression again.

References Scott Aaronson, Shalev Ben-David, and Robin Kothari. Separations in query complexity using cheat sheets. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 863–876, 2016. 2, 5, 5 Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal. Degree vs. approximate degree and quantum implications of huang’s sensitivity theorem. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1330–1342, 2021. 1.3, 1.3, 1.3 Yaroslav Alekseev, Yuval Filmus, and Alexander V Smal. Lifting dichotomies. computational complexity, 34(2):18, 2025. 1.2 Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of pac learnability of partial concept classes. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 658–671. IEEE, 2022. 1.4, 6 Kazuyuki Amano. Some improved bounds on communication complexity via new decomposition of cliques. Discrete Applied Mathematics, 166:249–254, 2014. 1.2 Anurag Anshu, Shalev Ben-David, and Srijita Kundu. On query-to-communication lifting for adversary bounds. arXiv preprint arXiv:2012.03415, 2020. 2 Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, and Robin Kothari. Unambiguous dnfs and alon–saks–seymour. SIAM Journal on Computing, pages FOCS21–157, 2023. 1, 1, 1, 1, 1, 1, 1, 1, 1.1, 1.1, 1.2, 1.2, 1.2, 1.3, 1.3, 1.3, 2, 5, 5, 5 Shalev Ben-David, Pooya Hatami, and Avishay Tal. Low-sensitivity functions from unambiguous certificates. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), pages 28–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2017. 1.2, 1.2, C Nicolas Bousquet, Aurélie Lagoutte, and Stéphan Thomassé. Clique versus independent set. European Journal of Combinatorics, 40:73–92, 2014. 1.2

37

Tsun-Ming Cheung, Hamed Hatami, Pooya Hatami, and Kaave Hosseini. Online learning and disambiguations of partial concept classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 42–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023. 1, 1.2, 1, 1.2, 1.2, 2, B Jacob Fox. A note on the alon-saks-seymour problem. arXiv preprint arXiv:2605.28915, 2026. 1.2, 1.2 Z. Gao, B. D. McKay, R. Naserasr, and B. Stevens. Bipartite edge partitions and the former Alon–Saks–Seymour conjecture. Australasian Journal of Combinatorics, 66:211–228, 2016. 1.2 Mika Göös. Lower bounds for clique vs. independent set. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1066–1076. IEEE, 2015. 1, 1.1, 1.2, 1.2 Mika Göös and Siddhartha Jain. arXiv:2208.00029, 2022. 2

Communication complexity of collision.

arXiv preprint

Mika Göös and Toniann Pitassi. Communication lower bounds via critical block sensitivity. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 847–856, 2014. 2 Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. SIAM Journal on Computing, 45(5):1835–1869, 2016. 1.2, 1 Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. SIAM Journal on Computing, 47(6):2435–2450, 2018. 1.2, 4 Hao Huang and Benny Sudakov. A counterexample to the alon-saks-seymour conjecture and related problems. Combinatorica, 32(2):205–219, 2012. 1.2, 1.2 Jeff Kahn. Recent results on some not-so-recent hypergraph matching and covering problems. Tech report 91-14, DIMACS, Rutgers University, 1991. 1, 1.2 Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju, and Clement Svendsen. The sample complexity of replicable realizable pac learning. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, pages 2064–2070, 2026. 2, 3 Nick Littlestone and Manfred Warmuth. Relating data compression and learnability. 1986. 1.4 Dhruv Mubayi and Sundar Vishwanathan. Bipartite coverings and the chromatic number. the electronic journal of combinatorics, pages N34–N34, 2009. 1.2, 1.2 Balas K Natarajan. On learning sets and functions. Machine Learning, 4:67–97, 1989. 1.4 Bogdan Nica. A brief introduction to spectral graph theory, volume 3. European Mathematical Society Zürich, 2018. doi: 10.4171/188. 2 Noam Nisan and Mario Szegedy. On the degree of boolean functions as real polynomials. Computational complexity, 4(4):301–313, 1994. 2, 5 Chirag Pabbaraju. Multiclass learnability does not imply sample compression. In International Conference on Algorithmic Learning Theory, pages 930–944. PMLR, 2024. 1.4, 1.4, 2, 6, 6

38

Alexander A Sherstov. The pattern matrix method. SIAM J. Comput., 40(arXiv: 0906.4291): 1969–2000, 2011. 2 Manami Shigeta and Kazuyuki Amano. Ordered biclique partitions and communication complexity problems. Discrete Applied Mathematics, 184:248–252, 2015. 1.2 Luca Trevisan. CS359G: Graph Partitioning and Expanders Lecture 6. stanford.edu/~trevisan/cs359g/lecture06.pdf, 2011. 2

https://theory.

Mihalis Yannakakis. Expressing combinatorial optimization problems by linear programs. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 223–228, 1988. 1, 1.2

A

Optimality of Corollaries 1.1 and 1.2

We give direct upper bounds showing that the separations in Corollary 1.1 and Corollary 1.2 are optimal up to constant factors. Claim A.1. For any partial function f and for any x ∈ f −1 (∗), it holds that min {C0 (f, x), C1 (f, x)} ≤ C(f )2 . Proof. Fix f , and any x ∈ f −1 (∗). Let k := C(f ). For every 0-input to f , choose a 0-certificate of size at most k, and let C0 be the resulting collection of all the 0-certificates. Similarly, for every 1-input to f , choose a 1-certificate of size at most k, and let C1 be the resulting collection of all the 1-certificates. For any certificate ρ, define its disagreement set with x as Dx (ρ) := {i ∈ dom(ρ) : ρi ̸= xi }. Since f (x) = ∗, it must be the case that Dx (ρ) ̸= ∅ for every ρ ∈ C0 ∪ C1 . Now, let τ be a certificate that is consistent with x, for which dom(τ ) intersects every Dx (ρ) for ρ ∈ C0 . Then, observe that τ is a 0-certificate for x. Otherwise, there would be an extension of τ , that is consistent with τ , and is a 0-input to f , which means it should be consistent with its 0-certificate in C0 . But since τ is inconsistent with every ρ ∈ C0 , this is a contradiction. By a similar argument, we have that any β that is consistent with x, and for which dom(β) intersects every Dx (σ) for σ ∈ C1 is a 1-certificate for x. So, consider the family of sets D0 := {Dx (ρ) : ρ ∈ C0 },

D1 := {Dx (σ) : σ ∈ C1 }.

Suppose that the size of the largest subfamily of D0 of pairwise disjoint sets, i.e., the matching number of D0 , is at most k, and consider any maximal subfamily comprising of Dx (ρ1 ), . . . , Dx (ρt ) of pairwise disjoint sets, where t ≤ k. This means that the union Dx (ρ1 ) ∪ · · · ∪ Dx (ρt ) hits every member of D0 ; its size is at most tk ≤ k 2 . Thus, in this case, C0 (f, x) ≤ k 2 . 39

In the other case, there exist k + 1 sets Dx (ρ1 ), . . . , Dx (ρk+1 ) that are pairwise disjoint, where every ρi ∈ C0 . Let T be defined as T :=

k+1 [

dom(ρj ) \ Dx (ρj ).

j=1

Since dom(ρj ) has size at most k, and every Dx (ρj ) is non-empty, we have that |dom(ρj ) \ Dx (ρj )| ≤ k − 1. Thus, |T | ≤ (k + 1)(k − 1) = k 2 − 1. We now claim that T hits every member of D1 . Suppose not, meaning that for some σ ∈ C1 , T ∩ Dx (σ) = ∅. Now, each ρj is a 0-certificate for f , whereas σ is a 1-certificate for f ; thus, every ρj must be inconsistent with σ. However, ρj and σ cannot disagree at a coordinate in dom(ρj ) \ Dx (ρj ), since these are the coordinates at which ρj agrees with x, and hence, if σ disagrees with a coordinate within this set, it would disagree with x at that coordinate, contradicting that T ∩ Dx (σ) = ∅. Thus, every ρj has a disagreement with σ within Dx (ρj ). But the sets Dx (ρ1 ), . . . , Dx (ρk+1 ) are pairwise disjoint. So, σ having a disagreement within each of these sets would in particular imply that |σ| ≥ k+1, which contradicts |σ| ≤ k. We conclude that T hits every member of D1 , which implies C1 (f, x) ≤ k 2 − 1. Combining the two cases above, we obtain min {C0 (f, x), C1 (f, x)} ≤ k 2 , and the claim follows by recalling that k = C(f ). Claim A.2. For any intersecting hypergraph G = (V, E) and for any coloring c : V → {0, 1}, there exists a c-monochromatic hitting set that has size at most r(G)2 . Proof. Let G = (V, E) be any intersecting hypergraph having rank r(G), and let c : V → {0, 1} be any coloring of its vertices. We will show that there is either a 0-monochromatic or 1-monochromatic hitting set of size at most r(G)2 . First, observe that if any edge is monochromatic, we are done, since the hypergraph is intersecting, which implies that the edge itself is a monochromatic hitting set of size at most r(G). So, let us assume that every edge contains at least one 0-vertex and one 1-vertex. For each edge e, let A(e) comprise the 0-vertices, and B(e) comprise the 1-vertices in e. Consider the family of sets A := {A(e) : e ∈ E}. Note that every set in A is non-empty, and has size at most r(G) − 1. Let ν(A) be the matching number of A, i.e., the largest number of pairwise disjoint members in A. There are two cases: 40

Case 1: ν(A) ≤ r(G). Let A(e1 ), . . . , A(et ) be a maximal subfamily of A that is pairwise disjoint, where t ≤ r(G). By maximality, it holds that the union U0 = A(e1 ) ∪ · · · ∪ A(et ) hits every member of A. We thus have that U0 is a 0-monochromatic set of size at most t · r(G) ≤ r(G)2 that hits every edge in the hypergraph. Case 2: ν(A) > r(G).

Let A(e1 ), . . . , A(er(G)+1 ) be pairwise disjoint. Consider the set U1 = B(e1 ) ∪ · · · ∪ B(er(G)+1 ).

Again, every |B(ei )| ≤ r(G) − 1, and hence |U1 | ≤ (r(G) + 1)(r(G) − 1) = r(G)2 − 1. We now claim that U1 hits every edge in E. Suppose not, meaning that for some edge f , U1 ∩ f = ∅. Since G is intersecting, f has non-empty intersection with every ei . But since f ∩ U1 = ∅, it must be the case that for every i, ∅ ̸= f ∩ ei ⊆ A(ei ). Since A(e1 ), . . . , A(er(G)+1 ) are pairwise disjoint, we obtain that f contains at least r(G)+1 vertices, contradicting that |f | ≤ r(G). Thus, U1 is a 1-monochromatic set that hits every edge in the hypergraph. Combining the two cases, we have shown that G always contains a c-monochromatic hitting set of size at most r(G)2 .

B

Proof of Theorem 3

We restate and give the necessary proof details of Theorem 3. Theorem 3 (Optimal Refutation of Alon-Saks-Seymour). For infinitely many n, there exists a 2 graph G having 2Θ(n ) vertices that admits a biclique partition of size 2O(n) but has chromatic 2 number 2Ω(n ) . Consequently, there exists an infinite family of graphs G satisfying

χ(G) ≥ exp Ω log2 (bp(G)) . (5) Proof. We first use our lifting theorem to lift the unambiguous DNF separation of Theorem 1 to a separation in communication complexity. Namely, Theorem 2 gives a gadget g : {0, 1}3 × {0, 1}3 → 2 2 2 {0, 1} such that the communication problem f ◦ g n : {0, 1}3n × {0, 1}3n → {0, 1} obtained by lifting the DNF from Theorem 1 with the gadget g satisfies 2

log Cov0 (f ◦ g n ) ≥ Ω(n2 ). Furthermore, it holds that 2

log Par1 (f ◦ g n ) ≤ O(UC1 (f )), since for any n-variate function f and any k-sized gadget, it holds that log Par1 (f ◦ g n ) ≤ O(k · 2 2 UC1 (f )). Combining the two bounds, we obtain a function h : {0, 1}Θ(n ) × {0, 1}Θ(n ) → {0, 1} for which log Cov0 (h) ≥ Ω(n2 ),

log Par1 (h) ≤ O(n).

We can now directly apply Lemma 3.5 from Cheung et al. [2023] to the function h, which converts 2 h into a graph G having 2Θ(n ) vertices, and satisfying p 2 bp(G) ≤ Par1 (h)2 ≤ 2O(n) , χ(G) ≥ Cov0 (h) ≥ 2Ω(n ) .

41

C

Proof of Corollary 1.5

We restate and give the necessary proof details for Corollary 1.5. Corollary 1.5 (Certificate Complexity vs. Sensitivity). There exists a family of Boolean functions f with C(f ) ≥ Ω(s(f )3 ). Proof. The proof is essentially contained in the proofs of Lemma 12 and Theorem 1 in Ben-David et al. [2017]; we flesh out the main steps here. Let f be the unambiguous DNF from Theorem 1, for which C0 (f ) ≥ Ω(n2 ),

UC1 (f ) ≤ O(n).

In fact, since C0 (f ) ≤ UC1 (f )2 always, we have that UC1 (f ) = Θ(n). Let u := UC1 (f ); we have that u = Θ(n). Now, we apply the desensitizing transformation introduced in Definition 11 in Ben-David et al. 2 [2017] to f . Namely, consider the function f ′ : {0, 1}3n → {0, 1}, which takes three inputs 2 x, y, z ∈ {0, 1}n and outputs f ′ (x, y, z) = 1 iff f (x) = f (y) = f (z) = 1 and the unique term that evaluates to 1 is the same for x, y and z. Lemma 12 in Ben-David et al. [2017] shows that C0 (f ′ ) ≥ C0 (f ). Now define the function F := OR3u ◦ f ′ , i.e., F takes 3u inputs to f ′ and outputs their OR. Ben-David et al. [2017] show (in the proof of their Theorem 1) that s(F ) ≤ 3u.

(47)

Now consider the 0-certificate complexity of F . To certify that F = 0, one must certify that each of the 3u evaluations of f ′ is 0. Thus, C0 (F ) = 3u · C0 (f ′ ) ≥ 3u · C0 (f ) = Ω(u3 ). Combining (47) and (48), we get that C0 (F ) ≥ Ω(s(F )3 ). This completes the proof.

42

(48)

Related documents

• Robust Mechanism Design on Networks with Externalities#1130749
• Almost Optimal FPT Inapproximability for k-SetCover#1014273
• A note on the partition bound for one-way classical communication complexity#974136
• Dispositifs optoélectroniques avec des teneurs en In et Ga réduites#288199
• Smarandache recursive arithmetic structures: Conjectures, open problems, and computational explorations#691366