Hardness of Clique Approximation for Monotone Circuits

We prove a lower bound on the size of monotone circuits solving the promise problem ${\mathrm{GAP}}_{\alpha ,\beta }(n)$.

To prove a lower bound on ${\mathrm{GAP}}_{\alpha ,\beta }(n)$, we introduce an associated strengthened distributional problem $𝒟({𝒯}_{\alpha }^{-},{𝒯}_{\beta }^{+})$ to distinguish two graph distributions ${𝒯}_{\alpha }^{-}$ and ${𝒯}_{\beta }^{+}$.

Note that $\alpha$ is chosen so that $𝒟({𝒯}_{\alpha }^{-},{𝒯}_{\beta }^{+})$ is associated with ${\mathrm{GAP}}_{\alpha ,\beta }(n)$ as the probability that a graph drawn from ${𝒯}_{\alpha }^{-}$ contains a clique of size $\alpha$ is small – a simple union bound can be used to argue that for $\alpha \ge 4$. As such, any circuit solving the problem ${\mathrm{GAP}}_{\alpha ,\beta }$ can distinguish ${𝒯}_{\alpha }^{-}$ from ${𝒯}_{\beta }^{+}$, and conversely, a lower bound for $𝒟({𝒯}_{\alpha }^{-},{𝒯}_{\beta }^{+})$ implies a lower bound for ${\mathrm{GAP}}_{\alpha ,\beta }$.

Our main results are lower and upper bounds on the monotone complexity of $𝒟({𝒯}_{\alpha }^{-},{𝒯}_{\beta }^{+})$, captured in the following two theorems.

We want to emphasize a special case of $\alpha =2{\log }_{2}n+1$ (or, equivalently, the negative distribution ${𝒯}^{-}$ being an Erdős–Rényi graph ${𝒢}_{n,p}$ with $p=1/2$). In this case, according to Theorem 4, we can choose $\delta =\sqrt{1/\log n}$ to get a polynomial-size circuit, rejecting ${𝒢}_{n,p}$ yet accepting a clique of size $\beta =n/2^{C\sqrt{\log n}}$. On the other hand, Theorem 3 states that if we wanted to reject ${𝒢}_{n,1/2}$ and accept a clique of size $\beta$, where $\beta =n/2^{\omega (\sqrt{\log n})}$, we would need a circuit of size $n^{\omega (1)}$.

As such, our two theorems provide a near-tight characterization of the power of polynomial-size monotone circuits to distinguish the ${𝒢}_{n,1/2}$ graph from a large clique.

Another interesting corollary of Theorem 3, is obtained by setting $\beta =\alpha$, and taking $\alpha$ as large as possible while satisfying the restriction , in order to obtain a strongest possible lower bound for the clique problem.

Note that no truly exponential lower bounds for the monotone circuit size are known for any explicit monotone problem. A lower bound of $2^{\tilde{\mathrm{\Omega }}(\sqrt{n})}$ (where $n$ is the size of the input) was shown for the arguably less-natural Harnik-Raz function [13] in [8], breaking the long-standing barrier of $2^{\tilde{\mathrm{\Omega }}(n^{1/3})}$ – and using the same breakthroughs in sunflower lemmas that are crucial in our improvement.

In our case, the input is an adjacency matrix of a graph on $n$ vertices hence the input has $m=\mathrm{\Theta }(n^2)$ bits; our lower bound, in terms of the input size, is then $2^{\mathrm{\Omega }(m^{1/4})}$ – the exponent is still by a factor of two worse than in the strongest known lower bound for any explicit monotone function.

Let us briefly recall the idea behind the approximation method for showing monotone circuit lower bounds, introduced by Razborov [19], and then utilized by [1, 8].

In order to show a lower bound for a size of a monotone circuit distinguishing two specific distributions ${𝒯}^{+}$ and ${𝒯}^{-}$, we proceed by inductively (gate-by-gate) approximating any given circuit $C$ by a simpler circuit $\widehat{C}$ (from some class of simple circuits).

If we can show that

1. 1.

   Every simple circuit fails to distinguish between ${𝒯}^{+}$ and ${𝒯}^{-}$ – that is, for all simple $\widehat{C}$, we have ${𝔼}_{x\sim {𝒯}^{+}}\widehat{C}(x)-{𝔼}_{x\sim {𝒯}^{-}}\widehat{C}(x)\le o(1)$.

2. 2.

   In each gate, by applying the approximation, we introduce error at most $\delta$ on both positive and negative distribution.

That implies a lower bound $\mathrm{\Omega }({\delta }^{-1})$ for the size of the smallest monotone circuit $C$ distinguishing those two distributions.

