Searching for Falsified Clause in Random (log{n})-CNFs Is Hard for Randomized Communication

Riazanov, Artur; Sofronova, Anastasia; Sokolov, Dmitry; Yuan, Weiqiang

doi:10.4230/LIPIcs.APPROX/RANDOM.2025.64

Searching for Falsified Clause in Random $(\log{n})$ -CNFs Is Hard for Randomized Communication

Artur Riazanov

EPFL, Lausanne, Switzerland Anastasia Sofronova

EPFL, Lausanne, Switzerland Dmitry Sokolov

EPFL, Lausanne, Switzerland Weiqiang Yuan

EPFL, Lausanne, Switzerland

Abstract

We show that for a randomly sampled unsatisfiable $O(\log n)$ -CNF over $n$ variables the randomized two-party communication cost of finding a clause falsified by the given variable assignment is linear in $n$ .

Keywords and phrases:

communication complexity, proof complexity, random CNF

Category:

RANDOM

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Communication complexity

Funding:

This project was supported by the Swiss State Secretariat for Education, Research and Innovation (SERI) under contract number MB22.00026.

DOI:

10.4230/LIPIcs.APPROX/RANDOM.2025.64

Event:

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Editors:

Alina Ene and Eshan Chattopadhyay

Series and Publisher:

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

1 Introduction

This paper studies the communication complexity of Falsified Clause Search Problem.

Definition 1 ([31]).

Let $X, Y$ be two disjoint sets of boolean variables and $\varphi$ be a CNF formula over the variables $X\sqcup Y$ . We define Falsified Clause Search Problem or $\mathrm{Search}_{\varphi}$ associated with formula $\varphi$ in the following way:

input:

a pair $(x,y)\in\{0,1\}^{X}\times\{0,1\}^{Y}$ ;
output:

a clause $C\in\varphi$ that is violated by the input $(x,y)$ .

Communication lower bounds for search problems have applications in many areas of complexity theory. We consider two areas that are the most relevant and explain the applicability of communication lower bounds.

Proof complexity.

This area of complexity theory studies how hard it is to prove that a given formula $\varphi$ is unsatisfiable; in other words, what is the length of the shortest proof in a certain proof system. Lower bounds for the proof systems often correspond to lower bounds on a run-time of SAT-solvers, and there are intricate connections to other areas of complexity theory, such as, for example, circuit complexity.

There is a general framework for obtaining lower bounds on the length of the shortest proofs via communication. Suppose that, for an unsatisfiable CNF formula $\varphi$ , we divide the variables into two disjoint groups $X$ and $Y$ in an arbitrary way. For a fixed proof system $\mathfrak{C}$ we can try to transform efficient proof of $\varphi$ into an efficient communication protocol for $\mathrm{Search}_{\varphi}$ . A lower bound on the communication complexity of $\mathrm{Search}_{\varphi}$ then implies a lower bound on the length of a proof of $\varphi$ in $\mathfrak{C}$ .

This framework seems to originate from [31]. Following this reduction, lower bounds for many different proof systems were obtained, for example: tree-like Cutting Planes [26, 25, 10, 6], tree-like Threshold proof system [5], tree-like $\mathrm{Res}(\oplus)$ [28], etc. [25, 21]. Depending on the communication model, even dag-like proofs can be analyzed via this framework [30, 35, 24, 12, 13, 40].

The lower bounds that can be achieved via this technique depend on the power of the communication model: the more powerful model we consider, the bigger class of proof systems we get the lower bound for. The choice of the formula $\varphi$ is important here as well, in a sense that we need to be able to show the lower bound on the communication complexity of $\mathrm{Search}_{\varphi}$ . Typically, $\varphi$ is artificially built for this purpose. In this paper, we show a communication lower bound for the natural class of formulas (without usage of ad hoc constructions) that is a candidate for being hard for all propositional proof systems.

Circuit complexity.

Natural embedding of $\mathrm{Search}_{\varphi}$ into a monotone Karchmer–Wigderson relation [29, 36] gives us the opportunity to use it for proving lower bounds for the monotone models of computation. From communication lower bounds, strong results are known for monotone formulas [37], monotone circuits [13, 32], monotone span programs [37, 34], etc. Communication is also the main instrument for showing separation between those models [34, 17], and trade-off results [9, 19]. These type of results are based on ad hoc constructions of the formulas $\varphi$ . Namely, $\varphi$ is designed in order to able to show communication lower bound.

1.1 Random CNF

To be more precise we start with the definition of random CNF formulas.

Definition 2.

Let $\mathfrak{F}(m,n,\Delta)$ denote the distribution of random $\Delta$ -CNF on $n$ variables obtained by sampling $m$ clauses (out of the $\binom{n}{\Delta}2^{\Delta}$ possible clauses) uniformly at random with repetitions.

The famous result of Chvátal–Szemerédi says that if we pick a formula from this distribution with the proper parameters, the resulting formula will be unsatisfiable with high probability.

Theorem 3 (Chvátal–Szemerédi, [7]).

For any $\Delta\geq 3$ whp $\bm{\varphi}\sim\mathfrak{F}(m,n,\Delta)$ is unsatisfiable if $m\geq\ln 2\cdot 2^{\Delta}n$ .

These types of distributions appear not only in most of the areas in computer science, but in general mathematics and physics as well [33]. An interesting application is due to Feige [11], who conjectured the following statement: no polynomial time algorithm may prove whp the unsatisfiability of a random $O(1)$ -CNF formula with arbitrary large constant clause density. Assuming Feige’s conjecture, it is known that some problems are hard to approximate: vertex covering, PAC learning DNFs [8], etc.

As a candidate to be hard to refute in all proof systems, random CNFs are actively studied and lower bounds are known for many different proof systems [23, 4, 3, 1, 38]. Recent developments in this direction utilize the connection between proof complexity of $\varphi$ and communication complexity of $\mathrm{Search}_{\varphi}$ . In particular, lower bounds for the Cutting Planes proofs of random $O(\log n)$ -CNF [24, 12, 40] follow this strategy. However, these results only consider lower bounds on deterministic dag-like communication complexity of $\mathrm{Search}_{\varphi}$ based on random $O(\log n)$ -CNF.

In this paper, we analyse the randomized tree-like communication of this problem that is incomparable with deterministic dag-like communication. This is a natural problem in a natural model, which also provides a way to explore how techniques used for structured formulas might extend to more typical instances like random CNFs. The main result is the following.

Theorem 4.

Let $c>0$ be a large enough constant, $n>0,\Delta\geq c\log n,m=O(n2^{\Delta})$ . If $\bm{\varphi}\sim\mathfrak{F}(m,n,\Delta)$ and $\bm{X},\bm{Y}\subseteq[n]$ is a partition of variables that is taken uniformly at random, then whp over choice of $\bm{\varphi}$ and partition $\bm{X},\bm{Y}$ the randomized communication complexity of $\mathrm{Search}_{\bm{\varphi}}$ is $\Omega(n)$ .

1.2 Prior Results and Technique

For several types of formulas $\varphi$ , the randomized communication complexity of $\mathrm{Search}_{\varphi}$ is well-studied. The approach for proving such bounds is the reduction of Unique Disjointness function to $\mathrm{Search}_{\varphi}$ . The main success in this direction is the reduction based on critical block sensitivity [25, 21], we also include some earlier results, though there is some difference in the technique [5]. More precisely, for this technique one should assume that $\varphi=\psi\circ g$ (we take some formula $\psi$ and, in place of each variable, we substitute a carefully chosen gadget $g$ with fresh variables). Assuming that $\mathrm{Search}_{\psi}$ has critical block sensitivity $m$ (that is a generalization of the block sensitivity measure), it is possible to reduce instances of unique disjointness of size $\mathrm{poly}(m)$ to $\mathrm{Search}_{\varphi}$ .

The general framework for working with such formulas of $\psi\circ g$ is called lifting, and the idea is to “lift” the hardness of $\psi$ with respect to another complexity measure to communication complexity via gadget. Lifting can be based on the other complexity measures as well. For example, it can also be implemented for randomized decision tree complexity instead of critical block sensitivity [16]; however, this method requires the lower bound on the randomized decision tree complexity, which might be non-trivial, especially in case of $\mathrm{Search}_{\varphi}$ problem. Such lower bound is known for Tseitin formulas [15], together with [16] it yields the lower bound for randomized communication complexity of $\mathrm{Search}$ for Tseitin formulas lifted by Inner Product.

The notable exception here is the lower bound on $\mathrm{Search}$ problem for Binary Pigeonhole Principle (BPHP) [27]. These formulas are not lifted, however the proof is also the reduction of Unique Disjointness to the $\mathrm{Search}$ problem. This reduction based on the inner symmetry of BPHP.

A different kind of proof of a $\mathrm{Search}_{\varphi}$ lower bound was given by Yang and Zhang [42] (based on [41, 42]), who prove a lower bound for a weak version of BPHP. In contrast to the previous works this one is not a reduction from Unique Disjointness. Instead, they directly apply the structure versus randomness framework from the lifting literature [18, 16] to the potential protocol that computes $\mathrm{Search}_{\varphi}$ .

Our proof of Theorem 4 combines the approach of [18, 16, 42] with the analysis of expander graphs via closure argument that was developed for proof complexity purposes in [3, 2]. However, we use the iterative construction of the closure from [39]. In part, this is also inspired by [20].

More precisely, the proof of our result is based on the following steps.

1.

Following [24, 12, 40] we divide variables between Alice and Bob uniformly at random.
2.

Following the line of work on lifting of randomized decision trees [18, 16, 42, 14] we show that every communication protocol can be converted into a more structured one, a so-called subcube-like protocol. In such a communication protocol, each rectangle is a product of two sets with some bits fixed and the remaining pseudorandom.
3.

Due to the nature of our random CNFs, the invariant that all clauses contain pseudorandom variables is not strong enough on its own. $\mathrm{Search}$ problem still might become trivial early on in communication protocol; for example, if the contradiction could be narrowed down to a small set of clauses. To avoid this problem, we use the closure trick [3, 2, 39, 20], that allows us to maintain expansion property on the pseudorandom part of the graph.
4.

Following [14], we show that the number of fixed bits in each rectangle is at most $O(d/\varepsilon)$ if we allow error $\varepsilon$ , where $d$ is the communication complexity of the original protocol.

