Lifting with Colourful Sunflowers

de Rezende, Susanna F.; Vinyals, Marc

doi:10.4230/LIPIcs.CCC.2025.36

Lifting with Colourful Sunflowers

Susanna F. de Rezende

Lund University, Sweden Marc Vinyals

University of Auckland, New Zealand

Abstract

We show that a generalization of the DAG-like query-to-communication lifting theorem, when proven using sunflowers over non-binary alphabets, yields lower bounds on the monotone circuit complexity and proof complexity of natural functions and formulas that are better than previously known results obtained using the approximation method. These include an $n^{\Omega(k)}$ lower bound for the clique function up to $k\leq n^{1/2-\epsilon}$ , and an $\exp(\Omega(n^{1/3-\epsilon}))$ lower bound for a function in P.

Keywords and phrases:

lifting, sunflower, clique, colouring, monotone circuit, cutting planes

Funding:

Susanna F. de Rezende: Supported by Knut and Alice Wallenberg grants KAW 2018.0371 and KAW 2021.0307, ELLIIT, and the Swedish Research Council grant 2021-05104.

Marc Vinyals: Supported by the Marsden Fund Council from Government funding, managed by Royal Society Te Apārangi.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Communication complexity ; Theory of computation

\rightarrow

Proof complexity ; Theory of computation

\rightarrow

Circuit complexity

Acknowledgements:

We are grateful to Lukáš Folwarczný who contributed to early stages of the work, to Bruno Pasqualotto Cavalar for dicussions on the topic, and to Noah Fleming, Duri Andrea Janett, Jakob Nordström, and Shuo Pang for allowing us to include parts of their lifting theorem in the full version of this article.

DOI:

10.4230/LIPIcs.CCC.2025.36

Event:

40th Computational Complexity Conference (CCC 2025)

Editors:

Srikanth Srinivasan

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

In 1985, Razborov [44] proved the first superpolynomial size lower bound for monotone Boolean circuits for a monotone function in NP, and, independently, Andreev [4] obtained exponential size lower bounds. Razborov’s result was for the perfect matching and the clique functions, and shortly after, Alon and Boppana [1] improved the lower bound for clique to exponential. These lower bounds introduced the so-called approximation method, which consists of showing that every gate computes a function close to a class of functions that cannot distinguish between the expected answers. The interpretation of close becomes looser in gates further away from the inputs. The classical combinatorial sunflower lemma is used to ensure that the class of functions computed by gates increases slowly, and therefore only contains the expected output function once the circuit size surpasses the bound we are set to prove.

The approximation method also found great success in proof complexity, after Krajíček [35, 36] introduced interpolation to proof complexity and Pudlák [40] showed it could be used to prove cutting planes lower bounds from lower bounds to a generalisation of monotone circuits called monotone real circuits. For a long time the only known method for proving lower bounds for monotone circuits and for cutting planes was via approximation method. Other methods like bottleneck counting were later shown to be equivalent to the approximation method for monotone circuits [48, 11, 33]. In contrast, lower bounds for proof systems such as resolution and polynomial calculus can be readily obtained from measuring width and degree respectively.

Not long after the approximation method was introduced, new and very influential techniques were developed to prove lower bounds for monotone formulas and later extended to capture tree-like cutting planes. Karchmer and Wigderson [34] proved superpolynomial formula size lower bounds for connectivity by establishing a relation between communication complexity and monotone circuit depth. Raz and McKenzie [43] introduced a new technique, now called lifting theorems, for obtaining communication lower bounds from query complexity lower bounds, and obtained separations between mon-NC and mon-P, and between levels of the mon-NC hierarchy. Their result was extended [12] to obtain lower bounds on the size of tree-like cutting planes proofs.

A decade ago, Göös, Pitassi, and Watson [24] brought to light the generality of the result of Raz and McKenzie [43] and reignited this line of work. A notable extension is the lifting theorem [22] for a model of DAG-like communication [45, 49] that corresponds to circuit size. These theorems, in their different flavours, have been instrumental in addressing many open questions in monotone circuit complexity, including: optimal $2^{\Omega(n)}$ lower bounds on the size of monotone Boolean formulas computing an explicit function in NP [39]; a complete picture of the relation between the mon-AC and mon-NC hierarchies [20]; a near optimal separation between monotone circuit and monotone formula size [19]; and an exponential separation between ${\text{NC}}^{2}$ and mon-P [22, 26].

One criticism to the lifting technique is that the lower bounds obtained are for artificial functions and formulas. This is because the lower bounds are not for the same function whose query complexity is high, but for the composition of two functions. This criticism applies to most lower bounds obtained via lifting discussed above. Nevertheless, we can obtain lower bounds for natural functions and formulas if we can reduce them to their lifted counterparts. Furthermore, we can carry the reduction already within the communication complexity model, which is easier than reducing between circuits or proofs. This idea appears already in Raz and McKenzie’s work [43], where they lift the collision-finding relation – equivalent to the pigeonhole principle – and subsequently apply a reduction to obtain a depth lower bound for clique. More recent results in circuit complexity also combine lifting and reductions [38, 46, 18] (see also [17]), as do results in proof complexity [32]. Another issue is that bounds obtained through lifting are often weaker than those obtained through more direct means, because generally composition increases the size of a function more than its complexity. The question of minimising the overhead due to lifting is recurring in the area.

Following on the topic of the strength of lower bounds, it is very natural to ask how well these match the corresponding upper bounds, and to aim for truly exponential lower bounds of the form $\exp(\Omega(n))$ rather than only $\exp(n^{\Omega(1)})$ . Razborov’s result [44] is for two monotone functions on graphs: $n^{\Omega(\log n)}$ lower bound for perfect matching and $n^{\Omega(k)}$ lower bound for $k$ -clique, for $k\leq\log n$ . Shortly after, Alon and Boppana [1, 53] extended the result on clique to $n^{\Omega(k^{1/2})}$ for $k\leq n^{2/3-\epsilon}$ , and Amano and Maruoka [3] provided lower-order improvements. More recently, Cavalar et al. [15] showed a stronger result of $n^{\Omega(k)}$ for $k\leq n^{1/3-\epsilon}$ .

Besides clique, if we consider lower bounds on any function in NP, Andreev [4] proved exponential lower bounds of the form $\exp(\Omega(n^{1/8}))$ . Alon and Boppana [1], Andreev [5], and Harnik and Raz [28] successively improved the bound to $\exp(\Omega(n^{1/3-\epsilon}))$ , and also recently Cavalar et al. [15] proved a lower bound of the form $\exp(\Omega(n^{1/2-\epsilon}))$ .

It is also of significant interest to prove lower bounds for functions in P, showing that monotone circuits are weaker than circuits with negations. The first such separation is Razborov’s superpolynomial bound on the matching function, and Tardos [52] proved the first exponential separation of the form $\exp(\Omega(n^{1/6}))$ . This latter result follows from the exponential lower bound for the clique–colouring function [1] and an upper bound Tardos proved for a monotone function extending clique–colouring. The more recent lower bounds of Harnik and Raz and Cavalar et al. apply to functions that are not known to be in P.

The breakthrough that allowed Cavalar et al. to prove lower bounds beyond $\exp(n^{1/3})$ was the robust sunflower lemma [47, 42, 2]. This improved sunflower lemma was also used to improve the parameters in the lifting theorem [37]. Indeed, the lifting overhead was reduced to the point that bounds obtainable by lifting could match those obtained via the approximation method. However, to our knowledge, this has not been applied to get better bounds in circuit or proof complexity.

1.1 Our results

In this paper we go one step further and use lifting to prove even better lower bounds than those currently known using the approximation method. We do so by generalising the lifting theorem to non-binary alphabets, using what we call colourful sunflowers (simply sunflowers over a larger alphabet). This allows us to obtain smaller lifted problems than what we would through a binary alphabet. We then reduce this lifted problem to the clique–colouring and related functions. This gives us better lower bounds on the size of monotone circuits and cutting planes proofs.

Clique–colouring

We begin with the monotone circuit complexity of the clique function, which distinguishes graphs containing a $k$ -clique from graphs that do not. In fact we consider the clique–colouring partial function, which distinguishes $n$ -vertex graphs containing a $k$ -clique from graphs that are $c$ -colourable, for $c<k$ . Since the clique function extends the clique–colouring function, it is at least as hard to compute.

The best lower bound to date for the clique–colouring function was $n^{\Omega(k^{1/2})}$ for $k\leq n^{2/3-\epsilon}$ .

Theorem 1 ([1]).

Given $c,k,n\in\mathbb{N}$ satisfying $c<k$ , $\sqrt{c}k\leq n/(8\log n)$ , it holds that any monotone Boolean circuit computing $(\mathrm{clique}_{k}\text{-}\mathrm{col}_{c})_{n}$ must have size

\left(\frac{n}{\sqrt{c}k\log n}\right)^{\Omega\left(\sqrt{c}\right)}\,.

(1)

A better $n^{\Omega(k)}$ bound for $k\leq n^{1/3-\epsilon}$ was also known for the clique function, but not for the clique–colouring function.

Theorem 2 ([15]).

Given $k,n\in\mathbb{N}$ satisfying $k\leq n^{1/3-\epsilon}$ , it holds that any monotone Boolean circuit computing $k$ -clique must have size

\left(\frac{n}{k^{3}}\right)^{\Omega\left(k\right)}\,.

(2)

We obtain a $n^{\Omega(k)}$ bound for $k\leq n^{1/2-\epsilon}$ for the clique–colouring function, improving on both results

Theorem 3 (Clique-colouring).

There exists a universal constant $A$ such that given any $c,k,n\in\mathbb{N}$ satisfying $c<k\leq n$ , it holds that any monotone Boolean circuit computing $(\mathrm{clique}_{k}\text{-}\mathrm{col}_{c})_{n}$ must have size

\left(\frac{n}{A\cdot kc\log k\log n}\right)^{\Omega\left({c}\right)}\,.

(3)

If we assume $c=\epsilon k$ for a constant $\epsilon>0$ , then we can get a slightly better lower bound: any monotone Boolean circuit computing $(\mathrm{clique}_{k}\text{-}\mathrm{col}_{\epsilon k})_{n}$ must have size

\left(\frac{n}{A\cdot k^{2}\log n}\right)^{\Omega\left({k}\right)}\,.

(4)

Note that we get tight $n^{\Omega(c)}$ lower bound even for large gap, that is, for any $k=n^{1-\delta}$ and $c\in[\log n,n^{\epsilon}]$ , for any constants $\epsilon<\delta$ . Even if $k=n/(\log^{4}n)$ and $c=\log n$ , we obtain a superpolynomial lower bound. Finally, observe that the largest lower bound we can get is $\exp(\Omega((n/\log n)^{1/2}))$ , where we recall that $n$ is the number of vertices in the input graph, and the number of variables in the function is $\Theta(n^{2})$ .

Colouring–cocolouring

Since a partition of a graph into $n/k$ cliques contains a clique of size at least $k$ , an even more specific task than clique–colouring is distinguishing $q$ -colourable graphs from $q$ -purely-cocolourable graphs. We state the result in terms of monotone real circuits, since that is needed to prove cutting planes lower bounds.

Theorem 4 ([30]).

For $n>q^{2}$ , every monotone function that distinguishes $n$ -vertex graphs $G$ with $\chi(G)\leq q$ from graphs with $\chi(\overline{G})\leq q$ has monotone real circuit complexity $2^{\Omega(q^{1/4})}$ .

We get a stronger lower bound, but only for $n=q^{2}+1$ .