For the clique problem (say, distinguishing random ${𝒢}_{n,p}$ graph which likely does not even have a clique of size $\alpha$, from a uniformly random clique of size $\beta \ge \alpha$), following [19, 1, 8], the “simple” circuits we use to approximate a given circuit are just small DNF formulas, specifically conjunctions of clique indicators – that is circuits of form

where

Moreover, a circuit is simple if the size of each clique indicator is bounded by $c$ (we will eventually choose $c:=\delta \alpha$), and the number of clique indicators of each size $\mathrm{\ell }\le c$ is appropriately bounded.

At a given gate, we wish to approximate a conjunction or a disjunction of two such simple circuits again by a simple circuit. By applying de Morgan laws in the conjunction case, we can transform the circuit again into DNF (without introducing any error).

Then, we repeat the following three steps, transforming the DNF obtained this way into a simple one.

1. 1.

   We replace all conjunctions ${𝒦}_{A_i}\wedge {𝒦}_{A_j}$ by clique indicators ${𝒦}_{A_i\cup A_j}$.

2. 2.

   As long as there is a family of cliques on sets $A_{i_1},\mathrm{\dots }{A}_{i_k}$ having a specific combinatorial structure, we replace all of them by a clique on the set $C$, where $C$ is the intersection of $A_{i_j}$.

3. 3.

   We remove all clique indicators ${𝒦}_{A_i}$ for $A_i$ larger than threshold $c$.

As it turns out, step 1 does not introduce any error on both the positive and negative distributions.

Step 3 can introduce error only on the positive distribution, which can be bounded by union bound – any given large clique indicator is unlikely to be satisfied by a large random clique. The number of those large clique indicators we discard is bounded (otherwise, we would have been able to apply step 2).

Finally, step 2 is the crux of the argument – we need to show that if the number of indicators of a given size is too large, then there always is a subset of those indicators that can be replaced by its intersection $C$ (the core), without introducing too much error on the negative distribution (clearly we will not introduce any error on the positive distribution in this case).

In the Razborov’s proof and some presentations of the Alon-Boppana proof (see for example [16, Chapter 9]), one can focus on finding a sunflower consisting of many sets among the set system $\{A_i\}$ (a sunflower is a family of sets for which all pairwise intersections are the same, see Section 1.3), and show that replacing a large sunflower by its core introduces only small error on the negative distribution. This, together with the Erdős-Rado result that any large enough family of bounded sets contains a large sunflower, gives an upper bound on the number of clique indicators of size $\mathrm{\ell }$ for a “simple circuit” (one on which the step 2 can no longer be applied), and hence yields a complete proof of a monotone circuit lower bound for the clique problem. Specifically, going carefully through the calculations, one could show this way a lower bound $n^{\mathrm{\Omega }(\sqrt{k})}$ for the ${\text{Clique}}_k$ problem whenever $k\le n^{1/2-\delta }$, translating to a $2^{\tilde{\mathrm{\Omega }}(n^{1/4})}$ lower bound for the Clique problem after taking optimal $k$. ¹¹1In the actual Alon-Boppana paper, they used a slightly more general combinatorial structure than sunflowers: a sequence of distinct sets $A_{i_1},\mathrm{\dots }{A}_{i_k}$, together with a set $C\subset A_t$ (not necessarily distinct from $A_{i_1},\mathrm{\dots }{A}_{i_k}$), s.t. all pairwise intersections $A_{i_s}\cap A_{i_r}\subset C$ – and they replaced $A_{i_1},\mathrm{\dots }{A}_{i_k}$ by $C$ in step 2 here. Clearly any sunflower $A_{i_1}\mathrm{\dots }{A}_{i_k}$ with the core $C=\bigcap A_{i_j}$ satifies this property. By using this more general structure, they were able to show a lower bound $n^{\sqrt{k}}$ for $k\le n^{2/3}$ – matching the result one would get insisting on using a sunflower here if the sunflower conjecture was true; yet without having to prove this conjecture.

The work of Cavalar, Kumar, and Rossman [8], introduced a notion of robust clique-sunflower, which abstracts exactly the property needed to bound the error introduced on the negative distribution ${𝒢}_{n,p}$ by replacing the robust clique sunflower by its core. They showed better quantitative bounds on the size of the set system needed to contain such a robust clique sunflower and were able to deduce a lower bound $n^{\tilde{\mathrm{\Omega }}(k)}$ for $k\le n^{1/3-\delta }$ – matching the same $2^{\tilde{\mathrm{\Omega }}(n^{1/3})}$ for the clique problem when picking largest admissible $k$.