In addition, we show the better error bound dependency on the protocol depth $d$ than in [14]. We give a more refined analysis of the conversion to the subcube-like protocols. More precisely, we show that the number of fixed bits in each rectangle is $O(d)$ even when we allow for the $\exp(-d)$ error.

2 Notation and Tools

We denote the standard binary entropy function by $\operatorname{H}(p)\coloneqq p\log(1/p)+(1-p)\log(1/(1-p))$ .

Definition 5.

A bipartite graph $G=(L,R,E)$ is called an $(r,\Delta,\alpha\Delta)$ -expander, if all vertices in $L$ have degree at most $\Delta$ and for any set $S\subseteq L$ such that $|S|\leq r$ it holds that $|N(S)|\geq\alpha\Delta|S|$ , where $N_{G}(S)$ denotes the set of neighbours of $S$ in $G$ (we omit the subscript if the graph is clear from the context).

With a CNF formula $\varphi$ over $n$ variables and with $m$ clauses we associate a graph $G_{\varphi}\coloneqq([m],[n],E)$ in a natural way: $(i,j)\in E$ iff the $i$ -th clause contains the $j$ -th variable. The following Lemma gives us some useful properties of underlying graphs of random CNFs. It follows from a standard computation, which was featured, for example, in [40, Lemma A.2].

Lemma 6.

Let $n>0$ , $\eta>0$ be an arbitrary constant, $\Delta=c\log{n}$ , for a large enough constant $c$ depends on $\eta$ , $m=O(n2^{\Delta})$ . Let $G\coloneqq([m],[n],E)$ be a bipartite graph, such that each $i\in[m]$ choses $\Delta$ neighbours uniformly at random over $\binom{n}{\Delta}$ possibilities. Then $G$ is an $(r,\Delta,(1-\eta)\Delta)$ -expander for $r=\Omega\left(n/\Delta\right)$ .

Instead of working directly with randomised communication, we use the equivalent characterisation through distributional communication complexity. That is, we prove a lower bound against deterministic protocols that achieve error $\varepsilon$ with respect to a certain distribution on inputs (here we use uniform distribution), and a lower bound against randomised protocols that achieve error $\varepsilon$ follows. Below, “communication protocol” refers to a deterministic communication protocol.

3 Refuting Bipartite CNFs

In this section we mainly prove a special “bipartite” case of Theorem 4. We show in Section 3.1 that it actually implies the general case.

Theorem 7.

Let $\alpha>0$ be an absolute constant. Let $G_{1}\coloneqq([m],[n],E_{1}),G_{2}\coloneqq([m],[n],E_{2})$ be two $(r,\Delta,\alpha\Delta)$ -expanders, and $X,Y\coloneqq\{0,1\}^{n}$ . For each $i\in[m]$ , let $C_{i}$ be a disjunction of variables in $\{x_{j}\mid j\in N_{G_{1}}(i)\}\cup\{y_{j}\mid j\in N_{G_{2}}(i)\}$ with arbitrary signs. Then for every communication protocol $\Pi\colon\{0,1\}^{n}\times\{0,1\}^{n}\to[m]$ of depth $d$ at most $O(\Delta r)$ :

\Pr_{\begin{subarray}{c}(\bm{x},\bm{y})\sim X\times Y\\ \bm{i}\sim\Pi(\bm{x},\bm{y})\end{subarray}}[C_{\bm{i}}(\bm{x},\bm{y})=0]\leq d% \cdot 2^{-\Omega(\Delta)}+\exp(-d).

This section is organized as follows. In Section 3.1, we derive Theorem 4 from Theorem 7. In Section 3.2, we formally define subcube-like protocols and provide necessary tools. In Section 3.3, we give a more refined analysis of the conversion from general protocols to subcube-like ones in [14]. In Section 3.4, we show the hardness of $\mathrm{Search}_{\varphi}$ against subcube-like protocols when the underlying graphs are good expanders. Finally, in Section 3.5, we put everything together and derive Theorem 7.

3.1 Deriving Theorem 4 from Theorem 7

The main part of the argument that reduces the general case to the bipartite is a clean-up lemma essentially saying that incurring a small error we can treat the general case as bipartite. Similar arguments have been made in [24, 12, 40].

Let $\varphi=\bigwedge_{i\in[n]}C_{i}$ be a $\Delta$ -CNF with the set of variables $[n]$ . Let $A\sqcup B=[n]$ be a partition of the variables. Let $G_{A}\coloneqq([m],A,E_{A})$ and $G_{B}\coloneqq([m],B,E_{B})$ be the graphs with edges connecting a clause with all variables from one of the sets mentioned in it. Let $\textsc{Error}_{A}\subseteq[m]$ and $\textsc{Error}_{B}\subseteq[m]$ be the sets of clauses with degree exceeding $(1-\delta)\Delta$ in $G_{A}$ and $G_{B}$ respectively. It means that clauses from $[m]\smallsetminus(\textsc{Error}_{A}\cup\textsc{Error}_{B})$ have at least $\delta\Delta$ variables from $A$ and $B$ . We then say that $(A,B)$ is $\delta$ -good partition for $\varphi$ if

1.

$\Pr\limits_{\bm{x}\sim\{0,1\}^{A}}[\forall i\in\textsc{Error}_{A}\text{ we % have }C_{i}(\bm{x},\cdot)\equiv 1]\geq 1-2^{-\Omega(\Delta)}$ .
2.

$\Pr\limits_{\bm{y}\sim\{0,1\}^{B}}[\forall i\in\textsc{Error}_{B}\text{ we % have }C_{i}(\cdot,\bm{y})\equiv 1]\geq 1-2^{-\Omega(\Delta)}$ .
3.

$G_{A}-\textsc{Error}_{A}-\textsc{Error}_{B}$ and $G_{B}-\textsc{Error}_{A}-\textsc{Error}_{B}$ are $(r,\Delta,\delta\Delta/2)$ -expanders, where $r=\Omega(n/\Delta)$ .

In this definition we assume that $\delta$ is an absolute constant and hidden constants depend on it.

Lemma 8.

Let $\bm{\varphi}\sim\mathfrak{F}(m,n,\Delta)$ with $\Delta=c\log n$ and $m=\alpha 2^{\Delta}n$ , where $c,\alpha>0$ are constants, and $c\geq 40$ . Let $\bm{X},\bm{Y}$ be a uniformly random partition of $[n]$ . Then whp $(\bm{X},\bm{Y})$ is a $\delta$ -good partition for $\bm{\varphi}$ for any $\delta\leq 1/10$ .

We defer the proof of this lemma to Appendix A.

Proof of Theorem 4.

Applying Lemma 8, we get that the variable partition $\bm{X}\sqcup\bm{Y}=[n]$ is $1/10$ -good wrt $\bm{\varphi}$ . Let $G_{1}\coloneqq G_{\bm{X}}-\textsc{Error}_{\bm{X}}-\textsc{Error}_{\bm{Y}}$ , $G_{2}\coloneqq G_{\bm{Y}}-\textsc{Error}_{\bm{X}}-\textsc{Error}_{\bm{Y}}$ . Note that the left parts of these graphs have equal size. We can add dummy variables to the right parts of these graphs to make them equal as well for the simplicity of notation.

By Lemma 8, the probability over $(\bm{x},\bm{y})\sim\{0,1\}^{\bm{X}}\times\{0,1\}^{\bm{Y}}$ for the $\textsc{Error}_{\bm{X}}$ or $\textsc{Error}_{\bm{Y}}$ to not be immediately satisfied is $2^{-\Omega(\Delta)}$ . This means that if we consider a protocol for the problem $\mathrm{Search}_{\bm{\varphi}}$ for the variable partition $\bm{X}\sqcup\bm{Y}$ with the probability of success $\varepsilon$ , we can reinterpret it as a protocol for $G_{1}$ and $G_{2}$ with the probability of success at least $\varepsilon-2^{-\Omega(\Delta)}$ .

We apply Theorem 7 with $\alpha\coloneqq\frac{1}{20}$ . Since $r\Delta$ can be as large as $\Omega(n)$ by Lemma 6, we can pick the constants depending on $\alpha$ such that the probability from Theorem 7 is less than $\frac{1}{100}$ . Then the probability of success for the problem from Theorem 4 is less than $\frac{1}{100}+2^{-\Omega(\Delta)}$ , and the theorem follows. $\hfill\blacktriangleleft$

3.2 Density Restoring Machinery

Every communication protocol $\Pi$ can be seen as a tree (not necessarily binary). Let $\mathcal{N}(\Pi)$ denote the set of all nodes in $\Pi$ . Each node $v\in\mathcal{N}(\Pi)$ is associated with a rectangle, denoted $R_{v}=X_{v}\times Y_{v}$ .

Definition 9 (Min-entropy).

For a random variable $\bm{x}$ , let $\textbf{H}_{\infty}(\bm{x})=\min_{x}\log{\frac{1}{\Pr[\bm{x}=x]}}$ .

Definition 10 (Spread variables).

Let $\bm{x}\in\{0,1\}^{n}$ be a random boolean vector. We say $\bm{x}$ is $\gamma$ -spread if for every $I\subseteq[n]$ we have $\textbf{H}_{\infty}(\bm{x}_{I})\geq\gamma|I|$ .

Definition 11 (Structured variables).

Let $\bm{x}\in\{0,1\}^{n}$ be a random boolean vector and $I\subseteq[n]$ . We say $\bm{x}$ is $(I,\gamma)$ -structured if there exists some $a_{I}\in\{0,1\}^{I}$ such that

$\blacksquare$

$\Pr[\bm{x}_{I}=a_{I}]=1$ ;
$\blacksquare$

$\bm{x}_{[m]\smallsetminus I}$ is $\gamma$ -spread.

Definition 12 (Subcube-like rectangle).

A rectangle $R=X\times Y\subseteq\{0,1\}^{n}\times\{0,1\}^{n}$ is $\gamma$ -subcube-like with respect to $(I,J)$ where $I,J\subseteq[n]$ if $\bm{x}\sim X$ is $(I,\gamma)$ -structured and $\bm{y}\sim Y$ is $(J,\gamma)$ -structured. In which case, we use $\textsf{fix}(X)\coloneqq I$ and $\textsf{fix}(Y)\coloneqq J$ to denote the fixed part of $X$ and $Y$ respectively.

Definition 13 (Subcube-like protocols [14]).

A communication protocol $\Pi\colon\{0,1\}^{n}\times\{0,1\}^{n}\to S$ is $\gamma$ -subcube-like if for every node $v\in\mathcal{N}(\Pi)$ in the protocol tree, $R_{v}$ is $\gamma$ -subcube-like.

