Average-Case Hardness of Binary-Encoded Clique
in Proof and Communication Complexity

Another type of evidence for hardness comes from propositional proof complexity, the study of the complexity of certifying, in various formal proof systems, that a given Boolean formula is a tautology or that it is unsatisfiable.

Proof complexity provides a perspective to analyze several algorithmic approaches to the $k$-Clique problem: If an algorithm rejects a $k$-Clique instance, the trace of its execution can be viewed as a certificate of the claim that the given graph does not contain a $k$-clique. This claim can be encoded as a CNF formula asserting that the graph does have a $k$-clique, and in this paper we study certificates of unsatisfiability, also called refutations, of this formula. Many classes of algorithms can be captured by propositional proof systems in this way: the core reasoning of state-of-the-art SAT-solvers is captured by resolution [4]; Gröebner basis algorithms by polynomial calculus [17]; the cutting planes methods in integer linear optimization by the cutting planes proof system [18]; and the Lassere hierarchy in semi-definite programming [40] by the sum-of-squares proof system.

Assuming the Nondeterministic Exponential Time Hypothesis [13], in every proof system the shortest refutation of $k$-Clique for some graph has length at least $N^{\mathrm{\Omega }(k)}$. On the other hand, unconditional lower bounds are only known for very restricted proof systems. Two encodings of the clique problem into CNF formulas are studied in the literature. The unary encoding uses $N$ propositional variables to encode the $i$th vertex of the purported $k$-clique, for every $i$, while the more succinct binary encoding uses only $\log N$ variables to encode the same information in binary.

The following results are known about the unary encoding. For treelike resolution, there are $N^{\mathrm{\Omega }(k)}$ length lower bounds even on average with respect to the Erdős-Rényi graph distribution [7, 41]. The current best known results are analogous average-case bounds for regular resolution [2], and Sherali–Adams with bounded coefficients [20]. For general resolution, in the parameter range $N^{5/6}\ll k\le N/3$, an $\exp (N^{\mathrm{\Omega }(1)})$ average-case lower bound for dense graphs is known [3], and when , an average-case lower bound $2^{k^{1-\epsilon }}$ holds [43]. Improving this to an optimal $N^{\mathrm{\Omega }(k)}$ lower bounds is a long-standing open problem, see, e.g., [8, 11], even for worst-case instances. In particular, all known techniques for proving resolution lower bounds seem to fail for this task [2].

Weak proof systems can, however, be very sensitive to the choice of encoding, as was shown in, e.g., [19]. This is also the case for the binary encoding of clique, where strong lower bounds are known for resolution: There is an $N^{\mathrm{\Omega }(k)}$ average-case lower bound for resolution [42], which was further extended to $s$-DNF resolution, for $s=o(\log \log n)$, at the cost of some loss in the exponent of the bound depending on $s$ [19].

We prove new lower bounds for $k$-Clique in three settings. Our first result is that the binary encoding of $k$-Clique requires exponential proof length in cutting planes. Prior to our work, nothing was known about the hardness of $k$-Clique for cutting planes, even in the treelike setting.

We consider next the frontier proof system resolution over parities ($\mathrm{Res}(\oplus )$) [35], which recently received a lot of attention [10, 1, 23, 9, 12], particularly following the breakthrough of [22]. Lower bounds are only known for restricted versions of this system, and in particular, nothing is known about the hardness of refuting $k$-Clique in $\text{Res}(\oplus )$. We prove the following length lower bound on $\text{Res}(\oplus )$ proofs of bounded depth.

Lastly, we study the communication version of the problem. Two parties are both given partial information about the members of a purported $k$-clique in a graph $G$. Again, $G$ does not actually have a $k$-clique, and the parties must find a missing edge in the purported clique, while communicating as few bits as possible. This corresponds to finding a falsified clause in the binary-encoded clique formula, if the partial information consists of the bits encoding the purported clique members. We prove the following lower bound in the setting where the parties have access to shared randomness.

Randomized communication complexity remains the most versatile tool for obtaining lower bounds for treelike cutting planes. Most of the known lower bounds are obtained via this connection [33, 5, 32, 28, 34]. Treelike cutting planes is a natural next candidate for proving clique lower bounds in the unary encoding.