Theorem 5 (Colouring-cocolouring).

Every monotone function that distinguishes $(q^{2}+1)$ -vertex graphs $G$ with $\chi(G)\leq q$ from graphs with $\chi(\overline{G})\leq q$ has monotone real circuit complexity $2^{\Omega((q/\log q)^{1/2})}$ .

We believe this result is not tight and that there should be a lower bound of $2^{q}$ . We can, however, get a tight lower bound in a non-balanced parameter regime.

Theorem 6.

For $c\leq n^{1/3-\epsilon}$ , every monotone function that distinguishes $n$ -vertex graphs $G$ with $\chi(G)\leq c$ from graphs with $\chi(\overline{G})\leq n/c-1$ has monotone real circuit complexity $n^{\Omega(c)}$ .

Bit pigeonhole principle

Turning to proof complexity, we consider the complexity of refuting the bit pigeonhole principle in the cutting planes proof system, where proofs manipulate linear inequalities. The bit pigeonhole principle formula $\mathrm{bitPHP}^{M}_{N}$ for $M>N$ falsely asserts that there are $M$ distinct binary strings of length $\log N$ . If $M\geq 2N$ , we refer to this formula as a weak bit pigeonhole principle formula. Hrubeš and Pudlák [30] provided the first cutting planes lower bound for $\mathrm{bitPHP}$ , which prior to this work was the best bound known for pigeonhole principle. Note that their result works also for the weak version.

Theorem 7 ([30]).

Every cutting planes refutation of the weak bit pigeonhole principle $\mathrm{bitPHP}^{M}_{N}$ , $M>N$ , has size $2^{\Omega(N^{1/8})}$ .

Our result is only for the bit pigeonhole principle (not weak), but we obtain a better bound.

Theorem 8 (Bit pigeonhole principle).

Every cutting planes refutation of the bit pigeonhole principle $\mathrm{bitPHP}^{N+1}_{N}$ has size $2^{\Omega((N/\log N)^{1/3})}$ .

Stronger lower bounds on the size of refutations of the (not weak) bit pigeonhole principle of the form $2^{n^{1-o(1)}}$ are known for the tree-like restriction of the cutting planes proof system [32, 7].

Separation between monotone and non-monotone Boolean circuits

We also obtain the best known separation between monotone Boolean circuits and non-monotone Boolean circuits.

Theorem 9 ([1, 52]).

There exists a monotone function $f\in{\text{P}}$ such that any monotone circuit computing $f$ is of size at least $\exp(\Omega(n^{1/6-\epsilon}))$ .

Using the result of [52] that there exists a total monotone function in P that extends the partial clique-colouring function and our lower bound for the clique-colouring, we immediately obtain that there exists a monotone function $f\in{\text{P}}$ over $n$ variables such that any monotone circuit computing $f$ is of size at least $\exp(\Omega(n^{1/4-o(1)}))$ . We can, furthermore, obtain an even better separation by considering a function $f$ obtained by restricting most of the edges of the input graph. By doing this, the lower bound for clique-colouring still applies, but the number of variables is reduced considerably and we get the following result.

Theorem 10 (Monotone vs non-monotone).

There exists a monotone function $f\in{\text{P}}$ such that any monotone circuit computing $f$ is of size at least $\exp(\Omega(n^{1/3-o(1)}))$ .

1.2 Technical contribution

The main technical contribution is to show that we can obtain better parameters by proving a generalised lifting theorem over large alphabets. We prove the lifting theorem following the same high-level structure as many others before. The proof consists of two key lemmas, a full range lemma and a triangle lemma, and a simulation procedure that relies on these two lemmas. The triangle lemma and the simulation procedure only change minimally, and the full range lemma follows from the sunflower lemma after adapting the probability distributions appropriately.

Once the lifting theorem is in place, we define a $2$ -CSP version of the graph pigeonhole principle. That is, we encode that $k$ elements can be coloured with $c<k$ colours without repetitions, each element having a pool of constantly many available colours. We show how clique–colouring reduces to this lifted CSP using a similar reduction to previous works [43, 18].

It is immediate that colouring-cocolouring reduces to clique-colouring. We show a reduction in the other direction which gives us lower bounds for colouring-cocolouring. A known further reduction [30], unmodified, yields lower bounds on the size of cutting planes refutations of the bit pigeonhole principle.

To explain why we obtain better parameters, it is convenient to think in terms of the falsified constraint search relation. For a fixed CSP, this relation consists of pairs of an assignment to variables and a constraint falsified by that output. This relation is universal, in the sense that for every relation $S$ there exists a CSP whose search relation is $S$ .

To apply the lifting technique we start with the search relation of a CSP on $n$ variables and $c$ constraints of arity $k$ , which is hard according to some query complexity measure. Then we compose that relation with a function on $m$ variables, a gadget, and we obtain a search relation of a CSP on $n m$ variables and $O(c\cdot m^{k})$ constraints, which is hard according to a communication complexity measure. When we reduce the lifted relation to e.g. clique, the size of the graph depends on the size of the lifted CSP, while the size of the clique depends on the original number of variables. Therefore minimising the arity of the CSP, along with the number of variables of the gadget, results in the least overhead.

Often it is enough to lift a CSP with constant arity over the binary alphabet, and the exact constant might not be too important if it is overshadowed by the gadget size. However, lifting theorems obtained through sunflowers can be applied with small gadgets of size $m^{1+\epsilon}$ , and arity becomes more relevant. For example, we could lift the standard 3-CSP Boolean encoding of the pigeonhole principle and obtain lower bounds for the clique function that hold for cliques of size up to $n^{1/3-\epsilon}$ . Using a 2-CSP with a constant-sized alphabet, however, allows us to obtain lower bounds for cliques of size up to $n^{1/2-\epsilon}$ .

We remark that the work introducing lifting theorems [43] already proves a lifting theorem for a large alphabet, which is used to lift a 2-CSP over an alphabet of linear size, precisely with the goal of proving formula lower bounds for the clique function. However, subsequent works only considered the Boolean case.

2 Lifting Theorem

A communication problem is a relation $S\colon X\times Y\to Z$ . We refer to an input $x\in X$ as Alice’s input, and to an input $y\in Y$ as Bob’s input. A DAG-like communication protocol computing a communication problem is a DAG where each node is identified with a set $R\subseteq X\times Y$ , with the following two properties. Each internal node is covered by its children. Each leaf is labelled with an element $z\in Z$ such that $z\in S(x,y)$ for all $(x,y)\in R$ .

A subcube-DAG protocol has the additional property that all nodes are subcubes, a rectangle-DAG protocol has the property that all nodes are combinatorial rectangles, and a triangle-DAG protocol has the property that all nodes are combinatorial triangles.

We assume that the fan-out of a subcube-DAG is $\Sigma$ when $X\times Y=\Sigma^{n}$ , and that the fan-out of rectangle- and triangle-DAGs is $2$ .

The width of a subcube-DAG is the maximum width (or codimension) of any node, and the width of a relation is the minimum width of any subcube-DAG computing it. Width is equivalent to following variation of the standard query complexity game, also called Prover–Adversary game [41, 6]. A player may query a variable or forget the value of a variable. The player aims to minimise the number of values they remember. The answer to a query is given by an adversary who aims to maximise that number and may give different answers to the same query.

The indexing function $\mathsf{Ind}_{m}\colon[m]\times\Sigma^{m}\to\Sigma$ is defined as $\mathsf{Ind}_{m}(x,y)=y_{x}$ . The composition of a relation $S\colon W^{n}\to Z$ and a function $g\colon V\to W$ , which we call a gadget, is $S\circ g^{n}\colon V^{n}\to Z$ .

Theorem 11 (Lifting Theorem).

There exists a large enough absolute constant $A$ such that any $m,n\in\mathbb{N}$ and any relation $S\colon\Sigma^{n}\to Z$ , the size of any triangle-DAG protocol solving $S\circ\mathsf{Ind}^{n}_{m}$ is at least

\left(\frac{m}{A\cdot|\Sigma|\cdot\mathsf{w}(S)\cdot\log(mn)}\right)^{\mathsf{% w}(S)}\,.

(5)

The theorem applies to rectangle-DAG protocols, which are a particular case of triangle-DAG protocols. It also holds that the communication complexity of $S\circ\mathsf{Ind}^{n}_{m}$ is bounded below by the query complexity of $S$ .

The search problem of a CSP $F$ is the relation $\mathsf{Search}(F)\colon\Sigma^{n}\to F$ that, given an assignment $\alpha\colon[n]\to\Sigma$ returns a constraint falsified by $\alpha$ . The relation is total if the CSP is unsatisfiable. In the context of a communication problem, we write $\mathsf{Search}^{X,Y}$ to explicitly refer to the variable partition.

Corollary 12.

For any $\epsilon>0$ , any alphabet $\Sigma$ , any unsatisfiable CSP $F$ on $n$ $\Sigma$ -variables, and any $m\geq\left(|\Sigma|\cdot\mathsf{w}(S)\cdot\log n\right)^{1+\epsilon}$ , the size of any triangle-DAG protocol solving $\mathsf{Search}(F)\circ\mathsf{Ind}^{n}_{m}$ is at least $m^{\Omega(\mathsf{w}(\mathsf{Search}(F)))}$ .

We prove the lifting theorem following the proof of the same theorem over the binary alphabet by de Rezende et al. [16]. Their proof simplifies proof of Lovett et al. [37], which in turn builds upon many other lifting theorems [27, 25, 22]. The proof of the lifting theorem relies on two lemmas, the full range lemma and the triangle lemma. A procedure that extracts a subcube-DAG from a triangle-DAG completes the proof. We describe how the proof needs to be adapted to a larger alphabet next. Since many parts of the proof change minimally or not at all, we defer the full proof to the appendix.

2.1 Full Range Lemma

The full range lemma states that, given a rectangle comprised of a well-structured $X$ part and a large enough $Y$ part, $\mathsf{Ind}(X,Y)$ takes all possible values. Following Lovett et al. [37], we prove this lemma as a consequence of the robust sunflower lemma, adapting their proof to a larger alphabet. Note that we cannot use the self-contained proof of de Rezende et al., which would result in a gadget size of at least $(n|\Sigma|)^{2+\epsilon}$ , while a gadget of size $(n|\Sigma|)^{1+\epsilon}$ is enough for a proof based on the sunflower lemma. In fact we can use gadgets of variable size $(w|\Sigma|)^{1+\epsilon}$ , depending on the width of the DAG we extract [23], assuming that $w=\Omega(\log n)$ . It is possible to remove the assumption $w=\Omega(\log n)$ with a more complex version of the full range lemma [37], but we do not require such small width.

We proceed to state the sunflower lemma. For a set $\mathcal{F}$ , $\mathcal{U}(\mathcal{F})$ is the distribution where we pick an element from $\mathcal{F}$ with probability $1/|\mathcal{F}|$ . $\mathcal{U}(X,p)$ is the distribution where we pick a set $S\subset X$ where $\Pr[x\in S]=p$ for all $x\in X$ independently. $\mathcal{D}_{1}(\{0,1\}^{N},p)$ is the distribution where we pick a string $s\in\{0,1\}^{N}$ where $\Pr[s_{i}=1]=p$ for all $i\in[N]$ independently.

The projection of an element $x\in X^{N}$ to a subset of coordinates $I\subseteq[N]$ is $x{\upharpoonright}_{I}=(x_{i})_{i\in I}$ . The projection of a set $S\subseteq X^{N}$ to a subset of coordinates $I\subseteq[N]$ is $S{\upharpoonright}_{I}=\{x{\upharpoonright}_{I}\mid x\in S\}$ . The marginal distribution of a random variable $A$ over a set $S\subseteq X^{N}$ on a subset of coordinates $I\subseteq[N]$ is $A{\upharpoonright}_{I}$ . We omit the projection symbol and write $x_{I}$ when it is clear from context.