Definition 14 (Codimension).

The codimension of a subcube-like rectangle $R=X\times Y$ is defined as the total number of fixed positions in $X$ and $Y$ , denoted $\mathrm{codim}(R)\coloneqq|\textsf{fix}(X)|+|\textsf{fix}(Y)|$ . The codimension of a subcube-like protocol $\Pi$ is the maximum codimension of subcube-like rectangles associated with any nodes in the protocol tree of $\Pi$ , denoted $\mathrm{codim}(\Pi)\coloneqq\max_{v\in\mathcal{N}(\Pi)}\mathrm{codim}(R_{v})$ .

Lemma 15 (Density Restoring Partition [22]).

Let $\bm{x}\in\{0,1\}^{n}$ be a random boolean vector with support $X\subseteq\{0,1\}^{n}$ and $0<\gamma<1$ be a fixed parameter. There exists a partition

X=X^{1}\sqcup X^{2}\sqcup X^{3}\cdots\sqcup X^{r}

such that for each $j\in[r]$ , $\bm{x}\mid\bm{x}\in X^{j}$ is $(I^{j},\gamma)$ -structured with respect to some $I^{j}\subseteq[n]$ .

Moreover, if we denote $p^{\geq j}\coloneqq\Pr[\bm{x}\in X^{j}\sqcup\cdots\sqcup X^{\ell}]$ , then it holds that:

\textbf{H}_{\infty}(\bm{x}_{[m]\smallsetminus I^{j}}\mid\bm{x}\in X^{j})\geq% \textbf{H}_{\infty}(\bm{x})-\gamma|I^{j}|-\log(1/p^{\geq j}).

3.3 Subcube-like protocols from general protocols

Göös et al. [14] show how to convert an arbitrary communication protocol into a subcube-like one. Specifically, they prove the following.

Lemma 16 ([14]).

Let $\Pi$ be a communication protocol of depth $d$ and $\varepsilon>0$ . There exists a subcube-like protocol $\tilde{\Pi}$ of codimension $\mathrm{codim}(\tilde{\Pi})=O(d/\varepsilon)$ such that

\Pr_{\bm{x},\bm{y}}[\Pi(\bm{x},\bm{y})\neq\tilde{\Pi}(\bm{x},\bm{y})]\leq\varepsilon.

Their bound is tight in the constant-error regime. However, it degenerates when $\varepsilon=O(d/n)$ .

In this subsection, we give a more refined analysis of the reduction in [14], which makes the bound applicable in the inverse polynomial error regime (when $d=\Omega(\log n)$ ). We remark that such an analysis has been implicitly provided in [22].

Lemma 17.

Let $\Pi$ be a communication protocol of depth $d$ . There exists a $\gamma$ -subcube-like protocol $\tilde{\Pi}$ of codimension $\mathrm{codim}(\tilde{\Pi})=\frac{7}{1-\gamma}\cdot d$ such that

\Pr_{\bm{x},\bm{y}}[\Pi(\bm{x},\bm{y})\neq\tilde{\Pi}(\bm{x},\bm{y})]\leq\exp(% -d).

We include a simplified version of the algorithm for such conversion from [14] for completeness. This algorithm simulates a subcube-like protocol $\Pi^{\prime}$ on an input $(x,y)$ , given a general protocol $\Pi$ .

Algorithm 2 (simplified) conversion from [14].

Proof.

Let $\Pi^{\prime}$ be as given by Algorithm 2 in [14]. More precisely, let the protocol tree of $\Pi^{\prime}$ consist all the possible configurations at the end of each iteration plus the initial one as the root (so the tree is not necessarily binary). Observe that $\Pi^{\prime}$ has depth $d$ , though may have much larger communication complexity.

For any $x,y\in\{0,1\}^{n}$ , we have $\Pi(x,y)=\Pi^{\prime}(x,y)$ . It suffices to show $\Pr_{\bm{x},\bm{y}}[\mathrm{codim}(R(\bm{x},\bm{y}))>\frac{7}{1-\gamma}\cdot d% ]\leq\exp(-d)$ , where $R(x,y)$ is the unique rectangle associated with the leaves of $\Pi$ that contains $(x,y)$ . The desired $\tilde{\Pi}$ can then be obtained by shaving all the nodes in the protocol tree of $\Pi^{\prime}$ associated with a rectangle of codimension greater than $\frac{7}{1-\gamma}\cdot d$ .

For each node $v\in\mathcal{N}(\Pi^{\prime})$ , define the entropy deficiency of $v$ as

\textbf{D}_{\infty}(v)\coloneqq\textbf{D}_{\infty}(X_{v})+\textbf{D}_{\infty}(% Y_{v}),

where

\textbf{D}_{\infty}(X_{v})\coloneqq n-|\textsf{fix}(X_{v})|-\textbf{H}_{\infty% }(\bm{x}_{[n]\smallsetminus\textsf{fix}(X_{v})}),\quad\quad\bm{x}\sim X_{v}

and $\textbf{D}_{\infty}(Y_{v})$ is defined analogously.

Now consider running $\Pi^{\prime}$ on $x, y$ , and let $v_{0},\ldots,v_{d}\in\mathcal{N}(\Pi^{\prime})$ denote all the nodes on the execution path. Fix any $k\in[d]$ and let us simply use $u$ and $v$ to denote $v_{k-1}$ and $v_{k}$ . Suppose without loss of generality that it is Alice who sends a bit to Bob in the $k$ -th iteration. Recall that in each iteration Alice first partitions $X_{u}=X_{u}^{0}\sqcup X_{u}^{1}$ according to the bit she sends. Then she performs the density-restoring partition with parameter $\gamma$ on $X_{u}^{b}=X_{u}^{b,1}\sqcup\ldots\sqcup X_{u}^{b,r}$ where $x\in X_{u}^{b}$ . Finally, she determines the unique $X^{b,i}_{u}$ that contains $x$ . Then for the next configuration, $X_{v}=X^{b,i}_{u}$ . Let us define

	$\displaystyle q_{u}^{b}\coloneqq\Pr[\bm{x}\in X^{b}_{u}\mid\bm{x}\in X_{u}],$
	$\displaystyle p_{u}^{b,\geq j}\coloneqq\Pr[\bm{x}\in\bigcup_{k\geq j}X^{b,k}_{% u}\bigg\|\bm{x}\in X^{b}_{u}]\quad\forall j\in[r],$
	$\displaystyle h_{k}(x,y)\coloneqq\log(1/q^{b}_{u})+\log(1/p_{u}^{b,\geq i}),$
	$\displaystyle n_{k}(x,y)\coloneqq\|\textsf{fix}(X_{v})\smallsetminus\textsf{fix% }(X_{u})\|.$

We have the following simple fact.

Fact 18.

$\textbf{D}_{\infty}(v)\leq\textbf{D}_{\infty}(u)-(1-\gamma)n_{k}(x,y)+h_{k}(x,y)$ .

Proof.

	$\displaystyle\textbf{D}_{\infty}(v)-\textbf{D}_{\infty}(u)$	$\displaystyle=-\|\textsf{fix}(X_{v})\|+\|\textsf{fix}(X_{u})\|+\textbf{H}_{\infty}% (X_{v})-\textbf{H}_{\infty}(X_{u})$
		$\displaystyle=-n_{k}(x,y)+(\textbf{H}_{\infty}(X_{v})-\textbf{H}_{\infty}(X_{u% }^{b}))+(\textbf{H}_{\infty}(X_{u}^{b})-\textbf{H}_{\infty}(X_{v}))$
	(from Lemma 15)	$\displaystyle\leq-n_{k}+\log(1/q_{u}^{b})+\left(\gamma\cdot n_{k}(x,y)+\log(1/% p_{u}^{b,\geq i})\right)$
		$\displaystyle=-(1-\gamma)n_{k}(x,y)+h_{k}(x,y).\$

$\hfill\blacktriangleleft$

Together with the nonnegativity of $\textbf{D}_{\infty}$ , we can bound the codimension of $R(x,y)$ by $h(x,y)\coloneqq\sum_{k=1}^{d}h_{k}(x,y)$ up to a multiplicative factor.

Claim 19.

For every $x,y\in\{0,1\}^{n}$ , $\mathrm{codim}(R(x,y))\leq\frac{1}{1-\gamma}\cdot h(x,y)$ .

Proof.

Consider the path in the tree leading to the leaf $R(x,y)$ , this path being of length $d$ . Summing up the inequalities from Fact 18 along that path, we get:

\textbf{D}_{\infty}(v_{d})-\textbf{D}_{\infty}(v_{0})\leq-(1-\gamma)\sum_{j=1}% ^{d}n_{j}(x,y)+\sum_{j=1}^{d}h_{j}(x,y)

Since $\textbf{D}_{\infty}(v_{d})$ is non-negative and $\textbf{D}_{\infty}(v_{0})=0$ , it follows that:

\mathrm{codim}(R(x,y))=\sum_{j=1}^{d}n_{j}(x,y)\leq\frac{1}{1-\gamma}\sum_{j=1% }^{d}h_{j}(x,y)=\frac{1}{1-\gamma}\cdot h(x,y).\

$\hfill\vartriangleleft$ We also observe that $h_{k}(\bm{x},\bm{y})$ has an exponential tail for each $k\in[d]$ , even conditioned on any node $v$ of depth $k-1$ being reached.

Claim 20.

For every node $v\in\mathcal{N}(\Pi^{\prime})$ of depth $0\leq k<d$ and threshold $\gamma\geq 0$ ,

\Pr_{\bm{x},\bm{y}}[h_{k+1}(\bm{x},\bm{y})\geq 1+\gamma\mid\bm{v}_{k}=v]\leq 2% ^{-\gamma}.

Proof.