There is, however, a growing evidence that the randomized communication model is too strong to give strong lower bounds for $k$-Clique. If, for example, the density of Erdős-Rényi graph is constant, then Alice and Bob can randomly sample a pair of indices of their nodes and verify whether or not the corresponding pair is connected with an edge. Thus, we can only hope for a non-trivial lower bound for the dense setting of $k$-Clique. Another weakness of the communication approach to $k$-Clique lower bounds was established by Jukna [36], who observed that for a bipartite version of the unary $k$-Clique, the corresponding problem has a $O(\log n)$-cost deterministic communication protocol.

Given these drawbacks, we view Theorem 1.3 as an indication of some hope for the communication approach to $k$-Clique lower bounds: at least in the dense binary setting the barriers above do not apply. Moreover, Theorem 1.3 (qualitatively) generalizes the main theorem in [51] with a much simpler proof.

Our contributions can be viewed as matching the lower bounds known for the weak version of binary pigeonhole principle (BPHP) with bounds for the binary encoding of $k$-Clique. In fact, all three bounds are obtained by adapting the techniques previously used to prove lower bounds for the weak binary pigeonhole principle [6, 12], or by adapting extensions of such techniques [25, 51]. Is there a more general principle behind our results, i.e., is there an explicit reduction from BPHP to average-case $k$-Clique? We know such a reduction exists in the worst case – indeed, the BPHP is a special case of the binary-encoded $k$-Clique– but in the average case such reductions are not known.

One concrete direction would be to prove

lower bounds on $k$-Clique in the treelike version of $\mathrm{Th}(2)$, the generalization of cutting planes refutations to degree-$2$ inequalities. Only the strong BPHP is known to be hard for this system [34], and the proof of this fact uses global symmetries of the formula. Therefore, it is unclear how to apply the technique to $k$-Clique for an Erdős-Rényi random graph, since the latter is unlikely to have symmetries. Does it fail because of the particular technique, or is the strong version of BPHP crucially easier than the weak one?

Another interesting direction to extend our lower bounds is to the Ramsey principles [42]. A graph is $c$-Ramsey if it has neither a clique nor an independent set of size $c\log n$. The Ramsey principle formulas defined in [42] encodes in binary the claim that a given graph is $c$-Ramsey. For resolution, an asymptotically optimal $n^{\mathrm{\Omega }(\log n)}$ length lower bound was proven in [42]. We ask the same question for cutting planes and $\text{Res}(\oplus )$.

In particular, matching the bounds known for resolution would require improving our lower bounds and extending them to randomly sampled graphs for a broader range of parameters, specifically to graphs which are not as dense.

As discussed above, for sparse graphs there is always a randomized communication protocol solving $k$-Clique in binary or unary encoding. However, we can weaken the communication model so it still captures tree-like cutting planes. One such model is a deterministic communication protocol with a Greater Than oracle, i.e., the players can compare real numbers at unit cost.

This model is shown to be significantly weaker than randomized communication [14, 16, 26]. Can we still solve $k$-Clique over a sparse graph?

We give a brief technical overview of our proofs. Notably, all of our techniques are to some extent based on previous work proving lower bounds on BPHP.

The rest of this paper is organized as follows. In Section 2 we give some preliminaries and in Section 3 we introduce some useful combinatorial properties of random graphs. In Section 4 we present our result for cutting planes and in Section 5, we show our theorem for $\text{Res}(\oplus )$. Finally, we prove our lower bound for randomized communication in Section 6. For complete proofs of our results, we refer to the full version of this paper [21].

Let $G$ be a graph over $k$ blocks $V(G)=V_1\bigsqcup \mathrm{\cdots }\bigsqcup V_k$, with $|V_i|=n$ for all $i\in [k]$. In everything that follows, let us assume, without loss of generality, that $n$ is a power of 2. For $u\in V(G)$, let $B(u)\in [k]$ denote the index of the block that contains $u$, and for every set of vertices $U\subseteq V(G)$, we define $B(U)≔\{B(u)\mid u\in U\}$. For a subset $U\subseteq V(G)$ we use $N^{\cap }(U,i)$ to denote the common neighborhood of $U$ at block $i$. For a set of blocks $I\subset [k]$, we then use $N^{\cap }(U,I)={\bigcup }_{i\in I}{N}^{\cap }(U,i)$. For all $i\in [k]$, every $u\in V_i$ can be identified with an integer in $[n]$, and we denote its binary representation by $\mathrm{𝖻𝗂𝗇}(u)=u_1\mathrm{\dots }{u}_{\log (n)}$.