A set system $\mathcal{F}$ over $A$ is $r$ -spread if for all $Z\subset A$ , it holds that

\Pr_{S\sim\mathcal{U}(\mathcal{F})}[Z\subset S]\leq r^{-|Z|}

(6)

The following robust sunflower lemma appears was proven by Rao [42, Lemma 4], although with a different distribution on sets $W$ , and was reproven by Tao [51, Proposition 5] and Bell et al. [9, Theorem 3] in the exact form we need.

Lemma 13 ([42, 51, 9]).

There is a universal constant $K$ such that the following holds. Let $0<p,\epsilon\leq 1/2$ , $s\geq 2$ , $r\geq K\cdot(1/p)\cdot\log(s/\epsilon)$ . Let $\mathcal{F}$ be a set system over $A$ such that:

1.

for all $S\in\mathcal{F}$ , $|S|\leq s$ ; and
2.

$\mathcal{F}$ is $r$ -spread.

Then

\Pr_{W\sim\mathcal{U}(A,p)}[\forall S\in\mathcal{F},\,S\not\subseteq W]\leq\epsilon

(7)

Next we use the sunflower lemma to prove the full range lemma, using the same concepts and adapting the proof of Lovett et al. [37].

The min-entropy of a random variable $A$ over a finite set $S$ , is

H_{\infty}(A):=\log\frac{1}{\max_{\beta\in S}\Pr\left[A=\beta\right]}.

(8)

We write $H_{\infty}(S)=H_{\infty}(\mathcal{U}(S))$ in an abuse of notation, and note that $H_{\infty}(S)=\log|S|$ .

A set $X\subseteq[m]^{N}$ has blockwise min-entropy $h$ with respect to a subset $J\subseteq[N]$ if for all $I\subseteq J$ it holds that $H_{\infty}(\mathcal{U}(X){\upharpoonright}_{I})\geq h|I|$ . Equivalently, if for all $I\subseteq J$ and $\beta\in[m]^{I}$ it holds that

\frac{\log(1/\Pr_{x\sim\mathcal{U}(X)}[x{\upharpoonright}_{I}=\beta])}{|I|}% \geq h.

(9)

If $J$ is omitted we assume $J=[N]$ .

The component list $S_{x}$ of a vector $x\in[m]^{N}$ is a set $S_{x}=\{(i,x_{i})\mid i\in[N]\}\subset[N]\times[m]$ . The component list set system of a set $X\subseteq[m]^{N}$ is $\mathcal{F}=\{S_{x}\mid x\in X\}$ .

The following key observation relates sunflowers and min-entropy, showing that the concepts of blockwise min-entropy and spreadness are equivalent.

Claim 14 ([37]).

A set $X\subseteq[m]^{N}$ has blockwise min-entropy $h=\log r$ iff the component list set system $\mathcal{F}$ of $X$ is $r$ -spread.

Claim 15 (Monotonicity).

For all $X\subseteq[m]^{N}$ , $\beta\colon X\to\Sigma^{N}$ and $\gamma\in\Sigma^{N}$ it holds

|y\in(\Sigma^{m})^{N}:\forall x\in X,y[x]\neq\beta(x)|\leq|y\in(\Sigma^{m})^{N% }:\forall x\in X,y[x]\neq\gamma|

(10)

Lemma 16 (Full Range Lemma).

Let $X\times Y\subseteq[m]^{N}\times(\Sigma^{m})^{N}$ be such that $X$ has block-wise min-entropy $\log r$ and $|Y|>\epsilon\cdot|\Sigma|^{mN}$ .

Let $K$ be a large enough constant. If $r,\epsilon$ , and $\Sigma$ satisfy $r\geq K\cdot|\Sigma|\cdot\log(N/\epsilon)$ then there exists an $x^{*}\in X$ such that for every $\beta\in\Sigma^{N}$ , there exists a $y_{\beta}\in Y$ such that $\mathsf{Ind}^{N}_{m}(x^{*},y_{\beta})=\beta$ .

Proof.

Let $\mathcal{F}$ be the component list set system of $X$ , which is $r$ -spread by Claim 14. Let $p=1/|\Sigma|$ . We can apply Lemma 13 with $s=N$ and get that:

\Pr_{S_{y}\sim\mathcal{U}([mN],p)}[\forall S_{x}\in\mathcal{F},S_{x}\not% \subseteq S_{y}]\leq\epsilon\,.

(11)

Let $y$ be the indicator vector for $S_{y}$ . This implies:

\Pr_{y\sim\mathcal{D}_{1}(\{0,1\}^{mN},p)}[\forall x\in X,y[x]\neq 1^{N}]\leq% \epsilon\,.

(12)

Suppose, for the sake of contradiction, that for all $x\in X$ there exists $\beta_{x}\in\Sigma^{N}$ such that for all $y\in Y$ , $y[x]\neq\beta_{x}$ . By counting:

$\displaystyle\|Y\|$	$\displaystyle\leq\|\{y\in(\Sigma^{m})^{N}:\forall x\in X,y[x]\neq\beta_{x}\}\|$	(13)
	$\displaystyle\leq\|\{y\in(\Sigma^{m})^{N}:\forall x\in X,y[x]\neq 1^{N}\}\|$	(14)
	$\displaystyle=\|\Sigma\|^{mN}\cdot\Pr_{y\sim\mathcal{U}(\Sigma^{mN})}[\forall x% \in X,y[x]\neq 1^{N}]$	(15)
	$\displaystyle=\|\Sigma\|^{mN}\cdot\Pr_{y\sim\mathcal{D}_{1}(\{0,1\}^{mN},p)}[% \forall x\in X,y[x]\neq 1^{N}]$	(16)
	$\displaystyle\leq\|\Sigma\|^{mN}\cdot\epsilon\,,$	(17)

where the first inequality is by our assumption on $Y$ , the second inequality is by Claim 15, and the last inequality is by Equation 12. This contradicts the bound on $|Y|$ . $\hfill\blacktriangleleft$

In particular, the Full Range Lemma holds when $r\geq m^{\delta}\geq K\cdot|\Sigma|\cdot 4w\cdot\log(mn^{2})$ and $\epsilon\leq 2^{-4w\log mn}$ , which is the setting in which we apply it.

2.2 Triangle Lemma

The triangle lemma shows how to cover each triangle in the protocol with sets of well-structured rectangles plus error rows and columns. The proof of this lemma is largely oblivious of the exact shape of the columns, which only comes into play when we need to prove that the set of error columns is not too large. The only changes we need to make are to consider the set of columns $Y$ as a subset of $\Sigma^{mn}$ rather than $\{0,1\}^{mn}$ , and the following calculation. For sets $A\subseteq B\neq\emptyset$ , the density of $A$ in $B$ is $|A|/|B|$ .

Claim 17.

Consider a collection of sets indexed by $\alpha\in([m]\cup\{\star\})^{n}$ , with $|\mathrm{fix}(\alpha)|\leq w$ , and $\beta\in(\Sigma\cup\{\star\})^{n}$ , with $\mathrm{fix}(\alpha)=\mathrm{fix}(\beta)$ . If every set has density at most $2^{-4w\log mn}$ , then the density of the whole collection is at most $2^{-w\log mn}$ .

Proof.

There are at most $\sum_{i=0}^{w}\binom{n}{i}m^{i}\leq(mn)^{w+1}\leq(mn)^{2w}$ many choices of $\alpha$ . Given a fixed $\alpha$ , there are at most $|\Sigma|^{|\mathrm{fix}(\alpha)|}\leq(mn)^{w}$ many choices of $\beta$ . By a union bound, the density of the union of all sets is at most $2^{-4w\log mn}\cdot(mn)^{2w}\cdot(nm)^{w}=2^{-w\log mn}$ . $\hfill\vartriangleleft$

2.3 Simulation

An informal sketch of how to extract a subcube-DAG from a triangle-DAG is as follows. We start at the root of the triangle-DAG, which corresponds to no queried variables. We can ensure this is the case only if the protocol is small with respect to the size of the error sets, which results in a small enough cumulative error. With the help of the triangle lemma, we traverse the triangle-DAG while maintaining a well-structured subset of the current triangle $T$ . If the block min-entropy of the well-structured subrectangle becomes larger with respect to a subset of variables $I^{\prime}$ that is different from the currently queried variables $I$ , then we do the following operation. First we forget all variables in $I\setminus I^{\prime}$ , then we query all variables in $I^{\prime}\setminus I$ . We use the full range lemma to guarantee that the answer to our queries is compatible with $T$ , and the answers themselves to choose which child of $T$ to follow in our traversal.

Again, nothing of substance changes when we use a larger alphabet. We rephrase the simulation to produce a subcube-DAG rather than a resolution refutation, reverting to the original formulation of DAG-like lifting [22]. This allows us to avoid syntactic issues with the negation of a term not being equivalent to a clause in multi-valued logic.

We provide a full proof in an appendix to the full version of this article.

2.4 Gadget Size

It is not possible to remove the linear dependence of the gadget size in terms of the alphabet size. We exhibit an explicit counterexample to lifting theorems with large alphabet and small gadgets.

Proposition 18.

There is a relation $R\colon\Sigma^{n}\to\Sigma$ with width $\Omega(n)$ but such that if $m=o(|\Sigma|)$ , then $R\circ\mathsf{Ind}_{m}^{n}$ has a protocol of size $O(|\Sigma|)$ .

Proof.

Let $R$ be defined as $(x,y)\in R$ iff $|\{i\in[n]\mid x_{i}=y\}|\leq n/2$ . On the one hand, the certificate complexity of the relation is $n/2$ , since every certificate must comprise at least $n/2$ coordinates where $x_{i}\neq y$ . Certificate complexity lower bounds width. On the other hand, if $m<|\Sigma|/2$ , then there exists an element $y\in\Sigma$ that appears less than $n/2$ times in Bob’s input to $R\circ\mathsf{Ind}_{m}^{n}$ . Hence a communication protocol is for Bob to simply announce that element, which gives a protocol of depth $\log|\Sigma|$ and size $|\Sigma|$ . $\hfill\blacktriangleleft$

Note that this example does not rule out a sublinear dependence when $\Sigma=\exp(n)$ , nor does it rule out an additive dependence.

3 Reductions

Let $G=((P\cup H),E)$ be a bipartite graph with uniform left degree $d$ . We assume $G$ is represented with an adjacency list (enforcing a fixed order on neighbours) and we denote the $i$ -th neighbour of $p\in P$ as $\Gamma(p,i)$ . The (functional) graph pigeonhole principle states that every left vertex maps to exactly one right vertex, and that the mapping is injective. We can encode this as a CSP, denoted $\mathrm{c}\text{}\mathrm{PHP}(G)$ , with variables $x_{p}$ for $p\in P$ , with the intended meaning that $z_{p}=i$ if $p$ is mapped to its $i$ th neighbour. The constraints of the CSP express injectivity: $[z_{p}\neq i]\lor[z_{p^{\prime}}\neq i^{\prime}]$ for each pair $p\neq p^{\prime}$ and $i,i^{\prime}$ such that $\Gamma(p,i)=\Gamma(p^{\prime},i^{\prime})$ . Totality and functionality are implicit from the choice of variables.