Let $\bm{b},\bm{i}$ be as defined in the $(k+1)$ -th iteration of Algorithm 2 given $\bm{x},\bm{y}$ . We have

		$\displaystyle\Pr_{\bm{x},\bm{y}}[h_{k+1}(\bm{x},\bm{y})\geq 1+\gamma\mid\bm{v}% _{k}=v]$
	$\displaystyle=$	$\displaystyle\sum_{b\in\{0,1\}}\Pr[\bm{b}=b\mid\bm{v}_{k}=v]\cdot\Pr[\log(1/q^% {b}_{v})+\log(1/p_{v}^{b,\geq\bm{i}})\geq 1+\gamma\mid\bm{b}=b,\bm{v}_{k}=v]$
	$\displaystyle=$	$\displaystyle\sum_{b\in\{0,1\}}q^{b}_{v}\cdot\Pr\left[q^{b}_{v}\cdot p^{b,\geq% \bm{i}}\leq 2^{-\gamma-1}\bigg\|\bm{b}=b,\bm{v}_{k}=v\right]$
	$\displaystyle\leq$	$\displaystyle\sum_{b\in\{0,1\}}q^{b}_{v}\cdot\min\left\{1,2^{-\gamma-1}\cdot q% ^{b}_{v}\right\}$
	$\displaystyle\leq$	$\displaystyle 2^{-\gamma},$

where in the second last inequality, we use the property that $\Pr[p_{v}^{b,\geq\bm{i}}\leq t\mid\bm{b}=b,\bm{v}_{k}=v]\leq t$ for all $t\in[0,1]$ . $\hfill\vartriangleleft$

Finally, we need the following adaptive version of Bernstein’s inequality, whose proof can be found in Appendix C.

Lemma 21.

Let $\bm{a}_{1},\ldots,\bm{a}_{n}\in\mathbb{R}$ be a random sequence of reals and $\zeta>0$ be some fixed parameter. If for any $1\leq k\leq n$ and $a_{1},\ldots,a_{k-1}\in\mathbb{R}$ such that $\Pr[\bm{a}_{1}=a_{1},\ldots,\bm{a}_{k-1}=a_{k-1}]>0$ ,

\Pr[\bm{a}_{k}\geq x\mid\bm{a}_{1}=a_{1},\ldots,\bm{a}_{k-1}=a_{k-1}]\leq\exp(% -\zeta x),

then

\Pr\left[\sum_{i=1}^{n}\bm{a}_{i}\geq\frac{4}{\zeta}n\right]\leq\exp(-n).

We are now ready to bound the codimension of $R(\bm{x},\bm{y})$ . Let $(\bm{a}_{k}\coloneqq h_{k}(\bm{x},\bm{y})-1)_{k\in[d]}\in\mathbb{R}^{d}$ be a random sequence of reals. By Claim 20, $\bm{a}$ satisfies the condition in Lemma 21 with $\zeta=\ln 2$ . Therefore,

\Pr[h(\bm{x},\bm{y})\geq 7d]=\Pr[\sum_{i=1}^{d}\bm{a}_{i}\geq 6d]\leq\exp(-d).

Together with Claim 19, we conclude that

\Pr[\mathrm{codim}(R(\bm{x},\bm{y}))\geq\frac{7}{1-\gamma}\cdot d]\leq\Pr[h(% \bm{x},\bm{y})\geq 7d]\leq\exp(-d).\

$\hfill\blacktriangleleft$

3.4 Lower bound against subcube-like protocols

The following lemma is implicit in [20], we include its proof in Appendix B for completeness.

Lemma 22.

Let $0<\beta<\alpha<1$ and let $\Pi\colon\{0,1\}^{n}\times\{0,1\}^{n}\to S$ be a subcube-like protocol of codimension $\mathrm{codim}(\Pi)\eqqcolon d\leq(\alpha-\beta)^{2}r\Delta/4$ , and $G_{1}=([m],[n],E_{1}),G_{2}=([m],[n],E_{2})$ be two $(r,\Delta,\alpha\Delta)$ -expanders. Then there exist families $\{\mathsf{Cl}^{X}(v)\}_{v\in\mathcal{N}(\Pi)},\{\mathsf{Cl}^{Y}(v)\}_{v\in% \mathcal{N}(\Pi)}$ of subsets of $[m]$ such that the following conditions hold:

1.

For every non-root $v\in\mathcal{N}(\Pi)$ , let $u$ denote $v$ ’s parent. Then $\mathsf{Cl}^{X}(u)\subseteq\mathsf{Cl}^{X}(v)$ and $\mathsf{Cl}^{Y}(u)\subseteq\mathsf{Cl}^{Y}(v)$ .
2.

For every $v\in\mathcal{N}(\Pi)$ , $G_{1}-\mathsf{Cl}^{X}(v)-N(\mathsf{Cl}^{X}(v))-\textsf{fix}(X_{v})$ and $G_{2}-\mathsf{Cl}^{Y}(v)-N(\mathsf{Cl}^{Y}(v))-\textsf{fix}(Y_{v})$ are both $(r,\Delta,\beta\Delta)$ -expanders.
3.

For every $v\in\mathcal{N}(\Pi)$ , $|\mathsf{Cl}^{X}(v)|,|\mathsf{Cl}^{Y}(v)|\leq\frac{1}{\alpha-\beta}d/\Delta$ .

Lemma 23.

As in Theorem 7 let $G_{1}\coloneqq([m],[n],E_{1}),G_{2}\coloneqq([m],[n],E_{2})$ be two $(r,\Delta,\alpha\Delta)$ -expanders, and $X,Y\coloneqq\{0,1\}^{n}$ . For each $i\in[m]$ , let $C_{i}$ be a disjunction of variables in $\{x_{j}\mid j\in N_{G_{1}}(i)\}\cup\{y_{j}\mid j\in N_{G_{2}}(i)\}$ with arbitrary signs. Let $\Pi\colon\{0,1\}^{n}\times\{0,1\}^{n}\to[m]$ be a $\gamma$ -subcube-like communication protocol of $\mathrm{codim}(\Pi)\coloneqq d$ . If $d\leq\alpha^{2}r\Delta/4$ , then

\Pr_{\bm{x},\bm{y}}[C_{\bm{i}}(\bm{x},\bm{y})=0\mid\bm{i}=\Pi(\bm{x},\bm{y})]% \leq O(2^{-\gamma\alpha\Delta/2}\cdot d).

Proof.

We rephrase the success probability of $\Pi$ as follows: Sample a random leaf $\bm{\ell}$ of $\Pi$ with probability $|R_{\bm{\ell}}|/2^{2n}$ . Then

\Pr_{\bm{x},\bm{y}}[C_{\bm{i}}(\bm{x},\bm{y})=0\mid\bm{i}=\Pi(\bm{x},\bm{y})]=% \operatorname{\mathbb{E}}_{\bm{\ell}}\Big[\Pr_{(\bm{x},\bm{y})\sim R_{\bm{\ell% }}}[C_{\Pi(\bm{\ell})}(\bm{x},\bm{y})=0]\Big].

(1)

Let $\{\mathsf{Cl}^{X}(v)\}_{v\in\mathcal{N}(\Pi)},\{\mathsf{Cl}^{Y}(v)\}_{v\in% \mathcal{N}(\Pi)}$ be given by Lemma 22 with respect to $\Pi,G_{1},G_{2}$ and $\beta=\alpha/2$ . For each node $v\in\mathcal{N}(\Pi)$ , define $J_{v}\coloneqq\mathsf{Cl}^{X}(v)\cup\mathsf{Cl}^{Y}(v)$ . We first observe that for each leaf $\ell$ , $\Pi$ has low success probability on $R_{\ell}$ if $\Pi(\ell)\notin J_{\ell}$ .

Claim 24.

Let $\ell$ be any leaf in the protocol tree of $\Pi$ . Suppose that $i\not\in J_{\ell}$ . Then

\Pr_{(\bm{x},\bm{y})\sim R_{\ell}}[C_{i}(\bm{x},\bm{y})=0]\leq 2^{-\gamma% \alpha\Delta/2}.

Proof.

By the definition of $J_{\ell}$ , we have $i\not\in\mathsf{Cl}^{X}(\ell)$ . Let $A\subseteq[n]\smallsetminus(\textsf{fix}(X)\cup N(\mathsf{Cl}^{X}(\ell)))$ be the set of neighbors of $i$ in $G_{1}-\mathsf{Cl}^{X}(\ell)-N(\mathsf{Cl}^{X}(\ell))-\textsf{fix}(X_{\ell})$ , by the expansion we get $|A|\geq\alpha\Delta/2$ . Since $X_{\ell}\times Y_{\ell}$ is $\gamma$ -subcube-like we have that $\bm{x}_{[n]\smallsetminus\textsf{fix}(X_{\ell})}$ is $\gamma$ -spread. In particular, $\textbf{H}_{\infty}(\bm{x}_{A})\geq\gamma|A|\geq\gamma\alpha\Delta/2$ . Let $\tau\in\{0,1\}^{A}$ be the unique assignment that violates all literals of $C_{i}$ in $A$ . The min-entropy bound above then implies $\Pr[C_{i}(\bm{x},\bm{y})=0]\leq\Pr[\bm{x}_{A}=\tau]\leq 2^{-\gamma\alpha\Delta% /2}.$ $\hfill\vartriangleleft$ On the other hand, unfortunately, it is possible that

p_{i}(\ell)\coloneqq\Pr_{(\bm{x},\bm{y})\sim R_{\ell}}[C_{i}(\bm{x},\bm{y})=0]

is close to $1$ for some $i\in J_{\ell}$ . Nevertheless, we can show that this can happen only for a small fraction of leaves.

Claim 25.

Let $\bm{\ell}$ be a random leaf sampled as stated above. Then

\operatorname{\mathbb{E}}_{\bm{\ell}}\left[\sum_{i\in J_{\bm{\ell}}}p_{i}(\bm{% \ell})\right]\leq 2^{-\gamma\alpha\Delta/2}\cdot d.

Proof.

First, denoting by $\ell_{\bm{x},\bm{y}}$ the leaf containing $(\bm{x},\bm{y})$ , we can write

	$\displaystyle\operatorname{\mathbb{E}}_{\bm{\ell}}\left[\sum_{i\in J_{\bm{\ell% }}}p_{i}(\bm{\ell})\right]$	$\displaystyle=\sum_{i\in[m]}\operatorname{\mathbb{E}}_{\bm{\ell}}[\mathbf{1}_{% i\in J_{\bm{\ell}}}\cdot p_{i}(\bm{\ell})]$
		$\displaystyle=\sum_{i\in[m]}\Pr_{\bm{x},\bm{y}}[i\in J_{\ell_{\bm{x},\bm{y}}}% \,\land\,C_{i}(\bm{x},\bm{y})=0]$
		$\displaystyle=\sum_{i\in[m]}\Pr_{\bm{x},\bm{y}}[C_{i}(\bm{x},\bm{y})=0\mid i% \in J_{\ell_{\bm{x},\bm{y}}}]\cdot\Pr_{\bm{x},\bm{y}}[i\in J_{\ell_{\bm{x},\bm% {y}}}]$
		$\displaystyle\leq\max_{i\in[m]}\Pr_{\bm{x},\bm{y}}[C_{i}(\bm{x},\bm{y})=0\mid i% \in J_{\ell_{\bm{x},\bm{y}}}]\cdot\sum_{i\in[m]}\Pr_{\bm{x},\bm{y}}[i\in J_{% \ell_{\bm{x},\bm{y}}}]$
		$\displaystyle=\max_{i\in[m]}\Pr_{\bm{x},\bm{y}}[C_{i}(\bm{x},\bm{y})=0\mid i% \in J_{\ell_{\bm{x},\bm{y}}}]\cdot\operatorname{\mathbb{E}}_{\bm{\ell}}[\|J_{% \bm{\ell}}\|].$