The natural distribution for which $k$-Clique is conjectured to be hard is an Erdős-Rényi distribution. The $p$-biased Erdős-Rényi distribution $𝒢(n,p)$ is defined by sampling an $n$-vertex graph with each of the $\left(\genfrac{}{}{0pt}{}{n}{2}\right)$ edges present with probability $p$ independently of the other edges. The parameter $p$ that conjecturally makes finding a $k$-clique in $𝑮\sim 𝒢(n,p)$ hard is at the threshold $p^{\prime }$ where for a lower the graph $𝑮$ does not have a $k$-clique a.a.s., and for a higher $p>p^{\prime }$ it does have a $k$-clique a.a.s.. By looking at the expected number of $k$-cliques in $𝑮$, one can conclude that the threshold value is $\mathrm{\Theta }(n^{-2/(k-1)})$.

We also define the $k$-partite version of the same distribution: For a fixed partition of the nodes, $𝒢(n,p,k)$ is sampled from by first sampling $𝑮\sim 𝒢(nk,p)$ and then intersecting $𝑮$ with a complete $k$-partite graph with $n$ nodes in each part.

We next recall some basic notions from proof complexity; see, e.g., [38, 11] for a more thorough exposition. A Boolean variable $x$ or its negation $\overline{x}$ is called a literal, and a disjunction of literals over pairwise disjoint variables $C={\mathrm{\ell }}_1\vee \mathrm{\cdots }\vee {\mathrm{\ell }}_k$ is called a clause. A CNF formula is a conjunction of clauses $F=C_1\wedge \mathrm{\cdots }\wedge C_m$. We sometimes call the clauses of $F$ axioms, and denote the set of variables occurring in $F$ as $\text{Vars}(F)$.

We encode the claim that a graph $G$ has a clique of size $k$. We use the so-called binary encoding [42, 19], where for every $i\in [k]$, there are $\log |V|$ variables to point out the $i$th member of a purported $k$-clique. For a propositional variable $x$, we use the notation $(x\ne 0)$ to denote the literal $x$, and $(x\ne 1)$ to denote the literal $\overline{x}$.

Assume that the vertices $v_i$, $v_j$ and $v$ are represented as $v_{i,1},\mathrm{\dots },v_{i,\log |V|}$, $v_{j,1},\mathrm{\dots },v_{j,\log |V|}$, and $v_1,\mathrm{\dots },v_{\log |V|}$ in binary, respectively. Let $x_{i,a}$, where $i\in [k]$ and $a\in [\log |V|]$, be propositional variables. The formula $\mathrm{𝖡𝖢𝗅𝗂𝗊𝗎𝖾}(G,k)$ consists of the clauses

The clauses (1) are called edge axioms, and the clauses (2) are called functionality axioms. The edge axioms encode that two non-neighbors are not simultaneously chosen as clique members, while the functionality axioms ensure that all clique members are distinct.

In this paper, we consider randomized (public coin) two party number-in-hand communication complexity. We quickly define the model and refer to [39, 44] for details.

Two players, Alice and Bob, are given inputs $x\in X$ and $y\in Y$, respectively. To solve a search problem $S\subseteq (X\times Y)\times 𝒪$, they need to find $o\in 𝒪$ such that $((x,y),o)\in S$, while communicating as few bits as possible. A deterministic communication protocol $\mathrm{\Pi }$ for $S$ is a rooted binary tree as follows. Every internal node $v\in \mathrm{\Pi }$ determines who is going to speak, and the spoken bit, which is a function of $v$ and the input $x$ or $y$ ($x$ if Alice speaks, $y$ otherwise), determines which child of $v$ the computation moves to. Every leaf $\mathrm{\ell }\in \mathrm{\Pi }$ is labeled by $o_{\mathrm{\ell }}\in 𝒪$, such that $((x,y),o_{\mathrm{\ell }})\in S$. We define a randomized communication protocol ${\mathrm{\Pi }}_r$ for $S$ as a distribution over deterministic communication protocols, such that the computation is correct with constant probability. The cost of a deterministic protocol $|\mathrm{\Pi }|$ is the maximum, over all inputs, of the number of bits communicated. The cost of a randomized protocol $|{\mathrm{\Pi }}_r|$ is the maximum cost among the deterministic protocols in the distribution.

We study the communication complexity of ${\mathrm{Search}}_{\mathrm{𝖡𝖢𝗅𝗂𝗊𝗎𝖾}(G,k)}^{X,Y}$, where we split the variables of $\mathrm{𝖡𝖢𝗅𝗂𝗊𝗎𝖾}(G,k)$ such that Alice and Bob each get half of the bits from every clique member, i.e., $X=Y={({\{0,1\}}^{\log |V|/2})}^k$, and denote this problem by ${\mathrm{𝖡𝖢𝗅𝗂𝗊𝗎𝖾}}^{cc}(G,k)$. As in the proof complexity setting, a version of Lemma 2.5 applies and we may prove lower bounds for the block encoding, i.e., for ${\mathrm{𝖡𝖢𝗅𝗂𝗊𝗎𝖾}}_{\text{block}}^{cc}(G,k)$.