We define the robust clique sunflower (after [8]) – a notion abstracting the main property of combinatorial sunflowers used to obtain a monotone lower bound for the ${\text{Clique}}_k$ problem, where the negative distribution is ${𝒢}_{n,p}$. This property ensures that for a DNF formula

if some of those sets $A_i$ form a robust clique sunflower, we can replace them by a single clique indicator on the common intersection $C$ while introducing only a small error on the negative distribution (and no error on the positive distribution).

This notion is intimately related to a similar notion of a robust sunflower, originally introduced in [20].

As it turns out, any large enough family of sets of size $\mathrm{\ell }$ contains a robust sunflower or a robust clique sunflower. We introduce a notation for the dependence between the size of the family and the parameters of this sunflower.

Note that a family $𝒮\subset 2^{[n]}$ is a robust clique sunflower (as in the Definition 6), if and only if the family of edge-sets $\{K_S:S\in 𝒮\}$ is a robust sunflower. This observation implies a simple (yet unsatisfactory) bound

In Section 1.4 (for instance Theorem 14) we provide a quantitative statement for how the upper bounds on $RCB$ can be translated into lower bounds for the Clique problem.

For completeness, let us discuss a way to reinterpret a result similar to the Alon-Boppana (with the negative distribution being ${𝒢}_{n,p}$ instead of random $(\alpha -1)$-partite graph) in this framework, by deducing a bound on the robust clique sunflowers from the sunflower bound.

What we call a $k$-sunflower is sometimes called in the literature a sunflower with $k$-petals. We chose a slightly more concise terminology.

A sunflower lemma [10] now says that for every $\mathrm{\ell }$ and $k$, there is a finite number $S(\mathrm{\ell },k)\le \mathrm{\ell }!{(k-1)}^{\mathrm{\ell }}$ such that every $\mathrm{\ell }$-uniform set system of size at least $S(\mathrm{\ell },k)$ has a $k$-sunflower. Subsequent results, including the breakthrough by [2] and improvements [5, 17, 23, 14, 18] provide successively smaller upper bounds on $S(\mathrm{\ell },k)$, concluding with the best currently known bound

while the famous sunflower conjecture ([10]) stipulates that $S(\mathrm{\ell },k)\le O{(k)}^{\mathrm{\ell }}$.

The following observation, similar in form to the core of the Razborov and Alon-Boppana results, is a simple way to connect sunflowers to robust clique sunflowers.

We carry over the high-level structure of the proof outlined in Section 1.2 in more detail in Section 2. This part of the proof is technically very similar to known results applying the approximation method (for example [19, 1, 8]). However, in contrast with many of the previous work, we made an effort to provide a statement of the lower bound theorem parameterized by the robust clique sunflower numbers $RCB(\mathrm{\ell },p,\epsilon )$ – which, in turn, can be upper bounded in several ways by the robust sunflower numbers $RB(\mathrm{\ell },p,\epsilon )$, or sunflower numbers $S(\mathrm{\ell },k)$ as discussed in Section 1.3.

Making these dependencies explicit instead of choosing optimal values of relevant parameters ahead of time based on currently best-known bounds on sunflower numbers makes the interplay between sunflower-like combinatorial statements and monotone lower bounds for the clique problem much clearer.

Moreover, our analysis allows us to show the inapproximability results (Theorem 3) – i.e., hardness of distinguishing a random clique of size $\beta$, from a random graph ${𝒢}_{n,p}$ which is unlikely to even have a clique of size $\alpha$ for .

The analysis of [19, 8] focused on the exact case, i.e., $\beta =\alpha$; whereas in [19, 1], the negative distribution was chosen to be a random complete $(\beta -1)$-partite graph. However, this choice was not crucial in their reasoning – only simple modifications are needed to adapt their proofs to the ${𝒢}_{n,p}$ being the negative distribution.

As we have been made aware recently, an even more general statement can be found [6, Theorem 5.6.4] – the following theorem can be deduced as a corollary of their more general framework, by a concrete instantiation of their notion of the notion of abstract sunflower to denote the robust clique sunflower.

It is instructive to see how to essentially recover the Alon-Boppana bounds from Theorem 14, using a simple lemma stating that large enough sunflowers are robust clique sunflowers (Lemma 10) together with the new bounds on the sunflower numbers (2). In this case, we have an upper bound on the

so taking $c:=O(\sqrt{\delta \alpha })$ for a small constant $\delta$, such that $RCB{(\mathrm{\ell },p,\epsilon )}^{1/\mathrm{\ell }}\le n^{\delta }\sqrt{\alpha }\log n$, we end up with a complexity lower bound $n^{\mathrm{\Omega }(\delta c)}=n^{\mathrm{\Omega }(\sqrt{\alpha })}$, as long as