Observe that $|J_{\ell}|\leq d$ for every leaf $\ell$ , it suffices to show

\Pr_{\bm{x},\bm{y}}[C_{i}(\bm{x},\bm{y})=0\mid i\in J_{\ell_{\bm{x},\bm{y}}}]% \leq 2^{-\gamma\alpha\Delta/2}.

for every $i\in[m]$ . Now let us fix an arbitrary $i\in[m]$ . The event “ $i\in J_{\ell_{\bm{x},\bm{y}}}$ ” can be reinterpreted as follows: with

V_{i}\coloneqq\{v\in\mathcal{N}(\Pi)\mid i\in J_{v}\text{ and the parent of $v% $ does not satisfy that}\}

we have that $i\in J_{\ell_{\bm{x},\bm{y}}}$ if and only if $(\bm{x},\bm{y})\in\bigsqcup_{v\in V_{i}}R_{v}$ (the rectangles form a partition since the nodes in $V_{i}$ are maximally close to the root). Then
$\Pr_{\bm{x},\bm{y}}[C_{i}(\bm{x},\bm{y})=0\mid i\in J_{\ell_{\bm{x},\bm{y}}}]% \leq\sum_{v\in V_{i}}\Pr_{\bm{x},\bm{y}}[(\bm{x},\bm{y})\in R_{v}\mid i\in J_{% \ell_{\bm{x},\bm{y}}}]\cdot\Pr_{\bm{x},\bm{y}}[C_{i}(\bm{x},\bm{y})=0\mid(\bm{% x},\bm{y})\in R_{v}].$

Since the right-hand side is a convex combination of $\Pr[C_{i}(\bm{x},\bm{y})=0\mid(\bm{x},\bm{y})\in R_{v}]$ for $v\in V_{i}$ , it suffices to bound the maximum of these probabilities.

The crucial observation to conclude the proof is that $i\not\in\mathsf{Cl}^{X}(v)$ if Bob spoke in the parent node of $v$ and $i\not\in\mathsf{Cl}^{Y}(v)$ if Alice spoke in that node. In any case, an argument similar to that in Claim 24 applies and we have $\Pr[C_{i}(\bm{x},\bm{y})=0\mid(\bm{x},\bm{y})\in R_{v}]\leq 2^{-\gamma\alpha% \Delta/2}$ , which concludes the proof. $\hfill\vartriangleleft$ Now we are ready to show the desired bound. Combining the above two claims, we have

	(1)	$\displaystyle=\Pr[\Pi(\bm{\ell})\notin J_{\bm{\ell}}]\cdot\operatorname{% \mathbb{E}}_{\bm{\ell}}[\Pr_{(\bm{x},\bm{y})\sim R_{\bm{\ell}}}[C_{\Pi(\bm{% \ell})}(\bm{x},\bm{y})=0]\mid\Pi(\bm{\ell})\notin J_{\bm{\ell}}]$
		$\displaystyle+\Pr[\Pi(\bm{\ell})\in J_{\bm{\ell}}]\cdot\operatorname{\mathbb{E% }}_{\bm{\ell}}[\Pr_{(\bm{x},\bm{y})\sim R_{\bm{\ell}}}[C_{\Pi(\bm{\ell})}(\bm{% x},\bm{y})=0]\mid\Pi(\bm{\ell})\in J_{\bm{\ell}}]$
		$\displaystyle\leq 2^{-\gamma\alpha\Delta/2}+\operatorname{\mathbb{E}}_{\bm{% \ell}}[\sum_{i\in J_{\bm{\ell}}}p_{i}(\bm{\ell})]$
		$\displaystyle=O(d/2^{\gamma\alpha\Delta/2}).\$

$\hfill\blacktriangleleft$

3.5 Proof of Theorem 7

We first restate the theorem for convenience. See 7

Proof.

Let $\tilde{\Pi}$ be a subcube-like protocol given by Lemma 17 with respect to $\Pi$ and $\gamma=\alpha$ . Then $\mathrm{codim}(\Pi^{\prime})\leq\frac{7d}{1-\alpha}$ . Moreover,

\Pr_{\bm{x},\bm{y}}[\Pi(\bm{x},\bm{y})\neq\tilde{\Pi}(\bm{x},\bm{y})]\leq\exp(% -d).

We can then apply Lemma 23 and conclude that

\Pr_{\bm{x},\bm{y}}[C_{\bm{i}}(\bm{x},\bm{y})=0\mid\bm{i}=\Pi(\bm{x},\bm{y})]% \leq\\ \Pr_{\bm{x},\bm{y}}[C_{\bm{i}}(\bm{x},\bm{y})=0\mid\bm{i}=\tilde{\Pi}(\bm{x},% \bm{y})]+\exp(-d)=d\cdot 2^{-\Omega(\Delta)}+\exp(-d).\quad\

$\hfill\blacktriangleleft$

References

[1] Michael Alekhnovich. Lower bounds for k-dnf resolution on random 3-cnfs. Comput. Complex., 20(4):597–614, 2011. doi:10.1007/s00037-011-0026-0.
[2] Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, and Avi Wigderson. Pseudorandom generators in propositional proof complexity. SIAM J. Comput., 34(1):67–88, 2004. doi:10.1137/S0097539701389944.
[3] Michael Alekhnovich and Alexander A. Razborov. Lower bounds for polynomial calculus: Non-binomial case. Proceedings of the Steklov Institute of Mathematics, 242:18–35, 2003. Available at http://people.cs.uchicago.edu/˜razborov/files/misha.pdf. Preliminary version in FOCS ’01.
[4] Paul Beame, Richard M. Karp, Toniann Pitassi, and Michael E. Saks. The efficiency of resolution and davis–putnam procedures. SIAM J. Comput., 31(4):1048–1075, 2002. doi:10.1137/S0097539700369156.
[5] Paul Beame, Toniann Pitassi, and Nathan Segerlind. Lower bounds for lov[a-acute]sz–schrijver systems and beyond follow from multiparty communication complexity. SIAM J. Comput., 37(3):845–869, 2007. doi:10.1137/060654645.
[6] Paul Beame and Michael Whitmeyer. Multiparty Communication Complexity of Collision-Finding and Cutting Planes Proofs of Concise Pigeonhole Principles. In Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis, editors, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1–21:20, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2025.21.
[7] Vašek Chvátal and Endre Szemerédi. Many hard examples for resolution. J. ACM, 35(4):759–768, October 1988. doi:10.1145/48014.48016.
[8] Amit Daniely and Shai Shalev-Shwartz. Complexity theoretic limitations on learning dnf’s. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 815–830, Columbia University, New York, New York, USA, 23–26 June 2016. PMLR. URL: https://proceedings.mlr.press/v49/daniely16.html.
[9] 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. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, pages 1371–1382, New York, NY, USA, 2025. Association for Computing Machinery. doi:10.1145/3717823.3718271.
[10] 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 Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 295–304. IEEE Computer Society, 2016. doi:10.1109/FOCS.2016.40.
[11] Uriel Feige. Relations between average case complexity and approximation complexity. In Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, page 5. IEEE Computer Society, 2002. doi:10.1109/CCC.2002.10006.
[12] Noah Fleming, Denis Pankratov, Toniann Pitassi, and Robert Robere. Random $\Theta(\log n)$ -CNFs are Hard for Cutting Planes. J. ACM, 69(3):19:1–19:32, 2022. doi:10.1145/3486680.
[13] Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov. Monotone circuit lower bounds from resolution. Theory Comput., 16:1–30, 2020. doi:10.4086/TOC.2020.V016A013.
[14] Mika Göös, Tom Gur, Siddhartha Jain, and Jiawei Li. Quantum communication advantage in tfnp. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, pages 1465–1475, New York, NY, USA, 2025. Association for Computing Machinery. doi:10.1145/3717823.3718155.
[15] Mika Göös, Rahul Jain, and Thomas Watson. Extension complexity of independent set polytopes. SIAM J. Comput., 47(1):241–269, 2018. doi:10.1137/16M109884X.
[16] Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized communication versus partition number. ACM Trans. Comput. Theory, 10(1):4:1–4:20, 2018. doi:10.1145/3170711.
[17] Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov. Adventures in monotone complexity and TFNP. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 38:1–38:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ITCS.2019.38.
[18] Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. SIAM J. Comput., 45(5):1835–1869, 2016. doi:10.1137/15M103145X.
[19] Mika Göös, Gilbert Maystre, Kilian Risse, and Dmitry Sokolov. Supercritical tradeoffs for monotone circuits. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, pages 1359–1370, New York, NY, USA, 2025. Association for Computing Machinery. doi:10.1145/3717823.3718229.
[20] Mika Göös, Ilan Newman, Artur Riazanov, and Dmitry Sokolov. Hardness condensation by restriction. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 2016–2027. ACM, 2024. doi:10.1145/3618260.3649711.
[21] Mika Göös and Toniann Pitassi. Communication lower bounds via critical block sensitivity. SIAM Journal on Computing, 47(5):1778–1806, 2018. doi:10.1137/16M1082007.
[22] Mika Göös, Toniann Pitassi, and Thomas Watson. Query-to-communication lifting for BPP. SIAM Journal on Computing, 49(4), 2020. doi:10.1137/17M115339X.
[23] Dima Grigoriev. Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theoretical Computer Science, 259(1):613–622, 2001. doi:10.1016/S0304-3975(00)00157-2.
[24] 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.
[25] Trinh Huynh and Jakob Nordström. On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 233–248. ACM, 2012. doi:10.1145/2213977.2214000.
[26] Russell Impagliazzo, Toniann Pitassi, and Alasdair Urquhart. Upper and lower bounds for tree-like cutting planes proofs. In Proceedings of the Ninth Annual Symposium on Logic in Computer Science (LICS ’94), Paris, France, July 4-7, 1994, pages 220–228. IEEE Computer Society, 1994. doi:10.1109/LICS.1994.316069.
[27] Dmitry Itsykson and Artur Riazanov. Proof complexity of natural formulas via communication arguments. In Valentine Kabanets, editor, 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference), volume 200 of LIPIcs, pages 3:1–3:34. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.CCC.2021.3.
[28] Dmitry Itsykson and Dmitry Sokolov. Resolution over linear equations modulo two. Ann. Pure Appl. Log., 171(1), 2020. doi:10.1016/J.APAL.2019.102722.
[29] 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.
[30] 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.
[31] László Lovász, Moni Naor, Ilan Newman, and Avi Wigderson. Search problems in the decision tree model. SIAM J. Discret. Math., 8(1):119–132, 1995. doi:10.1137/S0895480192233867.
[32] 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.
[33] Marc Mezard, Giorgio Parisi, and Riccardo Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science (New York, N.Y.), 297:812–815, September 2002. doi:10.1126/science.1073287.
[34] Toniann Pitassi and Robert Robere. Lifting nullstellensatz to monotone span programs over any field. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1207–1219. ACM, 2018. doi:10.1145/3188745.3188914.
[35] 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.
[36] Alexander A. Razborov. Applications of matrix methods to the theory of lower bounds in computational complexity. Comb., 10(1):81–93, 1990. doi:10.1007/BF02122698.
[37] Robert Robere, Toniann Pitassi, Benjamin Rossman, and Stephen A. Cook. Exponential lower bounds for monotone span programs. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 406–415. IEEE Computer Society, 2016. doi:10.1109/FOCS.2016.51.
[38] Anastasia Sofronova and Dmitry Sokolov. A lower bound for k-dnf resolution on random CNF formulas via expansion. Electron. Colloquium Comput. Complex., TR22-054, 2022. URL: https://eccc.weizmann.ac.il/report/2022/054.
[39] Dmitry Sokolov. (semi)algebraic proofs over $\pm$ 1 variables. 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 78–90. ACM, 2020. doi:10.1145/3357713.3384288.
[40] Dmitry Sokolov. Random $(\log n)$ -CNF Are Hard for Cutting Planes (Again). In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 2008–2015. ACM, 2024. doi:10.1145/3618260.3649636.
[41] Shuo Wang, Guangxu Yang, and Jiapeng Zhang. Communication Complexity of Set-Intersection Problems and Its Applications. Technical report, ECCC, 2023. URL: https://eccc.weizmann.ac.il/report/2023/164.
[42] Guangxu Yang and Jiapeng Zhang. Communication lower bounds for collision problems via density increment arguments. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 630–639, New York, NY, USA, 2024. Association for Computing Machinery. doi:10.1145/3618260.3649607.