Furthermore, we will make use of the characterization of randomized communication cost in terms of distributional communication complexity [52]: To prove a lower bound on the randomized communication cost, it is enough to prove a lower bounds on deterministic protocols with constant error probability for any input distribution. In particular, we will prove a lower bound for the uniform distribution.

Here we collect some technical preliminaries that are used only in this section. We start by recalling the notion of safe systems, introduced by [22].

We say that a set of linear forms $F$ over variables $x_{i,j}\in {({\{0,1\}}^{\log n})}^{[k]}$ is dangerous if the number of distinct blocks from which variables appear in $F$ is smaller than the size of $F$. If no subset of $F$ is dangerous we say that $F$ is safe. It turns out that safe sets have a very nice characterization making them nice to work with.

To handle non-safe systems we use the notion of closure. The closure of $F$, $\mathrm{Cl}(F)\subseteq [k]$ is defined as the minimal set (with respect to inclusion) of blocks such that $F[\setminus \mathrm{Cl}(F)]$ is safe, where $F[\setminus S]$ denotes the set of linear forms $F$ after setting variables belonging to a block in $S$ to zero. It turns out that the closure is uniquely defined [22, Lemma 4.1]. In an abuse of notation we will, for a linear system $\mathrm{\Psi }$, write $\mathrm{Cl}(\mathrm{\Psi })$ to refer to the closure of

To assign variables in a way that satisfies linear systems, we need the concept of affine restrictions. A (block respecting) affine restriction $\rho$ is a partial assignment that for some set $F\subseteq [k]$ sets all variables $x_{i,j}$, $i\in [k]\setminus F$ as an affine function of the unassigned variables $x_{i,j}$, $i\in F$. In this paper all affine restrictions will be block respecting and will for brevity just be called affine restrictions. For a linear system $\mathrm{\Psi }$ we use ${\mathrm{\Psi }|}_{\rho }$ to denote the system after substituting variables according to $\rho$.

We introduce the search problem ${\mathrm{NonEdge}}_M^G\subseteq {({\{0,1\}}^{\log n})}^{[k]\setminus B(M)}\times \left(\genfrac{}{}{0pt}{}{V(G)}{2}\right)$, where $M$ is some set of vertices of $G$ such that vertices in $M$ from distinct blocks in $G$ always have edges between them. As input we are given an assignment to the blocks outside of the support of $M$ such that every selected vertex lies in $N^{\cap }(M,[k]\setminus B(M))$. We are then asked to output two selected vertices not connected by an edge. When the graph $G$ is clear from context, we simply write ${\mathrm{NonEdge}}_M$. Observe that ${\mathrm{NonEdge}}_M^G$ is equivalent to ${\mathrm{Search}}_{\mathrm{𝖡𝖢𝗅𝗂𝗊𝗎𝖾}(G^{\prime },k-|B(M)|)}$ where $G^{\prime }$ is the subgraph of $G$ induced by $N^{\cap }(M,[k]\setminus B(M))$. Thus, any affine-DAG solving the falsified clause search problem also solves ${\mathrm{NonEdge}}_{\mathrm{\varnothing }}^{\mathrm{G}}$, as such it is enough to find lower bound for this problem. The following lemma was stated in [12] with $A_1=A_2=\mathrm{\cdots }=A_n$. Their proof still works for or slightly more general formulation.

Throughout this section we let $\alpha$, be positive real values and a positive integer. Furthermore, we assume $G$ is a fixed graph with $(\alpha ,\beta ,R)$-bounded common neighborhoods. Note that this choice of parameters ensures that for every vertex set $|M|\le R$, $|N^{\cap }(M,i)|\le 2n/3$.

The proof of Theorem 5.2 follows the same strategy as [12]. Given an affine-DAG solving ${\mathrm{NonEdge}}_M$ we wish to find an affine-DAG of much smaller depth solving a slightly smaller instance ${\mathrm{NonEdge}}_{M^{\ast }}$; repeating this process shows that the original depth must have been large. Formally, we use the following lemma which we will spend the remainder of the section proving.

First we show how Theorem 5.2 follows from Lemma 5.6.