Specialised to $\mathrm{c}\text{}\mathrm{PHP}(G)$ , the falsified constraint search problem $\mathsf{Search}(\mathrm{c}\text{}\mathrm{PHP}(G))\colon[d]^{|P|}\times(P\times P)$ is the relation containing $(z,(p,p^{\prime}))$ if $\Gamma(p,z_{p})=\Gamma(p^{\prime},z_{p^{\prime}})$ ; in other words, if there exists $i,i^{\prime}\in[d]$ such that $\Gamma(p,i)=\Gamma(p^{\prime},i^{\prime})$ and the constraint $[z_{p}\neq i]\lor[z_{p^{\prime}}\neq i^{\prime}]$ is violated. Recall that if $\mathrm{c}\text{}\mathrm{PHP}(G)$ is unsatisfiable, then $\mathsf{Search}(\mathrm{c}\text{}\mathrm{PHP}(G))$ is a total search problem.

The monotone Karchmer–Wigderson game of a (partial) monotone Boolean function $f$ is a communication problem $\mathrm{mKW}_{f}$ where Alice gets an input $x\in f^{-1}(0)$ , Bob gets an input $y\in f^{-1}(1)$ , and the set of correct outputs are coordinates $i\in[n]$ such that $x_{i}<y_{i}$ . The monotone (real) circuit size complexity of $f$ is equivalent to the rectangle-DAG (resp. triangle-DAG) size complexity of $\mathrm{mKW}_{f}$ [49, 31].

Lemma 19.

Let $G=((P\cup H),E)$ be a bipartite graph with $|P|=k$ and $|H|=c<k$ and uniform left degree $d$ . Then for any $m$ it holds that $\mathsf{Search}(\mathrm{c}\text{}\mathrm{PHP}(G))\circ\mathsf{Ind}^{k}_{m}$ reduces to $\mathrm{mKW}_{(\mathrm{clique}_{k}\text{-}\mathrm{col}_{c})_{mk}}$ .

Proof.

We need to show that there exists a function $\mu_{A}\colon[m]^{k}\rightarrow\{0,1\}^{\binom{mk}{2}}$ mapping Alice’s input and a function $\mu_{B}\colon[d]^{mk}\rightarrow\{0,1\}^{\binom{mk}{2}}$ mapping Bob’s input for $\mathsf{Search}(\mathrm{c}\text{}\mathrm{PHP}(G))\circ\mathsf{Ind}^{k}_{m}$ to their respective inputs for $\mathrm{mKW}_{(\mathrm{clique}_{k}\text{-}\mathrm{col}_{c})_{mk}}$ .

Moreover, we need a function $\mu_{O}\colon\{0,1\}^{\binom{mk}{2}}\rightarrow P\times P$ mapping from answers of $\mathrm{mKW}_{(\mathrm{clique}_{k}\text{-}\mathrm{col}_{c})_{mk}}$ to answers of $\mathsf{Search}(\mathrm{c}\text{}\mathrm{PHP}(G))\circ\mathsf{Ind}^{k}_{m}$ such that $\forall x,y$ it holds that

\mu_{O}(\mathrm{mKW}_{(\mathrm{clique}_{k}\text{-}\mathrm{col}_{c})_{mk}}(\mu_% {A}(x),\mu_{B}(y)))\subseteq\mathsf{Search}(\mathrm{c}\text{}\mathrm{PHP}(G))% \circ\mathsf{Ind}^{k}_{m}(x,y)\,.

(18)

We start by defining $\mu_{A}$ and $\mu_{B}$ . Both functions output a grid graph on the vertex set $V=\{(s,p):s\in[m],p\in[k]\}$ ; however, $\mu_{A}$ outputs a graph containing a $k$ -clique and $\mu_{B}$ outputs a $c$ -colourable graph.

Alice’s input to $\mathsf{Search}(\mathrm{c}\text{}\mathrm{PHP}(G))\circ\mathsf{Ind}^{k}_{m}$ are pointers $x_{p}\in[m]$ for $p\in[k]$ . Alice’s graph $(V,E_{A})$ output by $\mu_{A}$ is defined as $E_{A}=\{((x_{p},p),(x_{p^{\prime}},{p^{\prime}})):p,p^{\prime}\in[k],p\neq p^{% \prime}\}$ ; in other words, $E_{A}$ is precisely a clique of size $k$ over the vertices $(x_{p},p)_{p\in[k]}$ .

Bob’s input to $\mathsf{Search}(\mathrm{c}\text{}\mathrm{PHP}(G))\circ\mathsf{Ind}^{k}_{m}$ are strings $y_{p}\in[d]^{m}$ for $p\in[k]$ . Bob’s graph $(V,E_{B})$ output by $\mu_{B}$ is the maximal graph that admits the following $c$ -colouring: vertex $(s,p)$ is coloured $\Gamma(p,i)$ for $i=\mathsf{Ind}(s,{y_{p}})$ , that is, $(s,p)$ is coloured $q$ , where $q$ is the $\mathsf{Ind}(s,{y_{p}})$ -th neighbour of $p$ in $G$ .

Finally, we define $\mu_{O}((s,p),(s^{\prime},p^{\prime}))=(p,p^{\prime})$ . It remains to argue that Equation 18 is satisfied. By definition of $\mathrm{mKW}_{(\mathrm{clique}_{k}\text{-}\mathrm{col}_{c})_{mk}}(\mu_{A}(x),% \mu_{B}(y))$ , we have that $((s,p),(s^{\prime},p^{\prime}))$ is an edge that belongs to Alice’s graph but not to Bob’s. We need to argue that $(p,p^{\prime})$ is a valid answer to $\mathsf{Search}(\mathrm{c}\text{}\mathrm{PHP}(G))$ on input $z=\mathsf{Ind}_{m}^{k}(x,y)$ , that is, we must show that for $z_{p}=\mathsf{Ind}(x_{p},y_{p})$ and $z_{p^{\prime}}=\mathsf{Ind}(x_{p^{\prime}},y_{p^{\prime}})$ it holds that $\Gamma(p,z_{p})=\Gamma(p^{\prime},z_{p^{\prime}})$ . By construction of Bob’s graph, $\Gamma(p,i)=\Gamma(p^{\prime},i^{\prime})$ , for $i=\mathsf{Ind}(s,y_{p})$ and $i^{\prime}=\mathsf{Ind}(s^{\prime},y_{p^{\prime}})$ , and by construction of Alice’s graph, $s=x_{p}$ and $s^{\prime}=x_{p^{\prime}}$ . Together this implies that $\Gamma(p,z_{p})=\Gamma(p^{\prime},z_{p^{\prime}})$ , as we wished to prove. $\hfill\blacktriangleleft$

Given two graphs $G_{a}=(V,E_{a})$ $G_{b}=(V,E_{b})$ with $E_{a}\cap E_{b}=\emptyset$ and $c,k\in\mathbb{N}$ with $c<k$ , we define the function $\mathrm{clique}_{k}\text{-}\mathrm{col}_{c}({G_{a},G_{b}}):\{0,1\}^{|E_{a}|}$ to be the function that receives as input a subset of edges $E$ of $E_{a}$ and outputs $0$ if $E\cup E_{b}$ is $c$ -colourable and $1$ if $E\cup E_{b}$ has a $k$ -clique. Observe that $\mathrm{clique}_{k}\text{-}\mathrm{col}_{c}({G_{a},G_{b}})$ is a restriction of the function $(\mathrm{clique}_{k}\text{-}\mathrm{col}_{c})_{|V|}$ where all the edges in $E_{b}$ are set to $1$ and all the edges in neither $E_{a}$ nor $E_{b}$ are set to $0$ .

Let $G=((P\mathop{\dot{\cup}}H),E)$ be a bipartite graph with $P=\{p_{1},\ldots,p_{k}\}$ . We define the graphs $\widetilde{G}_{a,m}=(\widetilde{V},\widetilde{E}_{a})$ and $\widetilde{G}_{b,m}=(\widetilde{V},\widetilde{E}_{b})$ to be $k$ -partite graphs with vertex set $\widetilde{V}=V_{1}\mathop{\dot{\cup}}V_{2}\mathop{\dot{\cup}}\ldots\mathop{% \dot{\cup}}V_{k}$ , each $V_{i}$ with $m$ vertices, and edge sets

	$\displaystyle\widetilde{E}_{a}=\{(u,v)\in V_{i}\times V_{j}:i,j\in[k],i\neq j,% \exists h\in H\text{ s.t. }(p_{i},h),(p_{j},h)\in E\};\text{ and }$		(19)
	$\displaystyle\widetilde{E}_{b}=\{(u,v)\in V_{i}\times V_{j}:i,j\in[k],i\neq j,% \nexists h\in H\text{ s.t. }(p_{i},h),(p_{j},h)\in E\}\,.$		(20)

Note that, if $G$ has left degree at most $d=O(1)$ , then for each $i$ , there are at most $d^{2}$ different $j$ ’s such that $\exists h\in H\text{ s.t. }(p_{i},h),(p_{j},h)\in E$ . Therefore, the graph $\widetilde{G}_{m,a}$ has at most $m^{2}\cdot kd^{2}$ edges.

Lemma 20.

Let $G=((P\cup H),E)$ be a bipartite graph with $|P|=k$ and $|H|=c<k$ and uniform left degree $d$ . For any $m\in\mathbb{N}$ it holds that $\mathsf{Search}(\mathrm{c}\text{}\mathrm{PHP}(G))\circ\mathsf{Ind}^{k}_{m}$ reduces to $\mathrm{mKW}_{\mathrm{clique}_{k}\text{-}\mathrm{col}_{c}({\widetilde{G}_{a,m}% ,\widetilde{G}_{b,m}})}$ .

Proof.

The proof is exactly the same as for Lemma 19, with the only difference that some of the edges do not need to be defined by the reductions $\mu_{A}$ and $\mu_{B}$ . Note that the edges not in either $\widetilde{E}_{a}$ nor $\widetilde{E}_{b}$ are always set to $0$ in Alice’s graph, and the edges in $\widetilde{E}_{b}$ are always set to $1$ in Bob’s graph, so these edges are never a solution output by $\mu_{O}$ . $\hfill\blacktriangleleft$

Observation 21.

Let $c_{1},c_{2},n\in\mathbb{N}$ be such that $c_{1}c_{2}<n$ . We have that $\mathrm{mKW}_{(\mathrm{col}_{c_{1}}\text{-}\mathrm{cocol}_{c_{2}})_{n}}$ reduces to $\mathrm{mKW}_{(\mathrm{clique}_{n/c_{2}}\text{-}\mathrm{col}_{c_{1}})_{n}}$ .

Lemma 22.

Let $c,r,k,n\in\mathbb{N}$ be such that $c\leq r<k\leq n$ . It holds that $\mathrm{mKW}_{(\mathrm{clique}_{k}\text{-}\mathrm{col}_{c})_{n}}$ reduces to $\mathrm{mKW}_{(\mathrm{col}_{r}\text{-}\mathrm{cocol}_{n-k+r})_{nr}}$ .

Proof.

We define functions $\mu_{A},\mu_{B}\colon\{0,1\}^{\binom{n}{2}}\rightarrow\{0,1\}^{\binom{nr}{2}}$ such that $\mu_{B}$ maps $c$ -colourable to $r$ -colourable graphs and $\mu_{A}$ maps graphs containing a $k$ -clique to graphs whose complement is $(n-k+r)$ -colourable.