Appendix A Proof of Lemma 8

We start by proving Item 1 (Item 2 is analogous). Let $N^{\bm{X}}(i)$ for $i\in[m]$ be the set of neighbors of $i$ in $\bm{X}$ and $N^{\bm{Y}}(i)$ – in $\bm{Y}$ . Then $\textsc{Error}_{\bm{X}}=\{i\in[m]\mid|N^{\bm{X}}(i)|>(1-\delta)\Delta\}$ . We then write

	$\displaystyle\operatorname{\mathbb{E}}[\|\textsc{Error}_{\bm{X}}\|]$	$\displaystyle=\sum_{i\in[m]}\Pr[\|N^{\bm{X}}(i)\|>(1-\delta)\Delta\big]$
		$\displaystyle=\sum_{i\in[m]}\sum_{S\subseteq N(i)\colon\|S\|\geq(1-\delta)\Delta% }\Pr[\bm{X}\cup N(i)=S]$
		$\displaystyle=m\sum_{j\leq\delta\Delta}\binom{m}{m-j}2^{-\Delta}$
		$\displaystyle\leq m2^{-(1-\operatorname{H}(\delta))\Delta}$
		$\displaystyle=\alpha n\cdot 2^{\operatorname{H}(\delta)\Delta}$
		$\displaystyle=\alpha n^{1+c\operatorname{H}(\delta)}$

On the other hand for every $i\in\textsc{Error}_{\bm{X}}$ we have

\Pr_{\bm{x}\sim\{0,1\}^{\bm{X}}}[C_{i}(\bm{x},\cdot)\not\equiv 1]=2^{-|N^{\bm{% X}}(i)|}\leq 2^{-(1-\delta)\Delta}=n^{-c(1-\delta)}.

Then by a union bound we get

\Pr_{\bm{x}\sim\{0,1\}^{\bm{X}}}[\exists i\in\textsc{Error}_{\bm{X}}\colon C_{% i}(\bm{x},\cdot)\not\equiv 1]\leq|\textsc{Error}_{\bm{X}}|\cdot n^{-c(1-\delta% )}.

Then by Markov’s inequality applied to $|\textsc{Error}_{\bm{X}}|$ with probability $1-\varepsilon$ over $\bm{X}$ we have

	$\displaystyle\Pr_{\bm{x}\sim\{0,1\}^{\bm{X}}}[\exists i\in\textsc{Error}_{\bm{% X}}\colon C_{i}(\bm{x},\cdot)\not\equiv 1]$	$\displaystyle\leq 1/\varepsilon\cdot\operatorname{\mathbb{E}}[\|\textsc{Error}_% {\bm{X}}\|]\cdot n^{-c(1-\delta)}$
		$\displaystyle=\alpha/\varepsilon\cdot n^{1+c\operatorname{H}(\delta)-c(1-% \delta)}$
		$\displaystyle=\alpha/\varepsilon\cdot n^{1-c(1-\delta-\operatorname{H}(\delta))}$

Now it remains to prove Item 3. First, let $\bm{G}\coloneqq([m],[n],E_{\bm{X}}\sqcup E_{\bm{Y}})$ be the union of $G_{\bm{X}}$ and $G_{\bm{Y}}$ . By Lemma 6 whp over $\bm{\varphi}$ the graph $\bm{G}$ is an $(r,\Delta,(1-\eta)\Delta)$ -expander for any $\eta$ and $r=\Omega_{\eta}\left(\frac{n}{\Delta}\right)$ . Now it is sufficient to show $G_{\bm{X}}-\textsc{Error}_{\bm{Y}}$ is an $(r,\Delta,(\delta-2\eta)\Delta)$ -expander whp, $G_{\bm{Y}}-\textsc{Error}_{\bm{X}}$ is distributed identically to $G_{\bm{X}}-\textsc{Error}_{\bm{Y}}$ and removing additional nodes from the left-hand side does not reduce expansion.

We in fact show that conditioned on the fact that $\bm{G}$ is an $(r,\Delta,(1-\eta)\Delta)$ -expander, $G_{\bm{X}}-\textsc{Error}_{\bm{Y}}$ is $(r,\Delta,(\delta-2\eta)\Delta)$ -expander with probability $1$ . Consider an arbitrary subset $U\subseteq[m]$ of size at most $r$ . For every such subset we need to have $|N(U)\smallsetminus\bm{Y}\smallsetminus N(\textsc{Error}_{\bm{Y}})|\geq(\delta% -2\eta)\Delta|U\smallsetminus\textsc{Error}_{\bm{Y}}|$ . Here and below $N(S)=N_{\bm{G}}(S)$ . Consider the set $\partial U\coloneqq\{v\in N(U)\mid v\text{ is connected with a single node in }U\}$ . Then $|\partial U|\geq(1-2\eta)|U|\Delta$ : indeed the number of edges incident to $U$ can be estimated in two ways:

\Delta|U|=|E\cap(U\times[n])|\geq|\partial U|+2(|N(U)|-|\partial U|)\geq 2(1-% \eta)\Delta|U|-|\partial U|.

Then we can partition the set $N(U)$ into sets $N_{i}$ for $i\in U$ where $N_{i}\subseteq N(i)$ and $|N_{i}|\geq(1-2\eta)\Delta$ : find a node $i\in U$ such that $|\partial U\cap N(i)|\geq(1-2\eta)\Delta$ , let $N_{i}\coloneqq\partial U\cap N(i)$ and continue the process for $U\smallsetminus\{i\}$ , the reason the resulting sets form a partition is that $N_{i}\cap N(U\smallsetminus\{i\})=\emptyset$ by the definition of $\partial U$ .

For every $Y\subseteq[n]$ if $|N(i)\smallsetminus Y|\geq\delta\Delta$ , then $|N_{i}\smallsetminus Y|\geq|N(i)\smallsetminus Y|-|N(i)\smallsetminus N_{i}|% \geq(\delta-2\eta)\Delta$ . It follows that after removing $\textsc{Error}_{\bm{Y}}$ (vertices for which $|N(i)\smallsetminus\bm{Y}|<\delta\Delta$ ), every vertex $i$ in the set $U\smallsetminus\textsc{Error}_{\bm{Y}}$ in $G_{\bm{X}}$ has at least $(\delta-2\eta)\Delta$ neighbours in $N_{i}\smallsetminus\bm{Y}$ . As $N_{i}$ is a partition, it follows that $|N(U)\smallsetminus\textsc{Error}_{\bm{Y}}\smallsetminus N(\textsc{Error}_{\bm% {Y}})|\geq(\delta-2\eta)\Delta|U\smallsetminus\textsc{Error}_{\bm{Y}}|$ .

Finally, choosing $\eta=\delta/4$ completes the proof. By Lemma 6 this particular choice only affects the hidden constant in $r=\Omega(n/\Delta)$ .

Appendix B Proof of Lemma 22

Since $\mathsf{Cl}^{X}$ and $\mathsf{Cl}^{Y}$ are independent of each other, we just focus on constructing $\mathsf{Cl}^{X}$ . It suffices to prove the following lemma:

Lemma 26.

Let $G=([m],[n],E)$ be an $(r,\Delta,\alpha\Delta)$ -expander. Let $\mathcal{T}$ be a tree with nodes labeled with subsets of $[n]$ , where $S_{v}\subseteq[n]$ denotes the label of $v$ such that

$\blacksquare$

For the root of $\mathcal{T}$ , the node $r$ we have $S_{r}=\emptyset$ .
$\blacksquare$