recovering [1, Theorem 3.11]. Setting $\alpha =\beta$, gives a lower bound of form $n^{\mathrm{\Omega }(\sqrt{\alpha })}$ as long as $\alpha \le n^{2/3-\delta }$.

In a similar vein, plugging in the upper bound (3) for $RCB(\mathrm{\ell },p,\epsilon )$ (originally shown in [8, Lemma 3.2]), yields the lower bound $n^{\mathrm{\Omega }(\alpha )}$, as long as ${\alpha }^2\beta \le n^{1-\delta }/\log n$, and again choosing $\alpha =\beta$ yields an $n^{\mathrm{\Omega }(\alpha )}$ for $\alpha \le n^{1/3-\delta }$, recovering their [8, Theorem 3.23].

Finally, Theorem 14 together with our new bounds for the robust clique numbers (Corollary 13) directly imply the lower bound claimed in Theorem 3.

For the sake of abstraction, we describe a general inductive procedure of converting any monotone circuit $C$ computing a distributional decision problem $𝒟({𝒯}^{-},{𝒯}^{+})$, gate by gate, into an approximation circuit $\widehat{C}\in 𝒜$ from a set of approximation circuits $𝒜$. This procedure depends on a pair of “compression” functions ${𝒫}^{\wedge },{𝒫}^{\vee }:𝒜\times 𝒜\to 𝒜$. The error introduced by the conversion, with respect to the distributions ${𝒯}^{+}$ and ${𝒯}^{-}$, will depend solely on $𝒫$.

Depending on the choice of $𝒫$, $\widehat{C}$ can be very different from $C$. For the sake of analysis, we are interested in the maximum error that a single transformation step can introduce on either distribution.

We can also formalize the earlier intuition about proving circuit size lower bounds using the relative and absolute approximation errors.

We say that a circuit is $𝒫$-simple if it is in the image of the compression function $𝒫$.

In the following, we will specialize the definition of the approximation circuits $𝒜$ and the compression functions $({𝒫}^{\wedge },{𝒫}^{\vee })$ to prove the lower bounds on $𝒟({𝒯}_{\alpha }^{-},{𝒯}_{\beta }^{+})$.

We will often freely switch between the formal definition of an approximator as a Boolean circuit $A={\bigvee }_{i=1}^m{𝒦}_{A_i}$ and its representation as a set system over the universe of graph vertices $A=\{A_1,\mathrm{\dots },A_m\}\subseteq 2^{2^{[n]}}$.

We observe that for the identity $\tau =id$, $𝒫$ introduces no error on the graph distributions ${𝒯}_{\alpha }^{-}$ and ${𝒯}_{\beta }^{+}$. Indeed, the positive distribution is supported on the $\beta$ cliques. A $\beta$-clique $G$ contains both cliques $K_{X_i}$ and $K_{Y_j}$ if and only if it contains a clique $K_{X_i\cup Y_i}$. On the other hand, on the negative distribution, transforming a conjunction $K_{X_i}\wedge K_{X_j}$ into the clique indicator $K_{X_i\cup Y_j}$ can only reject more instances. Thus, the error only depends on the choice of $\tau$. For constructing such $\tau$, we will use the robust clique sunflowers.

For a DNF formula $A:={\bigvee }_{i=1}^m{𝒦}_{A_i}$ we define $c{l}_{p,\epsilon }(A)$ to be a formula obtained from $A$ by repeatedly replacing any $(p,\epsilon )$-robust clique sunflower $A_{i_1},\mathrm{\dots }{A}_{i_k}$ by its core $C:={\bigcap }_j{A}_{i_j}$, as long as there is such a robust clique sunflower, interleaved with removing all sets $A_j$, s.t. $A_i\subset A_j$ for some $A_i$. The ${\mathrm{trim}}_c(A)$ will be a circuit obtained from $A$ by removing all sets $|A_i|>c$.

Finally, we will choose the inner compression function (used in Definition 20) as

We say that a circuit $A$ is $(p,\epsilon )$-closed, if there are no $(p,\epsilon )$-robust sunflowrers among the sets $A_1,\mathrm{\dots }{A}_m$. The bound on the number of sets $A_j$ of a given size for an $(p,\epsilon )$-closed circuit is a direct consequence of the definition of a closed circuit and the $RCB$ numbers.

A crucial property that we will exploit both in the analysis of the approximator as well as in the construction of an explicit algorithm solving $𝒟({𝒯}_{\alpha }^{-},{𝒯}_{\beta }^{+})$ is that the positive test distribution ${𝒯}_{\beta }^{+}$ is “well-spread” in a sense that it is unlikely for a large clique-indicator to accept many instances of ${𝒯}_{\beta }^{+}$.