Suppose Alice’s input for $\mathrm{mKW}_{(\mathrm{clique}_{k}\text{-}\mathrm{col}_{c})_{n}}$ is the graph $G_{A}=(V,E_{A})$ and Bob’s input is $G_{B}=(V,E_{B})$ . The graphs output by the functions $\mu_{A},\mu_{B}$ are defined on vertex set $U=\{(v,i):v\in V,i\in[r]\}$ as follows.

Let $\chi\colon V\rightarrow[c]$ be a proper $c$ -colouring of $G_{B}$ . Bob’s graph $(U,\widetilde{E}_{B})$ output by $\mu_{B}$ is the maximal graph that admits the following $r$ -colouring: vertex $(v,i)$ is coloured with colour $(\chi(v)+i)\!\!\mod r$ . Since this graph admits an $r$ -colouring it is a valid input for Bob for $\mathrm{mKW}_{(\mathrm{col}_{r}\text{-}\mathrm{cocol}_{n-k+r})_{nr}}$ .

Let $K\subseteq V$ be a set of $k$ vertices such that $G_{A}[K]$ is a clique. Alice’s graph $(U,\widetilde{E}_{A})$ output by $\mu_{A}$ contains edges $\widetilde{E}_{A}=\{((v,i_{1}),(v,i_{2})):v\not\in K,i_{1},i_{2}\in[r],i_{1}% \neq i_{2}\}\cup\{((v_{1},i),(v_{2},i)):v_{1},v_{2}\in K,v_{1}\neq v_{2},i\in[% r]\}$ . Note that this graph is formed by $n-k+r$ disjoint cliques and, therefore, it is a valid input for Alice for $\mathrm{mKW}_{(\mathrm{col}_{r}\text{-}\mathrm{cocol}_{n-k+r})_{nr}}$ .

Finally, we define the function $\mu_{O}(((v_{1},i_{1}),(v_{2},i_{2})))=(v_{1},v_{2})$ mapping outputs of $\mathrm{mKW}_{(\mathrm{col}_{r}\text{-}\mathrm{cocol}_{n-k+r})_{nr}}$ to outputs of $\mathrm{mKW}_{(\mathrm{clique}_{k}\text{-}\mathrm{col}_{c})_{n}}$ . It remains to argue that valid answers are mapped to valid answers. Let $((v_{1},i_{1}),(v_{2},i_{2}))$ be an edge present in Alice’s graph and absent in Bob’s graph. By Alice’s construction, either $v_{1}=v_{2}$ or $i_{1}=i_{2}$ . By Bob’s construction, if $v_{1}=v_{2}$ and $i_{1}\neq i_{2}$ then $(\chi(v_{1})+i_{1})\!\!\mod r\neq(\chi(v_{2})+i_{2})\!\!\mod r$ and thus there is an edge between $(v_{1},i_{1})$ and $(v_{2},i_{2})$ . It must therefore be the case that $i_{1}=i_{2}$ , which implies that $v_{1},v_{2}\in K$ and that $\chi(v_{1})\neq\chi(v_{2})$ . We conclude that $(v_{1},v_{2})$ is a valid answer for $\mathrm{mKW}_{(\mathrm{clique}_{k}\text{-}\mathrm{col}_{c})_{n}}$ . $\hfill\blacktriangleleft$

Lemma 23.

Let $c_{1},c_{2},\ell_{1},\ell_{2},n\in\mathbb{N}$ be such that $c_{1}c_{2}<n$ and $\ell_{1},\ell_{2}\geq 1$ . It holds that $\mathrm{mKW}_{(\mathrm{col}_{c_{1}}\text{-}\mathrm{cocol}_{c_{2}})_{n}}$ reduces to $\mathrm{mKW}_{(\mathrm{col}_{\ell_{1}c_{1}}\text{-}\mathrm{cocol}_{\ell_{2}c_{% 2}})_{\ell_{1}\ell_{2}n}}$ .

Proof.

Given the symmetry of $\mathrm{mKW}_{(\mathrm{col}_{c_{1}}\text{-}\mathrm{cocol}_{c_{2}})_{n}}$ , it is enough to reduce $\mathrm{mKW}_{(\mathrm{col}_{c_{1}}\text{-}\mathrm{cocol}_{c_{2}})_{n}}$ to $\mathrm{mKW}_{(\mathrm{col}_{\ell c_{1}}\text{-}\mathrm{cocol}_{c_{2}})_{\ell n}}$ .

The reduction is given by functions $\mu_{A},\mu_{B}\colon\{0,1\}^{\binom{n}{2}}\rightarrow\{0,1\}^{\binom{n\ell}{2}}$ such that $\mu_{A}$ maps a $c_{1}$ -colourable graph into an $\ell c_{1}$ -colourable graph, and $\mu_{B}$ maps a graph whose complement is $c_{2}$ -colourable into a graph whose complement is $c_{2}$ -colourable.

Suppose Alice’s input for $\mathrm{mKW}_{(\mathrm{col}_{c_{1}}\text{-}\mathrm{cocol}_{c_{2}})_{n}}$ is the graph $G_{A}=(V,E_{A})$ and Bob’s input is $G_{B}=(V,E_{B})$ . The graphs output by the functions $\mu_{A},\mu_{B}$ are defined on vertex set $U=\{(v,i):v\in V,i\in[\ell]\}$ as follows. Alice’s graph $(U,\widetilde{E}_{A})$ has edges $\widetilde{E}_{A}=\{((v_{1},i_{1}),(v_{2},i_{2})):(v_{1},v_{2})\in E_{A},i_{1}% ,i_{2}\in[\ell]\}$ , and admits the colouring $\xi(v,i)=\ell\xi(v)+i$ . Bob’s graph $(U,\widetilde{E}_{B})$ has edges $\widetilde{E}_{B}=\{((v_{1},i_{1}),(v_{2},i_{2})):i_{1}\neq i_{2}\text{ or }(v% _{1},v_{2})\in E_{B}\}$ . Since its complement consists of $\ell$ independent copies of the complement of $G_{B}$ , it is $c_{2}$ -colourable.

Finally, we map outputs according to the function $\mu_{O}(((v_{1},i_{1}),(v_{2},i_{2})))=(v_{1},v_{2})$ . To show that the reduction is correct, we observe that if $((v_{1},i_{1}),(v_{2},i_{2}))$ is not present in Bob’s graph, then it must be the case that $i_{1}=i_{2}$ and $(v_{1},v_{2})\not\in E_{B}$ , while if $((v_{1},i_{1}),(v_{2},i_{2}))$ is present in Alice’s graph, then it must be that $(v_{1},v_{2})\in E_{A}$ . $\hfill\blacktriangleleft$

The CSP $\mathrm{bitPHP}_{c}^{n}$ for $n$ pigeons and $c$ holes is defined over $n\log c$ binary variables and has a constraint expressing $\neg\bigwedge_{j\in[\log c]}(x_{i,j}=x_{i^{\prime},j})$ , expanded into CNF, for each $i\neq i^{\prime}\in[n]$ .

Lemma 24 ([30]).

Let $c_{1},c_{2},\ell_{1},\ell_{2},n\in\mathbb{N}$ be such that $c_{1}c_{2}<n$ . Partition the inputs of $\mathsf{Search}^{X,Y}(\mathrm{bitPHP}_{c_{1}c_{2}}^{n})$ , where $X$ is the first $\log c_{1}$ variables and $Y$ is the last $\log c_{2}$ variables of each pigeon. Then $\mathrm{mKW}_{(\mathrm{col}_{c_{1}}\text{-}\mathrm{cocol}_{c_{2}})_{n}}$ and $\mathsf{Search}^{X,Y}(\mathrm{bitPHP}_{c_{1}c_{2}}^{n})$ are equivalent.

Proof.

There is a direct correspondence between problems. An instance of the communication problem $\mathsf{Search}^{X,Y}(\mathrm{bitPHP}_{c_{1}c_{2}}^{n})$ can be viewed as two colourings of a graph on $n$ vertices: the first one is a colouring with $c_{1}$ colours, and the second with $c_{2}$ colours. Bob’s graph can be constructed by taking the maximal graph respecting the $c_{1}$ -colouring; and Alice’s graph can be constructed by taking the minimal graph such that the $c_{2}$ -colouring is a valid cocolouring. An edge present in Alice’s graph and missing in Bob’s corresponds precisely to two rows of their input which are the same.

The other direction is similar. Let $\chi_{1}$ be a colouring of Bob’s graph, and $\chi_{2}$ be a cocolouring of Alice’s graph. Alice and Bob can create a matrix with $n$ rows such that Alice’s (resp. Bob’s) part of row $i$ is $\chi_{2}(i)$ (resp. $\chi_{1}(i)$ ) written in binary. Two rows that are the same correspond precisely to an edge present in Alice’s graph and missing in Bob’s. $\hfill\blacktriangleleft$

4 Applications

In this section, we prove the theorems stated in the introduction, which are all obtained via an application of the lifting theorem to the CSP $\mathrm{c}\text{}\mathrm{PHP}(G)$ for an appropriate expander graph $G$ , and the appropriate reduction from Section 3.

To obtain a width lower bound we need the bipartite graph $G$ , over which $\mathrm{c}\text{}\mathrm{PHP}(G)$ is defined, to be a good vertex expander as per the following definition. A $(m,n,d,r,e)$ -bipartite expander graph is a bipartite graph $G=((U\cup V),E)$ with $|U|=m$ , $|V|=n$ , with every vertex in $U$ having degree at most $d$ , and where for every subset $S\subseteq[m]$ such that $|S|\leq r$ , the neighbourhood of $S$ , denoted $N(S)$ , satisfies $|{N}(S)|\geq e|S|$ . A standard calculation [29] shows that random graphs are good expanders. We record two different parameter regimes that we use in our applications.

The first family of expander graphs have constant degree, and are fairly balanced.

Lemma 25.

Let $m,n\in\mathbb{N}$ be such that $m=\Theta(n)$ . Then there exists $d=O(1)$ and $r=\Omega(n)$ such that with high probability a random graph $G\sim\mathbf{G}(m,n,d)$ is an $(m,n,d,r,d/2)$ -bipartite expander graph.

The second family has logarithmic degree and can be very unbalanced.

Lemma 26.

Let $r,d,n,m\in\mathbb{N}$ be such that $n\leq m$ , $d=6\ln m$ and $r=n/de^{3}$ . With high probability a random graph $G\sim\mathbf{G}(m,n,d)$ is an $(m,n,d,r,d/2)$ -bipartite expander graph.

We can easily obtain a width lower bound for refuting $\mathrm{c}\text{}\mathrm{PHP}(G)$ from known width lower bounds on the $\{0,1\}$ -encoding of the graph pigeonhole principle [10] at the cost of a linear factor in the degree of the graph. We prefer, however, to prove the lower bound directly and avoid such loss.

Let $G=((U\cup V),E)$ be a bipartite graph. A collection of matchings $\mathcal{M}$ is an $s$ -online matching if $\emptyset\in\mathcal{M}$ ; $\mathcal{M}$ is closed under taking subsets; and if for each matching $M\in\mathcal{M}$ such that $|M|<s$ , and for each $u\in U$ not covered by $M$ there exists $v\in V$ such that $M\cup\{(u,v)\}\in\mathcal{M}$ .

Lemma 27 ([21]).

If $G$ is an $(m,n,d,r,e)$ -bipartite expander graph, then it has an ${(e-1)r/2}$ -online matching.

Since online matchings correspond precisely to adversary strategies in the Prover–Adversary games, we obtain the following, slightly tighter, lower bound. The upper bound is given by a Prover strategy that queries any $n+1$ left vertices.

Theorem 28.

If $G$ is an $(m,n,d,r,e)$ -bipartite expander graph then