If $u$ is a parent of $v$ , then $S_{u}\subseteq S_{v}$ .
$\blacksquare$

For every $u$ we have $|S_{u}|\leq d\leq(\alpha-\beta)^{2}r\Delta/4$ .

Then there for every node $u$ to $\mathcal{T}$ there exists a set $T_{u}\subseteq[m]$ such that

(a)

The graph $G_{u}\coloneqq G-T_{u}-S_{u}-N(T_{u})$ is an $(r,\Delta,\beta\Delta)$ -expander.
(b)

If $u$ is a parent of $v$ , then $T_{u}\subseteq T_{v}$ .
(c)

$|T_{u}|\leq\frac{1}{\alpha-\beta}d/\Delta$ .

To finish the proof of Lemma 22 given Lemma 26 we just let $\mathcal{T}$ be the tree of the protocol and $S_{u}$ be $\textsf{fix}(X_{u})$ , then take $\mathsf{Cl}^{X}(u)\coloneqq T_{u}$ .

We now proceed to prove Lemma 26. Wlog we may assume that if $u$ is a parent of $v$ we have $|S_{v}\smallsetminus S_{u}|\leq 1$ (just by replacing a single edge in $\mathcal{T}$ by a chain of edges).

We construct the sets $T_{u}$ inductively starting from the root $r$ where $T_{r}=\emptyset$ . Suppose $u$ is a parent of node $v$ and we have constructed $T_{u}$ . If $S_{u}=S_{v}$ , we just let $T_{v}\coloneqq T_{u}$ , so assume that $S_{v}\smallsetminus S_{u}=\{i\}$ . Let $G^{\prime}_{u}\coloneqq G_{u}-i$ . Let us find the largest set $B_{v}\subseteq[m]\smallsetminus T_{u}$ such that $|B_{v}|\leq r$ and $|N_{G^{\prime}_{u}}(B_{v})|\leq\beta\Delta|B_{v}|$ and let $T_{v}\coloneqq T_{u}\cup B_{v}$ . Then $G_{v}=G^{\prime}_{u}-T_{u}-N_{G^{\prime}_{u}}(T_{u})$ . It is clear that $T$ satisfies Item (b).

Proof of Item (c).

We show by induction on the depth $\ell$ of a node $u$ that $|T_{u}|\leq\frac{1}{\alpha-\beta}\ell/\Delta$ . The base case is satisfied since for the root $r$ the set $T_{r}$ is empty. Now let $u$ be a node at depth $\ell$ and $v$ be its child at depth $\ell+1$ . We have that $|T_{u}|\leq\frac{1}{\alpha-\beta}\ell/\Delta$ , we need to prove that $|T_{v}|=|T_{u}\sqcup B_{v}|\leq\frac{1}{\alpha-\beta}(\ell+1)/\Delta$ .

On the one hand $N_{G^{\prime}_{u}}(B_{v})=N_{G}(B_{v})\smallsetminus(N_{G}(T_{u})\cup S_{v})$ . On the other hand, $|N_{G^{\prime}_{u}}(B_{v})|\leq\beta\Delta|B_{v}|$ . By the expansion of $G$ we have $|N_{G}(B_{v})|\geq\alpha\Delta|B_{v}|$ . Hence $|N_{G}(T_{u})\cup S_{v}|\geq(\alpha-\beta)\Delta|B_{v}|$ . By the assumption on the tree $|S_{v}|=\ell+1$ , and by induction hypothesis $|T_{u}|\leq\frac{1}{\alpha-\beta}\ell/\Delta$ , so $|N_{G}(T_{u}))|\leq\frac{1}{\alpha-\beta}\ell$ .

Combining the two inequalities, we get $\frac{1}{\alpha-\beta}\ell+(\ell+1)\geq(\alpha-\beta)\Delta|B_{v}|$ .

From that, we get $|B_{v}|\leq 2\cdot\frac{1}{\left(\alpha-\beta\right)^{2}\Delta}\cdot(\ell+1)% \leq r/2$ , where the last inequality follows from the assumptions on $\ell$ . Then we get that $|T_{v}|\leq|T_{u}|+|B_{v}|\leq r$ . Now we can use expansion of $G$ to bound $|N_{G}(T_{v})|\geq\alpha\Delta|T_{v}|$ . On the other hand, let $r=w_{0},w_{1},\dots,w_{\ell}=u,w_{\ell+1}=v$ be the path in $\mathcal{T}$ from the root to $v$ . We then have

N_{G}(T_{v})\subseteq\bigcup_{i=0}^{\ell}N_{G^{\prime}_{w_{i}}}(B_{{w_{i+1}}})% \cup S_{v}.

By the choice of sets $B$ we get $|N_{G}(T_{v})|\leq\beta\Delta|T_{v}|+|S_{v}|$ . Combining the two bounds we get $|T_{v}|\leq\frac{1}{\alpha-\beta}|S_{v}|/\Delta$ , which concludes the proof.

Proof of Item (a).

Pick the node $v$ at depth $\ell+1$ such that $G_{v}$ is not an $(r,\Delta,\beta\Delta)$ -expander, and $v$ is the closest to the root among such nodes. In particular, for its parent $u$ the graph $G_{u}$ is $(r,\Delta,\beta\Delta)$ -expander. Then there exists a set $T$ of size at most $r$ such that $N_{G_{v}}(T)<\beta\Delta|T|$ . By expansion of $G$ we get $|N_{G}(T)|\geq\alpha\Delta|T|$ . Then, since $N_{G_{v}}(T)=N_{G}(T)\smallsetminus(N_{G}(T_{v})\cup S_{v})$ we have

\frac{1}{2}(\alpha-\beta)\Delta r\geq\frac{2}{\alpha-\beta}\ell\geq\frac{1}{% \alpha-\beta}\ell+(\ell+1)\geq|N_{G}(T_{v})\cup S_{v}|\geq(\alpha-\beta)\Delta% |T|.

The left-hand side follows from Item (c) and the right-hand side follows from the analysis above. Then $|T|\leq r/2$ . Since by the proof of Item (c) we have that $|B_{v}|\leq r/2$ , we get $|T\cup B_{v}|\leq r$ , yet $|N_{G^{\prime}_{u}}(T\cup B_{v})|<\beta\Delta|B_{v}|+\beta\Delta|T|\leq\beta% \Delta|B_{v}\sqcup T|$ , contradicting the choice of $B_{v}$ .

Appendix C Proof of Lemma 21

Lemma 21. [Restated, see original statement.]

Let $\bm{a}_{1},\ldots,\bm{a}_{n}\in\mathbb{R}$ be a random sequence of reals and $\zeta>0$ be some fixed parameter. If for any $1\leq k\leq n$ and $a_{1},\ldots,a_{k-1}\in\mathbb{R}$ such that $\Pr[\bm{a}_{1}=a_{1},\ldots,\bm{a}_{k-1}=a_{k-1}]>0$ ,

\Pr[\bm{a}_{k}\geq x\mid\bm{a}_{1}=a_{1},\ldots,\bm{a}_{k-1}=a_{k-1}]\leq\exp(% -\zeta x),

then

\Pr\left[\sum_{i=1}^{n}\bm{a}_{i}\geq\frac{4}{\zeta}n\right]\leq\exp(-n).

Proof.

Let $\lambda\in(0,\zeta)$ be some parameter that will be determined later. First, observe that for any $1\leq k\leq n$ and $a_{1},\ldots,a_{k-1}\in\mathbb{R}$ such that $\Pr[\bm{a}_{1}=a_{1},\ldots,\bm{a}_{k-1}=a_{k-1}]>0$ ,

\operatorname{\mathbb{E}}[\exp(\lambda\bm{a}_{k})\mid\bm{a}_{1}=a_{1},\ldots,% \bm{a}_{k-1}=a_{k-1}]\leq\zeta\int\limits_{0}^{\infty}\exp(\lambda x)\cdot\exp% (-\zeta x)\cdot\differential{x}=\zeta/(\zeta-\lambda).

(2)

Next, we prove by induction on $k$ from $n$ to $1$ that

\operatorname{\mathbb{E}}\left[\exp\left(\lambda\sum_{i=k}^{n}\bm{a}_{i}\right% )\middle|\bm{a}_{1}=a_{1},\ldots,\bm{a}_{k-1}=a_{k-1}\right]\leq\left(\frac{% \zeta}{\zeta-\lambda}\right)^{n-k+1}.

(3)

The base case $k=n$ is exactly (2). Now assume that (3) holds for all $k\geq m+1$ . Then

		$\displaystyle\operatorname{\mathbb{E}}\left[\exp(\lambda\sum_{i=m}^{n}\bm{a}_{% i})\middle\|\bm{a}_{1}=a_{1},\ldots,\bm{a}_{m-1}=a_{m-1}\right]$
	$\displaystyle\leq$	$\displaystyle\sum_{a_{m}}\Pr[\bm{a}_{m}=a_{m}\mid\bm{a}_{1}=a_{1},\ldots,\bm{a% }_{m-1}=a_{m-1}]\cdot\exp(\lambda a_{m})\cdot$
		$\displaystyle\hskip 56.9055pt\cdot\operatorname{\mathbb{E}}\left[\exp(\lambda% \sum_{i=m+1}^{n}\bm{a}_{i})\middle\|\bm{a}_{1}=a_{1},\ldots,\bm{a}_{m}=a_{m}\right]$
	$\displaystyle\leq$	$\displaystyle\left(\frac{\lambda}{\zeta-\lambda}\right)^{n-m}\cdot% \operatorname{\mathbb{E}}[\exp(\lambda\bm{a}_{m})\mid\bm{a}_{1}=a_{1},\ldots,% \bm{a}_{m-1}=a_{m-1}]$
	$\displaystyle=$	$\displaystyle\left(\frac{\lambda}{\zeta-\lambda}\right)^{n-m+1}.$

Finally, by setting $\lambda=\zeta/2$ , we conclude that

	$\displaystyle\Pr\left[\sum_{i=1}^{n}\bm{a}_{i}\geq\frac{4}{\zeta}n\right]$	$\displaystyle=\Pr\left[\exp\left(\lambda\sum_{i=1}^{n}\bm{a}_{i}\right)\geq% \exp\left(\frac{4\lambda}{\zeta}n\right)\right]$
		$\displaystyle\leq\operatorname{\mathbb{E}}\left[\exp(\lambda\sum_{i=1}^{n}\bm{% a}_{i})\right]\cdot\exp(-2n)$
		$\displaystyle\leq\left(\frac{\zeta}{\zeta-\lambda}\right)^{n}\cdot\exp(-2n)$
		$\displaystyle\leq\exp(-n).\$

$\hfill\blacktriangleleft$

[bib.bib1] [1] Michael Alekhnovich. Lower bounds for k-dnf resolution on random 3-cnfs. Comput. Complex., 20(4):597–614, 2011. doi:10.1007/s00037-011-0026-0.

[bib.bib2] [2] Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, and Avi Wigderson. Pseudorandom generators in propositional proof complexity. SIAM J. Comput., 34(1):67–88, 2004. doi:10.1137/S0097539701389944.

[bib.bib3] [3] Michael Alekhnovich and Alexander A. Razborov. Lower bounds for polynomial calculus: Non-binomial case. Proceedings of the Steklov Institute of Mathematics, 242:18–35, 2003. Available at http://people.cs.uchicago.edu/˜razborov/files/misha.pdf. Preliminary version in FOCS ’01.

[bib.bib4] [4] Paul Beame, Richard M. Karp, Toniann Pitassi, and Michael E. Saks. The efficiency of resolution and davis–putnam procedures. SIAM J. Comput., 31(4):1048–1075, 2002. doi:10.1137/S0097539700369156.

[bib.bib5] [5] Paul Beame, Toniann Pitassi, and Nathan Segerlind. Lower bounds for lov[a-acute]sz–schrijver systems and beyond follow from multiparty communication complexity. SIAM J. Comput., 37(3):845–869, 2007. doi:10.1137/060654645.

[bib.bib6] [6] Paul Beame and Michael Whitmeyer. Multiparty Communication Complexity of Collision-Finding and Cutting Planes Proofs of Concise Pigeonhole Principles. In Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis, editors, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1–21:20, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2025.21.

[bib.bib7] [7] Vašek Chvátal and Endre Szemerédi. Many hard examples for resolution. J. ACM, 35(4):759–768, October 1988. doi:10.1145/48014.48016.

[bib.bib8] [8] Amit Daniely and Shai Shalev-Shwartz. Complexity theoretic limitations on learning dnf’s. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 815–830, Columbia University, New York, New York, USA, 23–26 June 2016. PMLR. URL: https://proceedings.mlr.press/v49/daniely16.html.

[bib.bib9] [9] 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. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, pages 1371–1382, New York, NY, USA, 2025. Association for Computing Machinery. doi:10.1145/3717823.3718271.

[bib.bib10] [10] 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 Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 295–304. IEEE Computer Society, 2016. doi:10.1109/FOCS.2016.40.

[bib.bib11] [11] Uriel Feige. Relations between average case complexity and approximation complexity. In Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, page 5. IEEE Computer Society, 2002. doi:10.1109/CCC.2002.10006.

[bib.bib12] [12] Noah Fleming, Denis Pankratov, Toniann Pitassi, and Robert Robere. Random $\Theta(\log n)$ -CNFs are Hard for Cutting Planes. J. ACM, 69(3):19:1–19:32, 2022. doi:10.1145/3486680.

[bib.bib13] [13] Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov. Monotone circuit lower bounds from resolution. Theory Comput., 16:1–30, 2020. doi:10.4086/TOC.2020.V016A013.

[bib.bib14] [14] Mika Göös, Tom Gur, Siddhartha Jain, and Jiawei Li. Quantum communication advantage in tfnp. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, pages 1465–1475, New York, NY, USA, 2025. Association for Computing Machinery. doi:10.1145/3717823.3718155.

[bib.bib15] [15] Mika Göös, Rahul Jain, and Thomas Watson. Extension complexity of independent set polytopes. SIAM J. Comput., 47(1):241–269, 2018. doi:10.1137/16M109884X.

[bib.bib16] [16] Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized communication versus partition number. ACM Trans. Comput. Theory, 10(1):4:1–4:20, 2018. doi:10.1145/3170711.

[bib.bib17] [17] Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov. Adventures in monotone complexity and TFNP. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 38:1–38:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ITCS.2019.38.

[bib.bib18] [18] Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. SIAM J. Comput., 45(5):1835–1869, 2016. doi:10.1137/15M103145X.

[bib.bib19] [19] Mika Göös, Gilbert Maystre, Kilian Risse, and Dmitry Sokolov. Supercritical tradeoffs for monotone circuits. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, pages 1359–1370, New York, NY, USA, 2025. Association for Computing Machinery. doi:10.1145/3717823.3718229.

[bib.bib20] [20] Mika Göös, Ilan Newman, Artur Riazanov, and Dmitry Sokolov. Hardness condensation by restriction. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 2016–2027. ACM, 2024. doi:10.1145/3618260.3649711.

[bib.bib21] [21] Mika Göös and Toniann Pitassi. Communication lower bounds via critical block sensitivity. SIAM Journal on Computing, 47(5):1778–1806, 2018. doi:10.1137/16M1082007.

[bib.bib22] [22] Mika Göös, Toniann Pitassi, and Thomas Watson. Query-to-communication lifting for BPP. SIAM Journal on Computing, 49(4), 2020. doi:10.1137/17M115339X.

[bib.bib23] [23] Dima Grigoriev. Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theoretical Computer Science, 259(1):613–622, 2001. doi:10.1016/S0304-3975(00)00157-2.

[bib.bib24] [24] 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.bib25] [25] Trinh Huynh and Jakob Nordström. On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 233–248. ACM, 2012. doi:10.1145/2213977.2214000.

[bib.bib26] [26] Russell Impagliazzo, Toniann Pitassi, and Alasdair Urquhart. Upper and lower bounds for tree-like cutting planes proofs. In Proceedings of the Ninth Annual Symposium on Logic in Computer Science (LICS ’94), Paris, France, July 4-7, 1994, pages 220–228. IEEE Computer Society, 1994. doi:10.1109/LICS.1994.316069.

[bib.bib27] [27] Dmitry Itsykson and Artur Riazanov. Proof complexity of natural formulas via communication arguments. In Valentine Kabanets, editor, 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference), volume 200 of LIPIcs, pages 3:1–3:34. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.CCC.2021.3.

[bib.bib28] [28] Dmitry Itsykson and Dmitry Sokolov. Resolution over linear equations modulo two. Ann. Pure Appl. Log., 171(1), 2020. doi:10.1016/J.APAL.2019.102722.

[bib.bib29] [29] 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.bib30] [30] 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.bib31] [31] László Lovász, Moni Naor, Ilan Newman, and Avi Wigderson. Search problems in the decision tree model. SIAM J. Discret. Math., 8(1):119–132, 1995. doi:10.1137/S0895480192233867.

[bib.bib32] [32] 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.bib33] [33] Marc Mezard, Giorgio Parisi, and Riccardo Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science (New York, N.Y.), 297:812–815, September 2002. doi:10.1126/science.1073287.

[bib.bib34] [34] Toniann Pitassi and Robert Robere. Lifting nullstellensatz to monotone span programs over any field. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1207–1219. ACM, 2018. doi:10.1145/3188745.3188914.

[bib.bib35] [35] 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.bib36] [36] Alexander A. Razborov. Applications of matrix methods to the theory of lower bounds in computational complexity. Comb., 10(1):81–93, 1990. doi:10.1007/BF02122698.

[bib.bib37] [37] Robert Robere, Toniann Pitassi, Benjamin Rossman, and Stephen A. Cook. Exponential lower bounds for monotone span programs. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 406–415. IEEE Computer Society, 2016. doi:10.1109/FOCS.2016.51.

[bib.bib38] [38] Anastasia Sofronova and Dmitry Sokolov. A lower bound for k-dnf resolution on random CNF formulas via expansion. Electron. Colloquium Comput. Complex., TR22-054, 2022. URL: https://eccc.weizmann.ac.il/report/2022/054.

[bib.bib39] [39] Dmitry Sokolov. (semi)algebraic proofs over $\pm$ 1 variables. 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 78–90. ACM, 2020. doi:10.1145/3357713.3384288.

[bib.bib40] [40] Dmitry Sokolov. Random $(\log n)$ -CNF Are Hard for Cutting Planes (Again). In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 2008–2015. ACM, 2024. doi:10.1145/3618260.3649636.

[bib.bib41] [41] Shuo Wang, Guangxu Yang, and Jiapeng Zhang. Communication Complexity of Set-Intersection Problems and Its Applications. Technical report, ECCC, 2023. URL: https://eccc.weizmann.ac.il/report/2023/164.

[bib.bib42] [42] Guangxu Yang and Jiapeng Zhang. Communication lower bounds for collision problems via density increment arguments. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 630–639, New York, NY, USA, 2024. Association for Computing Machinery. doi:10.1145/3618260.3649607.

Searching for Falsified Clause in Random (log⁡(n))-CNFs Is Hard for Randomized Communication

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Definition 1 ([31]).

Proof complexity.

Circuit complexity.

1.1 Random CNF

Definition 2.

Theorem 3 (Chvátal–Szemerédi, [7]).

Theorem 4.

1.2 Prior Results and Technique

2 Notation and Tools

Definition 5.

Lemma 6.

3 Refuting Bipartite CNFs

Theorem 7.

3.1 Deriving Theorem 4 from Theorem 7

Lemma 8.

Proof of Theorem 4.

3.2 Density Restoring Machinery

Definition 9 (Min-entropy).

Definition 10 (Spread variables).

Definition 11 (Structured variables).

Definition 12 (Subcube-like rectangle).

Definition 13 (Subcube-like protocols [14]).

Definition 14 (Codimension).

Lemma 15 (Density Restoring Partition [22]).

3.3 Subcube-like protocols from general protocols

Lemma 16 ([14]).

Lemma 17.

Proof.

Fact 18.

Proof.

Claim 19.

Proof.

Claim 20.

Proof.

Lemma 21.

3.4 Lower bound against subcube-like protocols

Lemma 22.

Lemma 23.

Proof.

Claim 24.

Proof.

Claim 25.

Proof.

3.5 Proof of Theorem 7

Proof.

References

Appendix A Proof of Lemma 8

Appendix B Proof of Lemma 22

Lemma 26.

Proof of Item (c).

Proof of Item (a).

Appendix C Proof of Lemma 21

Lemma 21. [Restated, see original statement.]

Proof.

Searching for Falsified Clause in Random $(\log{n})$ -CNFs Is Hard for Randomized Communication