\frac{(e-1)r}{2}\leq\mathsf{w}(\mathsf{Search}(\mathrm{c}\text{}\mathrm{PHP}(G% )))\leq n+1\,.

We can now apply our lifting theorem (Theorem 11) to $\mathrm{c}\text{}\mathrm{PHP}(G)$ for an appropriate $G$ and obtain the following result.

Theorem 3 (Clique-colouring). [Restated, see original statement.]

There exists a universal constant $A$ such that given any $c,k,n\in\mathbb{N}$ satisfying $c<k\leq n$ , it holds that any monotone Boolean circuit computing $(\mathrm{clique}_{k}\text{-}\mathrm{col}_{c})_{n}$ must have size

\left(\frac{n}{A\cdot kc\log k\log n}\right)^{\Omega\left({c}\right)}\,.

(3)

If we assume $c=\epsilon k$ for a constant $\epsilon>0$ , then we can get a slightly better lower bound: any monotone Boolean circuit computing $(\mathrm{clique}_{k}\text{-}\mathrm{col}_{\epsilon k})_{n}$ must have size

\left(\frac{n}{A\cdot k^{2}\log n}\right)^{\Omega\left({k}\right)}\,.

(4)

Proof.

For the first part, let $G$ be an $(k,c,d,r,d/2)$ -bipartite expander graph for $d=O(\log k)$ and $dr=\Omega(c)$ . By Theorem 28, we have that $c+1\geq\mathsf{w}(\mathsf{Search}(\mathrm{c}\text{}\mathrm{PHP}(G)))=\Omega(c)$ . Applying Theorem 11 we conclude that there exists a large enough absolute constant $A^{\prime}$ such that any triangle-DAG protocol solving $\mathsf{Search}(\mathrm{c}\text{}\mathrm{PHP}(G))\circ\mathrm{IND}_{m}^{k}$ requires size

\left(\frac{m}{A^{\prime}\cdot d\cdot(c+1)\cdot\log(mk)}\right)^{(d/2-1)r/2}% \geq\left(\frac{m}{A\cdot\log k\cdot c\cdot\log(mk)}\right)^{\Omega\left(c% \right)}\,.

(21)

Finally, the result follows from the reduction to clique-colouring given by Lemma 19, where we note that $n=mk$ .

The second part is similar, but we choose $G$ to be an $(k,\epsilon k,d,r,d/2)$ -bipartite expander graph for $d=O(1)$ and $r=\Omega(k)$ . The result follows, as before, by applying the lifting theorem (Theorem 11) to the width lower bound (Theorem 28) and using the reduction to clique-colouring (Lemma 19). $\hfill\blacktriangleleft$

We are now ready to prove Theorem 6, restated below.

Theorem 6. [Restated, see original statement.]

For $c\leq n^{1/3-\epsilon}$ , every monotone function that distinguishes $n$ -vertex graphs $G$ with $\chi(G)\leq c$ from graphs with $\chi(\overline{G})\leq n/c-1$ has monotone real circuit complexity $n^{\Omega(c)}$ .

We actually prove a slightly more general statement that we use later on.

Theorem 29.

There exists an absolute constant $A$ such that any monotone real circuit computing $(\mathrm{col}_{c}\text{-}\mathrm{cocol}_{n/c-1})_{n}$ has size at least

\displaystyle\left(\frac{n}{A\cdot c^{3}\log(n)}\right)^{\Omega\left(c\right)}\,.

Proof.

It follows from Lemma 22, by setting $k=c+1$ and $r=c$ , that there is a reduction from $\mathrm{mKW}_{(\mathrm{clique}_{c+1}\text{-}\mathrm{col}_{c})_{n^{\prime}}}$ to $\mathrm{mKW}_{(\mathrm{col}_{c}\text{-}\mathrm{cocol}_{n^{\prime}-1})_{n^{% \prime}c}}$ . By renaming $n=n^{\prime}\cdot c$ we get that the latter is equivalent to $\mathrm{mKW}_{(\mathrm{col}_{c}\text{-}\mathrm{cocol}_{n/c-1})_{n}}$ .

By Theorem 3, this implies that any monotone real circuit computing $(\mathrm{col}_{c}\text{-}\mathrm{cocol}_{n^{\prime}-1})_{n^{\prime}c}$ must have size at least

\displaystyle\left(\frac{n^{\prime}}{A^{\prime}\cdot k^{2}\log(n^{\prime})}% \right)^{\Omega\left(k\right)}=\left(\frac{n}{A\cdot c^{3}\log(n)}\right)^{% \Omega\left(c\right)}\,,

(22)

for some universal constants $A$ and $A^{\prime}$ . $\hfill\blacktriangleleft$

We can now easily prove Theorem 5 and Theorem 8.

Theorem 5 (Colouring-cocolouring). [Restated, see original statement.]

Every monotone function that distinguishes $(q^{2}+1)$ -vertex graphs $G$ with $\chi(G)\leq q$ from graphs with $\chi(\overline{G})\leq q$ has monotone real circuit complexity $2^{\Omega((q/\log q)^{1/2})}$ .

Proof.

As argued in the proof above, we have that any monotone real circuit computing $(\mathrm{col}_{c}\text{-}\mathrm{cocol}_{n^{\prime}-1})_{n^{\prime}c}$ requires size

\displaystyle\left(\frac{n^{\prime}}{A^{\prime}\cdot k^{2}\log(n^{\prime})}% \right)^{\Omega\left(k\right)}

(23)

for $k=c+1$ . Setting $\ell_{1}=(n^{\prime}-1)/c$ and applying Lemma 23, and setting $c=\epsilon(n^{\prime}/\log n^{\prime})^{1/2}$ for $\epsilon=1/4A^{\prime}$ , we conclude that any monotone real circuit computing $(\mathrm{col}_{n^{\prime}-1}\text{-}\mathrm{cocol}_{n^{\prime}-1})_{n^{\prime}% (n^{\prime}-1)}$ requires size $2^{\Omega\left((n^{\prime}/\log n^{\prime})^{1/2}\right)}$ . Substituting $q=n^{\prime}-1$ , gives us the stated bound. $\hfill\blacktriangleleft$

To formally state Theorem 8 we need to define the cutting planes proof system. We choose to define the semantic version, which is simpler and stronger than the syntactic one. A semantic cutting planes refutation of a CSP $F$ given by a set of linear inequalities $F=\{A_{1},\ldots,A_{m}\}$ is a sequence of linear inequalities $C_{1},\ldots,C_{L}$ where $C_{j}$ is either identical to some $A_{i}$ , or is semantically implied by $C_{i}$ and $C_{i^{\prime}}$ with $i,i^{\prime}<j$ . In the proof below, we use the fact that, given a cutting planes refutation of a CSP $F$ of length $L$ , there exists a triangle-DAG protocol of size $L$ computing $\mathsf{Search}^{X,Y}(F)$ for any partition $X, Y$ [49, 31].

Theorem 8 (Bit pigeonhole principle). [Restated, see original statement.]

Every cutting planes refutation of the bit pigeonhole principle $\mathrm{bitPHP}^{N+1}_{N}$ has size $2^{\Omega((N/\log N)^{1/3})}$ .

Proof.

Immediate from Theorem 29, Lemma 24, and the correspondence between the size of cutting planes proofs and triangle-DAGs. $\hfill\blacktriangleleft$

Finally, we prove Theorem 10, which requires a slightly more careful argument than that in the proof of Theorem 3.

Theorem 10 (Monotone vs non-monotone). [Restated, see original statement.]

There exists a monotone function $f\in{\text{P}}$ such that any monotone circuit computing $f$ is of size at least $\exp(\Omega(n^{1/3-o(1)}))$ .

We define the graphs $\widetilde{G}_{a,m}=(\widetilde{V},\widetilde{E}_{a})$ and $\widetilde{G}_{b,m}=(\widetilde{V},\widetilde{E}_{b})$ to be $k$ -partite graphs with vertex set $\widetilde{V}=V_{1}\mathop{\dot{\cup}}V_{2}\mathop{\dot{\cup}}\ldots\mathop{% \dot{\cup}}V_{k}$ , where $|V_{i}|=m$ , and edge sets

	$\displaystyle\widetilde{E}_{a}=\{(u,v)\in V_{i}\times V_{j}:i,j\in[k],i\neq j,% \exists h\in H\text{ s.t. }(p_{i},h),(p_{j},h)\in E\};\text{ and }$		(24)
	$\displaystyle\widetilde{E}_{b}=\{(u,v)\in V_{i}\times V_{j}:i,j\in[k],i\neq j,% \nexists h\in H\text{ s.t. }(p_{i},h),(p_{j},h)\in E\}\,.$		(25)

Note that, if $G$ has left degree at most $d=O(1)$ , then for each $i$ , there are at most $d^{2}$ different $j$ ’s such that there exists $h\in H$ with $(p_{i},h),(p_{j},h)\in E$ . Therefore, the graph $\widetilde{G}_{m,a}$ has at most $m^{2}\cdot kd^{2}$ edges.

Proof of Theorem 10.

Let $G=(P\mathop{\dot{\cup}}H,E)$ be a $(k,k-1,d,r,d/s)$ -bipartite expander graph given by Lemma 25, with $d=O(1)$ and $r=\Omega(k)$ . For any $m$ the following holds.

Let $\widetilde{G}_{a,m}=(\widetilde{V},\widetilde{E}_{a})$ and $\widetilde{G}_{b,m}=(\widetilde{V},\widetilde{E}_{b})$ be the graphs defined for Lemma 20. Note that the graph $\widetilde{G}_{m,a}$ has at most $O(m^{2}\cdot k)$ edges, so the function $\mathrm{clique}_{k}\text{-}\mathrm{col}_{c}({\widetilde{G}_{a,m},\widetilde{G}% _{b,m}})$ has $n=O(m^{2}\cdot k)$ inputs. By Theorem 11 applied to $\mathrm{c}\text{}\mathrm{PHP}(G)$ , and using the reduction in Lemma 20, we conclude that any monotone circuit computing $\mathrm{clique}_{k}\text{-}\mathrm{col}_{c}({\widetilde{G}_{a,m},\widetilde{G}% _{b,m}})$ requires size at least

\left(\frac{m}{A\cdot k\cdot\log(mk)}\right)^{\Omega(k)}

(26)

for a large enough constant $A$ .

By choosing $m=A^{\prime}k\log k$ , for large enough constant $A^{\prime}$ , we have that

\left(\frac{m}{A\cdot k\cdot\log(mk)}\right)^{\Omega(k)}\geq\exp(\Omega(k))% \geq\exp\left(\Omega\left(\left({n}/{\log^{2}n}\right)^{1/3}\right)\right)\geq% \exp(\Omega(n^{1/3-o(1)}))\,.

(27)

Now let $g$ be the total monotone function in P that extends $(\mathrm{clique}_{k}\text{-}\mathrm{col}_{k-1})_{N}$ for $N=\binom{km}{2}$ given by Tardos [52]. Consider the function $f$ that is obtained from $g$ by setting all edges in $\widetilde{E}_{b}$ to $1$ and all edges not in either $\widetilde{E}_{a}$ nor $\widetilde{E}_{b}$ to $0$ . Note that this function computes $\mathrm{clique}_{k}\text{-}\mathrm{col}_{c}({\widetilde{G}_{a,m},\widetilde{G}% _{b,m}})$ . Moreover, since it is a restriction of a function in P, it follows that $f\in{\text{P}}$ . This concludes the proof. $\hfill\blacktriangleleft$

5 Concluding Remarks

While the lower bounds we proved are better than what is currently known via the approximation method, we believe that it is possible to prove matching bounds with the approximation method. Both methods have common traits: the procedure in which we identify error rectangles in a triangle-DAG by traversing its nodes from the leaves is not too unlike the procedure in which we identify error functions in a monotone circuit, and the best bounds for both are obtained using sunflower lemma. It might even be possible to prove that lifting is a particular instantiation of the approximation method. The advantage of our approach is that once the lifting theorem is established, we can apply it as a black box and obtain new lower bounds by simply proving reductions in the communication world.

The lower bounds in this paper have been known, and presented in various occasions, since 2021. Since then, some of the results have been obtained with the approximation method. A very recent paper independently obtained the same bound for clique-colouring using the approximation method and sunflowers [13]. A bottleneck counting approach (which is the same as approximation method) was used to directly prove a nearly optimal cutting planes lower bound for a different formula [50]. Extending the bottleneck counting argument, another very recent paper independently obtained the same bound for cutting planes proofs of the bit pigeonhole principle [8], even in the weak setting. It may also be possible to obtain an $\exp(\Omega({n^{1/3-\epsilon}}))$ lower bound for a monotone function in P using the approximation method [14], albeit for a different function.

References

[1] N. Alon and R. B. Boppana. The monotone circuit complexity of Boolean functions. Combinatorica, 7:1–22, 1987. doi:10.1007/BF02579196.
[2] Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang. Improved bounds for the sunflower lemma. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 624–630. ACM, 2020. doi:10.1145/3357713.3384234.
[3] Kazuyuki Amano and Akira Maruoka. The potential of the approximation method. SIAM Journal on Computing, 33(2):433–447, January 2004. Preliminary version in FOCS ’96. doi:10.1137/s009753970138445x.
[4] A. E. Andreev. On a method for obtaining lower bounds for the complexity of individual monotone functions. Sov. Math., Dokl., 31:530–534, 1985.
[5] A. E. Andreev. A method for obtaining efficient lower bounds for monotone complexity. Algebra Logic, 26(1):1–18, 1987. doi:10.1007/BF01978380.
[6] Albert Atserias and Víctor Dalmau. A combinatorial characterization of resolution width. J. Comput. Syst. Sci., 74(3):323–334, 2008. doi:10.1016/j.jcss.2007.06.025.
[7] Paul Beame and Michael Whitmeyer. Multiparty communication complexity of collision finding. CoRR, abs/2411.07400, 2024. doi:10.48550/arXiv.2411.07400.
[8] Paul Beame and Michael Whitmeyer. Multiparty communication complexity of collision-finding and cutting planes proofs of concise pigeonhole principles. Technical report, Electronic Colloquium on Computational Complexity (ECCC), 2025. URL: https://eccc.weizmann.ac.il/report/2025/057.
[9] Tolson Bell, Suchakree Chueluecha, and Lutz Warnke. Note on sunflowers. Discret. Math., 344(7):112367, 2021. doi:10.1016/j.disc.2021.112367.
[10] Eli Ben-Sasson and Avi Wigderson. Short proofs are narrow - resolution made simple. J. ACM, 48(2):149–169, 2001. doi:10.1145/375827.375835.
[11] Christer Berg and Staffan Ulfberg. Symmetric approximation arguments for monotone lower bounds without sunflowers. Computational Complexity, 8(1):1–20, June 1999. doi:10.1007/s000370050017.
[12] Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, and Jan Johannsen. On the relative complexity of resolution refinements and cutting planes proof systems. SIAM J. Comput., 30(5):1462–1484, 2000. doi:10.1137/S0097539799352474.
[13] Jarosław Błasiok and Linus Meierhöfer. Hardness of clique approximation for monotone circuits, 2025. doi:10.48550/arXiv.2501.09545.
[14] Bruno Pasqualotto Cavalar. Private communication, 2025.
[15] Bruno Pasqualotto Cavalar, Mrinal Kumar, and Benjamin Rossman. Monotone circuit lower bounds from robust sunflowers. Algorithmica, 84(12):3655–3685, 2022. doi:10.1007/s00453-022-01000-3.
[16] Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett, Jakob Nordström, and Shuo Pang. Truly supercritical trade-offs for resolution, cutting planes, monotone circuits, and weisfeiler-leman. Technical report, Electronic Colloquium on Computational Complexity (ECCC), 2024. URL: https://eccc.weizmann.ac.il/report/2024/185.
[17] Susanna F. de Rezende, Mika Göös, and Robert Robere. Guest column: Proofs, circuits, and communication. ACM SIGACT News, 53(1):59–82, 2022. doi:10.1145/3532737.3532746.
[18] Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, and Robert Robere. KRW composition theorems via lifting. Comput. Complex., 33(1):4, April 2024. Preliminary version in FOCS ’20. doi:10.1007/s00037-024-00250-7.
[19] Susanna F. de Rezende, Or Meir, Jakob Nordstrom, Toniann Pitassi, Robert Robere, and Marc Vinyals. Lifting with simple gadgets and applications to circuit and proof complexity. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS ’20), November 2020. doi:10.1109/focs46700.2020.00011.
[20] Susanna F. de Rezende, Jakob Nordström, and Marc Vinyals. How limited interaction hinders real communication (and what it means for proof and circuit complexity). In Proceedings of the 57th IEEE Annual Symposium on Foundations of Computer Science (FOCS ’16), October 2016. doi:10.1109/focs.2016.40.
[21] Paul Feldman, Joel Friedman, and Nicholas Pippenger. Wide-sense nonblocking networks. SIAM J. Discret. Math., 1(2):158–173, 1988. doi:10.1137/0401018.
[22] Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov. Monotone circuit lower bounds from resolution. Theory of Computing, 16(13):1–30, 2020. Preliminary version in STOC ’18. doi:10.4086/toc.2020.v016a013.
[23] Mika Göös, Sajin Koroth, Ian Mertz, and Toniann Pitassi. Automating cutting planes is np-hard. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 68–77. ACM, 2020. doi:10.1145/3357713.3384248.
[24] Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. SIAM J. Comput., 47(6):2435–2450, 2018. doi:10.1137/16M1059369.
[25] Mika Göös, Toniann Pitassi, and Thomas Watson. Query-to-communication lifting for BPP. SIAM J. Comput., 49(4), 2020. doi:10.1137/17M115339X.
[26] Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov. Adventures in monotone complexity and TFNP. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS ’19), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1–38:19, January 2019. doi:10.4230/LIPIcs.ITCS.2019.38.
[27] Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. SIAM Journal on Computing, 45(5):1835–1869, October 2016. Preliminary version in STOC ’15. doi:10.1137/15M103145X.
[28] Danny Harnik and Ran Raz. Higher lower bounds on monotone size. In F. Frances Yao and Eugene M. Luks, editors, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 378–387. ACM, 2000. doi:10.1145/335305.335349.
[29] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bull. Am. Math. Soc., New Ser., 43(4):439–561, 2006. doi:10.1090/S0273-0979-06-01126-8.
[30] Pavel Hrubes and Pavel Pudlák. Random formulas, monotone circuits, and interpolation. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 121–131. IEEE Computer Society, 2017. doi:10.1109/FOCS.2017.20.
[31] Pavel Hrubes and Pavel Pudlák. A note on monotone real circuits. Inf. Process. Lett., 131:15–19, 2018. doi:10.1016/j.ipl.2017.11.002.
[32] Dmitry Itsykson and Artur Riazanov. Proof complexity of natural formulas via communication arguments. In Proceedings of the 36th Annual IEEE Conference on Computational Complexity (CCC ’21). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPICS.CCC.2021.3.
[33] Stasys Jukna. Finite limits and monotone computations: the lower bounds criterion. In Proceedings of the 12th Annual IEEE Conference on Computational Complexity (CCC ’97), pages 302–313, 1997. doi:10.1109/ccc.1997.612325.
[34] Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discret. Math., 3(2):255–265, 1990. doi:10.1137/0403021.
[35] Jan Krajícek. Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic. J. Symb. Log., 62(2):457–486, 1997. doi:10.2307/2275541.
[36] Jan Krajícek. Interpolation by a game. Math. Log. Q., 44:450–458, 1998. doi:10.1002/malq.19980440403.
[37] Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, and Jiapeng Zhang. Lifting with sunflowers. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 104:1–104:24. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ITCS.2022.104.
[38] Igor Carboni Oliveira. Unconditional lower bounds in complexity theory. PhD thesis, Columbia University, USA, 2015. doi:10.7916/D8ZP45KT.
[39] Toniann Pitassi and Robert Robere. Strongly exponential lower bounds for monotone computation. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC ’17), pages 1246–1255, June 2017. doi:10.1145/3055399.3055478.
[40] Pavel Pudlák. Lower bounds for resolution and cutting plane proofs and monotone computations. J. Symb. Log., 62(3):981–998, 1997. doi:10.2307/2275583.
[41] Pavel Pudlák. Proofs as games. Am. Math. Mon., 107(6):541–550, 2000. URL: http://www.jstor.org/stable/2589349.
[42] Anup Rao. Coding for Sunflowers. Discrete Anal., 2020:8, 2020. Id/No 2. doi:10.19086/da.11887.
[43] Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy. Comb., 19(3):403–435, 1999. doi:10.1007/s004930050062.
[44] A. A. Razborov. Lower bounds for the monotone complexity of some Boolean functions. Sov. Math., Dokl., 31:354–357, 1985.
[45] Alexander A. Razborov. Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic. Izvestiya: Mathematics, pages 205–227, February 1995. doi:10.1070/im1995v059n01abeh000009.
[46] Robert Robere. Unified lower bounds for monotone computation. PhD thesis, University of Toronto, Canada, 2018. URL: http://hdl.handle.net/1807/92007.
[47] Benjamin Rossman. The monotone complexity of k-clique on random graphs. SIAM J. Comput., 43(1):256–279, 2014. doi:10.1137/110839059.
[48] Janos Simon and Shi-Chun Tsai. On the bottleneck counting argument. Theoretical Computer Science, 237(1–2):429–437, April 2000. Preliminary version in CCC ’97. doi:10.1016/s0304-3975(99)00321-7.
[49] Dmitry Sokolov. Dag-like communication and its applications. In Proceedings of the 12th International Computer Science Symposium in Russia (CSR ’17), volume 10304 of Lecture Notes in Computer Science, pages 294–307. Springer, June 2017. doi:10.1007/978-3-319-58747-9_26.
[50] Dmitry Sokolov. Random (log $n$ )-cnf are hard for cutting planes (again). In Proceedings of the 56th Annual ACM SIGACT Symposium on Theory of Computing (STOC ’24), pages 2008–2015, 2024. doi:10.1145/3618260.3649636.
[51] Terence Tao. The sunflower lemma via shannon entropy, 2020. URL: https://terrytao.wordpress.com/2020/07/20/the-sunflower-lemma-via-shannon-entropy/.
[52] Éva Tardos. The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica, 8(1):141–142, March 1988. doi:10.1007/bf02122563.
[53] Ingo Wegener. The complexity of Boolean functions. Wiley-Teubner, 1987. URL: http://ls2-www.cs.uni-dortmund.de/monographs/bluebook/.

[bib.bib1] [1] N. Alon and R. B. Boppana. The monotone circuit complexity of Boolean functions. Combinatorica, 7:1–22, 1987. doi:10.1007/BF02579196.

[bib.bib2] [2] Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang. Improved bounds for the sunflower lemma. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 624–630. ACM, 2020. doi:10.1145/3357713.3384234.

[bib.bib3] [3] Kazuyuki Amano and Akira Maruoka. The potential of the approximation method. SIAM Journal on Computing, 33(2):433–447, January 2004. Preliminary version in FOCS ’96. doi:10.1137/s009753970138445x.

[bib.bib4] [4] A. E. Andreev. On a method for obtaining lower bounds for the complexity of individual monotone functions. Sov. Math., Dokl., 31:530–534, 1985.

[bib.bib5] [5] A. E. Andreev. A method for obtaining efficient lower bounds for monotone complexity. Algebra Logic, 26(1):1–18, 1987. doi:10.1007/BF01978380.

[bib.bib6] [6] Albert Atserias and Víctor Dalmau. A combinatorial characterization of resolution width. J. Comput. Syst. Sci., 74(3):323–334, 2008. doi:10.1016/j.jcss.2007.06.025.

[bib.bib7] [7] Paul Beame and Michael Whitmeyer. Multiparty communication complexity of collision finding. CoRR, abs/2411.07400, 2024. doi:10.48550/arXiv.2411.07400.

[bib.bib8] [8] Paul Beame and Michael Whitmeyer. Multiparty communication complexity of collision-finding and cutting planes proofs of concise pigeonhole principles. Technical report, Electronic Colloquium on Computational Complexity (ECCC), 2025. URL: https://eccc.weizmann.ac.il/report/2025/057.

[bib.bib9] [9] Tolson Bell, Suchakree Chueluecha, and Lutz Warnke. Note on sunflowers. Discret. Math., 344(7):112367, 2021. doi:10.1016/j.disc.2021.112367.

[bib.bib10] [10] Eli Ben-Sasson and Avi Wigderson. Short proofs are narrow - resolution made simple. J. ACM, 48(2):149–169, 2001. doi:10.1145/375827.375835.

[bib.bib11] [11] Christer Berg and Staffan Ulfberg. Symmetric approximation arguments for monotone lower bounds without sunflowers. Computational Complexity, 8(1):1–20, June 1999. doi:10.1007/s000370050017.

[bib.bib12] [12] Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, and Jan Johannsen. On the relative complexity of resolution refinements and cutting planes proof systems. SIAM J. Comput., 30(5):1462–1484, 2000. doi:10.1137/S0097539799352474.

[bib.bib13] [13] Jarosław Błasiok and Linus Meierhöfer. Hardness of clique approximation for monotone circuits, 2025. doi:10.48550/arXiv.2501.09545.

[bib.bib14] [14] Bruno Pasqualotto Cavalar. Private communication, 2025.

[bib.bib15] [15] Bruno Pasqualotto Cavalar, Mrinal Kumar, and Benjamin Rossman. Monotone circuit lower bounds from robust sunflowers. Algorithmica, 84(12):3655–3685, 2022. doi:10.1007/s00453-022-01000-3.

[bib.bib16] [16] Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett, Jakob Nordström, and Shuo Pang. Truly supercritical trade-offs for resolution, cutting planes, monotone circuits, and weisfeiler-leman. Technical report, Electronic Colloquium on Computational Complexity (ECCC), 2024. URL: https://eccc.weizmann.ac.il/report/2024/185.

[bib.bib17] [17] Susanna F. de Rezende, Mika Göös, and Robert Robere. Guest column: Proofs, circuits, and communication. ACM SIGACT News, 53(1):59–82, 2022. doi:10.1145/3532737.3532746.

[bib.bib18] [18] Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, and Robert Robere. KRW composition theorems via lifting. Comput. Complex., 33(1):4, April 2024. Preliminary version in FOCS ’20. doi:10.1007/s00037-024-00250-7.

[bib.bib19] [19] Susanna F. de Rezende, Or Meir, Jakob Nordstrom, Toniann Pitassi, Robert Robere, and Marc Vinyals. Lifting with simple gadgets and applications to circuit and proof complexity. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS ’20), November 2020. doi:10.1109/focs46700.2020.00011.

[bib.bib20] [20] Susanna F. de Rezende, Jakob Nordström, and Marc Vinyals. How limited interaction hinders real communication (and what it means for proof and circuit complexity). In Proceedings of the 57th IEEE Annual Symposium on Foundations of Computer Science (FOCS ’16), October 2016. doi:10.1109/focs.2016.40.

[bib.bib21] [21] Paul Feldman, Joel Friedman, and Nicholas Pippenger. Wide-sense nonblocking networks. SIAM J. Discret. Math., 1(2):158–173, 1988. doi:10.1137/0401018.

[bib.bib22] [22] Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov. Monotone circuit lower bounds from resolution. Theory of Computing, 16(13):1–30, 2020. Preliminary version in STOC ’18. doi:10.4086/toc.2020.v016a013.

[bib.bib23] [23] Mika Göös, Sajin Koroth, Ian Mertz, and Toniann Pitassi. Automating cutting planes is np-hard. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 68–77. ACM, 2020. doi:10.1145/3357713.3384248.

[bib.bib24] [24] Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. SIAM J. Comput., 47(6):2435–2450, 2018. doi:10.1137/16M1059369.

[bib.bib25] [25] Mika Göös, Toniann Pitassi, and Thomas Watson. Query-to-communication lifting for BPP. SIAM J. Comput., 49(4), 2020. doi:10.1137/17M115339X.

[bib.bib26] [26] Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov. Adventures in monotone complexity and TFNP. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS ’19), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1–38:19, January 2019. doi:10.4230/LIPIcs.ITCS.2019.38.

[bib.bib27] [27] Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. SIAM Journal on Computing, 45(5):1835–1869, October 2016. Preliminary version in STOC ’15. doi:10.1137/15M103145X.

[bib.bib28] [28] Danny Harnik and Ran Raz. Higher lower bounds on monotone size. In F. Frances Yao and Eugene M. Luks, editors, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 378–387. ACM, 2000. doi:10.1145/335305.335349.

[bib.bib29] [29] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bull. Am. Math. Soc., New Ser., 43(4):439–561, 2006. doi:10.1090/S0273-0979-06-01126-8.

[bib.bib30] [30] Pavel Hrubes and Pavel Pudlák. Random formulas, monotone circuits, and interpolation. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 121–131. IEEE Computer Society, 2017. doi:10.1109/FOCS.2017.20.

[bib.bib31] [31] Pavel Hrubes and Pavel Pudlák. A note on monotone real circuits. Inf. Process. Lett., 131:15–19, 2018. doi:10.1016/j.ipl.2017.11.002.

[bib.bib32] [32] Dmitry Itsykson and Artur Riazanov. Proof complexity of natural formulas via communication arguments. In Proceedings of the 36th Annual IEEE Conference on Computational Complexity (CCC ’21). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPICS.CCC.2021.3.

[bib.bib33] [33] Stasys Jukna. Finite limits and monotone computations: the lower bounds criterion. In Proceedings of the 12th Annual IEEE Conference on Computational Complexity (CCC ’97), pages 302–313, 1997. doi:10.1109/ccc.1997.612325.

[bib.bib34] [34] Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discret. Math., 3(2):255–265, 1990. doi:10.1137/0403021.

[bib.bib35] [35] Jan Krajícek. Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic. J. Symb. Log., 62(2):457–486, 1997. doi:10.2307/2275541.

[bib.bib36] [36] Jan Krajícek. Interpolation by a game. Math. Log. Q., 44:450–458, 1998. doi:10.1002/malq.19980440403.

[bib.bib37] [37] Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, and Jiapeng Zhang. Lifting with sunflowers. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 104:1–104:24. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ITCS.2022.104.

[bib.bib38] [38] Igor Carboni Oliveira. Unconditional lower bounds in complexity theory. PhD thesis, Columbia University, USA, 2015. doi:10.7916/D8ZP45KT.

[bib.bib39] [39] Toniann Pitassi and Robert Robere. Strongly exponential lower bounds for monotone computation. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC ’17), pages 1246–1255, June 2017. doi:10.1145/3055399.3055478.

[bib.bib40] [40] Pavel Pudlák. Lower bounds for resolution and cutting plane proofs and monotone computations. J. Symb. Log., 62(3):981–998, 1997. doi:10.2307/2275583.

[bib.bib41] [41] Pavel Pudlák. Proofs as games. Am. Math. Mon., 107(6):541–550, 2000. URL: http://www.jstor.org/stable/2589349.

[bib.bib42] [42] Anup Rao. Coding for Sunflowers. Discrete Anal., 2020:8, 2020. Id/No 2. doi:10.19086/da.11887.

[bib.bib43] [43] Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy. Comb., 19(3):403–435, 1999. doi:10.1007/s004930050062.

[bib.bib44] [44] A. A. Razborov. Lower bounds for the monotone complexity of some Boolean functions. Sov. Math., Dokl., 31:354–357, 1985.

[bib.bib45] [45] Alexander A. Razborov. Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic. Izvestiya: Mathematics, pages 205–227, February 1995. doi:10.1070/im1995v059n01abeh000009.

[bib.bib46] [46] Robert Robere. Unified lower bounds for monotone computation. PhD thesis, University of Toronto, Canada, 2018. URL: http://hdl.handle.net/1807/92007.

[bib.bib47] [47] Benjamin Rossman. The monotone complexity of k-clique on random graphs. SIAM J. Comput., 43(1):256–279, 2014. doi:10.1137/110839059.

[bib.bib48] [48] Janos Simon and Shi-Chun Tsai. On the bottleneck counting argument. Theoretical Computer Science, 237(1–2):429–437, April 2000. Preliminary version in CCC ’97. doi:10.1016/s0304-3975(99)00321-7.

[bib.bib49] [49] Dmitry Sokolov. Dag-like communication and its applications. In Proceedings of the 12th International Computer Science Symposium in Russia (CSR ’17), volume 10304 of Lecture Notes in Computer Science, pages 294–307. Springer, June 2017. doi:10.1007/978-3-319-58747-9_26.

[bib.bib50] [50] Dmitry Sokolov. Random (log $n$ )-cnf are hard for cutting planes (again). In Proceedings of the 56th Annual ACM SIGACT Symposium on Theory of Computing (STOC ’24), pages 2008–2015, 2024. doi:10.1145/3618260.3649636.

[bib.bib51] [51] Terence Tao. The sunflower lemma via shannon entropy, 2020. URL: https://terrytao.wordpress.com/2020/07/20/the-sunflower-lemma-via-shannon-entropy/.

[bib.bib52] [52] Éva Tardos. The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica, 8(1):141–142, March 1988. doi:10.1007/bf02122563.

[bib.bib53] [53] Ingo Wegener. The complexity of Boolean functions. Wiley-Teubner, 1987. URL: http://ls2-www.cs.uni-dortmund.de/monographs/bluebook/.

$\displaystyle\|Y\|$	$\displaystyle\leq\|\{y\in(\Sigma^{m})^{N}:\forall x\in X,y[x]\neq\beta_{x}\}\|$	(13)
	$\displaystyle\leq\|\{y\in(\Sigma^{m})^{N}:\forall x\in X,y[x]\neq 1^{N}\}\|$	(14)
	$\displaystyle=\|\Sigma\|^{mN}\cdot\Pr_{y\sim\mathcal{U}(\Sigma^{mN})}[\forall x% \in X,y[x]\neq 1^{N}]$	(15)
	$\displaystyle=\|\Sigma\|^{mN}\cdot\Pr_{y\sim\mathcal{D}_{1}(\{0,1\}^{mN},p)}[% \forall x\in X,y[x]\neq 1^{N}]$	(16)
	$\displaystyle\leq\|\Sigma\|^{mN}\cdot\epsilon\,,$	(17)