The Overlap Gap Property: a Topological Barrier to Optimizing over Random Structures

To set the stage, we consider a generic optimization problem $\min_{\sigma}\mathcal{L}(\sigma,\Xi_{N})$. Here $\mathcal{L}$ encodes the objective function (cost) to be minimized. The solutions $\sigma$ lie in some ambient solution space $\Sigma_{N}$, which is typically very high dimensional, often discrete, with $N$ encoding its dimension. The space $\Sigma_{N}$ is equipped with some metric (distance) $\rho_{N}(\sigma,\tau)$ defined for each pairs of solutions $\sigma,\tau\in\Sigma_{N}$. For the max-clique problem we can take $\Sigma_{N}=\{0,1\}^{N}$. For the Number Partitioning problem we can take $\Sigma_{N}=\{-1,1\}^{N}$. $\Xi_{N}$ is intended to denote the associated randomness of the problem. So, for example, for the max-clique problem, $\Xi_{N}$ encodes the random graph $\mathbb{G}(N,1/2)$, and $\sigma\in\{0,1\}^{N}$ encodes a set of nodes constituting a clique, with $\sigma_{i}=1$ if node $i$ is in the clique and $=0$ otherwise. We denote by $\xi$ an instance generated according to the probability law of $\Xi_{N}$. In the present context, $\xi$ is any graph, the likelihood of generating of which is $2^{-{N(N-1)\over 2}}$. Finally, $-\mathcal{L}(\sigma,\Xi_{N})$ is the number of ones in the vector $\sigma$. Now, if $\sigma_{N}$ does not actually encode a clique (that is for at least one of the edges $(i,j)$ of the graph we have $\sigma_{N,i}=\sigma_{N,j}=1$) we can easily augment the setup by declaring $\mathcal{L}(\sigma,\Xi_{N})=\infty$ for such ”non-clique” encoding vectors. For the Number Partitioning problem, $\Xi_{N}$ is just the probability distribution associated with an $N$-vector of independent standard Gaussians. For each $\sigma\in\Sigma_{N}=\{-1,1\}^{N}$ and each instance $\xi$ of $\Xi_{N}$, the value of the associated partition is $\mathcal{L}(\sigma,\xi)=|\langle\sigma,\xi\rangle|$. Here $\langle x,y\rangle$ denotes an inner product between vectors $x$ and $y$. Thus, for the largest clique problem we have that the random variable $c^{*}=-\min_{\sigma\in\Sigma_{N}}\mathcal{L}(\sigma,\Xi_{N})$ is approximately $2\log_{2}N$ with high degree of likelihood. For the Number Partitioning problem we have that $c^{*}=\min_{\sigma\in\Sigma_{N}}\mathcal{L}(\sigma,\Xi_{N})$ is approximately $\sqrt{N}2^{-N}$ with high degree of likelihood as well.

We now introduce the Overlap Gap Property (abbreviated as OGP) and its several variants. The term was introduced in [GL18], but the property itself was discovered by Achlioptas and Ricci-Tersenghi [ART06], and Mezard, Mora and Zecchina [MMZ05]. The definition of the OGP pertains to a particular instance $\xi$ of the randomness $\Xi_{N}$. We say that the optimization problem $\min_{\sigma}\mathcal{L}(\sigma,\xi)$ exhibits the OGP with values $\mu>0,0\leq\nu_{1}<\nu_{2}$ if for every two solutions $\sigma,\tau$ which are $\mu$-optimal in the additive sense, namely satisfy $\mathcal{L}(\sigma,\xi)\leq c^{*}+\mu,\mathcal{L}(\tau,\xi)\leq c^{*}+\mu$, it is the case that either $\rho_{N}(\sigma,\tau)\leq\nu_{1}$ or $\rho_{N}(\sigma,\tau)\geq\nu_{2}$. Intuitively, the definition says that every two solutions which are ”close” (within an additive error $\mu$) to optimality, are either ”close” (at most distance $\nu_{1}$) to each other, or ”far” (at least distance $\nu_{2}$) from each other, thus exhibiting a fundamental topological discontinuity of the set of distances of near optimal solutions. In the case of random instances $\Xi_{N}$ we say the the problem exhibits the OGP if the problem $\min\mathcal{L}(\sigma,\xi)$ exhibits the OGP with high likelihood when $\xi$ is generated according to the law $\Xi_{N}$. An illustration of the OGP is depicted on Figure 2. The notion of the ”overlap” refers to the fact that distances in normed space are directly relatable to inner products, commonly called overlaps in the spin glass theory, via $\|\sigma-\tau\|_{2}^{2}=\|\sigma\|_{2}^{2}+\|\tau\|_{2}^{2}-2\langle\sigma,\tau\rangle$, and the fact that solutions $\sigma,\tau$ themselves often have identical or close to identical norms. The OGP is of interest only for certain choices of parameters $\mu,\nu_{1},\nu_{2}$ which is always problem dependent. Furthermore, all of these parameters along with the optimal value $c^{*}$ are usually dependent on the problem size, such as the number of Boolean variables in the K-SAT model or number of nodes in a graph. In particular, the property is of interest only if there are pairs of $\mu$-optimal solutions $\sigma,\tau$ satisfying both $\rho_{N}(\sigma,\tau)\leq\nu_{1}$ and $\rho_{N}(\sigma,\tau)\geq\nu_{2}$ property. The first case is trivial as we can take $\tau=\sigma$, but the existence of pairs with distance at least $\nu_{2}$ needs to be verified. Establishing the OGP rigorously can be either straightforward or technically very involved, again depending on the problem. It is should not be surprising that the presence of the OGP presents a potential difficulty in finding an optimal solution, due to the presence of multiple local minima, similarly to the lack of convexity property. An important distinction should be noted, however, between the OGP and the lack of convexity property. The function $\mathcal{L}(\sigma,\xi)$ can be non-convex, but not exhibiting the OGP, as depicted on Figure 3. Thus the ”common” intractability obstruction presented by non-convexity is not identical with the OGP. Also, the solution space $\Sigma_{N}$ is often discrete (such as the binary cube) rendering the notions of convexity non-applicable.

We now extend the OGP definition to the so-called ensemble Overlap Gap Property, abbreviated as the e-OGP, and the multi-overlap gap property, abbreviated as the m-OGP. We say that a set of problem instances $\Xi$ satisfies the e-OGP with parameters $\mu>0,0\leq\nu_{1}<\nu_{2}$ if for every pair of instances $\xi,\psi\in\Xi$, for every $\mu$-optimal solution $\sigma$ of the $\xi$ instance (namely $\mathcal{L}(\sigma,\xi)\leq\min_{\sigma^{\prime}}\mathcal{L}(\sigma^{\prime},\xi)+\mu$), and every $\mu$-optimal solution $\tau$ of the $\psi$ instance (namely $\mathcal{L}(\tau,\psi)\leq\min_{\tau^{\prime}}\mathcal{L}(\tau^{\prime},\psi)+\mu$), it is the case that either $\rho_{N}(\sigma,\tau)\leq\nu_{1}$ or $\rho_{N}(\sigma,\tau)\geq\nu_{2}$, and in the case when instances $\xi$ and $\psi$ are probabilistically independent, the former case (i.e. $\rho_{N}(\sigma,\tau)\leq\nu_{1}$) is not the possible. The set $\Xi$ represents a collection of problem instances over which the optimization problem is considered. For example $\Xi$ might represent a collection of correlated random graphs $\mathbb{G}(N,1/2)$, or random matrices or random tensors. Indeed, below we will provide an example of a family of correlated random graphs $\mathbb{G}(N,1/2)$ as a main example of the case when the e-OGP holds. We see that the OGP is the special case of the e-OGP when $\Xi$ consist of a single instance $\xi$.

Finally, we say that a family of instances $\Xi$ satisfies the m-OGP with parameters $\mu,\nu_{1}<\nu_{2}$ and $m$, if for every $m$-collection of instances $\xi_{1},\ldots,\xi_{m}\in\Xi$ and every collection of solutions $\sigma_{1},\ldots,\sigma_{m}$ that are $\mu$-optimal with respect to $\xi_{1},\ldots,\xi_{m}$, at least one pair $\sigma_{i},\sigma_{j}$ satisfies $\rho_{N}(\sigma_{i},\sigma_{j})\leq\nu_{1}$ or $\rho_{N}(\sigma_{i},\sigma_{j})\geq\nu_{2}$. Informally, the m-OGP means that one cannot find $m$ near optimal solutions for $m$ instances such that all $m(m-1)/2$ pairs of distances lie in the interval $(\nu_{1},\nu_{2})$. Clearly the case $m=2$ boils down to the e-OGP discussed earlier. In many applications the difference between $\nu_{1}$ and $\nu_{2}$ is often significantly smaller than the value of $\nu_{1}$ itself, that is $\nu_{1}\approx\nu_{2}$. Thus, roughly speaking the m-OGP means that one cannot find $m$ near optimal solutions so that all pairwise distances are $\approx\nu_{1}$. The first usage of OGP as an obstruction to algorithms was adopted by Gamarnik and Sudan in [GS17a]. The first application of m-OGP as an obstruction to algorithms was adopted by Rahman and Virag in [RV17]. While their variant of m-OGP proved useful for some applications as in Gamarnik and Sudan [GS17b], and Coja-Oghlan, Haqshenas and Hetterich [COHH17], since then the definition of m-OGP has been extended to ”less symmetric” variants as one by Wein in [Wei20] and by Bresler and Huang in [BH21]. We will not discuss the nature of these extensions and instead refer to the aforementioned references for further details. e-OGP was introduced in Chen et al. [CGPR19].

Next we discuss how the presence of variants of the OGP constitutes an obstruction to algorithms. The broadest class of algorithms for which such an implication can be established are algorithms that are stable with respect to a small perturbation of instances $\xi$. An algorithm $\mathcal{A}$ is viewed here simply as a mapping from instances $\xi$ to solutions $\sigma$, which we abbreviate as $\mathcal{A}(\xi)=\sigma$. Suppose, we have a parametrized collection of instances $\xi_{t}$ with discrete parameter $t$ taking values in some interval $[0,T]$. We say that the algorithm $\mathcal{A}$ is stable or specifically $\kappa$-stable with respect to the family $(\xi_{t})$ if for every $t$, $\rho_{N}(\mathcal{A}(\xi_{t+1}),\mathcal{A}(\xi_{t}))\leq\kappa$. Informally, if we think of $\xi_{t+1}$ as an instance obtained from $\xi_{t}$ by a small perturbation, the output of the algorithm does not change much: the algorithm is not very sensitive to the input. Continuous versions of such stability have been considered as well, specifically in the context of models with Gaussian distribution. Here $t$ is a continuous parameter, and the algorithm is stable with sensitivity value $\delta$ if for every $t$ $\rho_{N}(\mathcal{A}(\xi_{t+\delta}),\mathcal{A}(\xi_{t}))\leq\kappa$. Often these bounds are established only with probabilistic guarantees, both in the case of discrete and continuously valued $t$.

Now assume that the e-OGP holds for a family of instances $\xi_{t},t\in[0,T]$. Assume two additional conditions: (a) the regime $\rho_{N}(\sigma,\tau)\leq\nu_{1}$ for $\mu$-optimal solutions $\sigma$ of $\xi_{0}$, and $\mu$-optimal solutions $\tau$ of $\xi_{T}$ is non-existent (namely every $\mu$-optimal solution of $\xi_{0}$ is ”far” from every $\mu$-optimal solution of $\xi_{T})$; and (b) $\kappa<\nu_{2}-\nu_{1}$. The property (a) is typically verified since the end points $\xi_{0}$ and $\xi_{T}$ of the interpolated sequence are often independent, and (a) can be checked by straightforward moment arguments. The verification of condition (b) typically involves technical and problem dependent arguments. The conditions (a) and (b) above plus the OGP allow us to conclude that any $\kappa$-stable algorithm fails to produce a $\mu$-optimal solution. This is seen by a simple contradiction argument based on continuity: consider the sequence of solutions $\sigma_{t}=\mathcal{A}(\xi_{t}),t=0,\ldots,T$, produced by the algorithm $\mathcal{A}$. We have $\rho_{N}(\sigma_{t},\sigma_{t+1})\leq\kappa$ for every $t$ and $\rho_{N}(\sigma_{0},\sigma_{T})\geq\nu_{2}$ by the OGP and assumption (a) above. Suppose, for the purposes of contradiction, that every solution $\sigma_{t}$ produced by the algorithm is $\mu$-optimal for every instance $\xi_{t}$. Then by the OGP it is the case that, in particular, $\rho_{N}(\sigma_{0},\sigma_{t})$ is either at most $\nu_{1}$ or at least $\nu_{2}$ for every $t$. Since $\rho_{N}(\sigma_{0},\sigma_{T})\geq\nu_{2}$, there exists $t$, possibly $t=0$, such that $\rho_{N}(\sigma_{0},\sigma_{t})\leq\nu_{1}$ and $\rho_{N}(\sigma_{0},\sigma_{t+1})\geq\nu_{2}$. Then $\kappa\geq\rho_{N}(\sigma_{t},\sigma_{t+1})\geq|\rho_{N}(\sigma_{0},\sigma_{t})-\rho_{N}(\sigma_{0},\sigma_{t+1})|\geq\nu_{2}-\nu_{1}$, which is a contradiction with the assumption (b).

Simply put, the crux of the argument is that the algorithm cannot ”jump” over the gap $\nu_{2}-\nu_{1}$, since the incremental distances, bounded by $\kappa$ are two small to allow for it. This is the main method by which stable algorithms are ruled out in presence of the OGP and is illustrated on Figure 4. On this figure the smaller circle represent all of the $\mu$-optimal solutions which are at most distance $\nu_{1}$ from $\sigma_{0}$, across all instances $t\in[0,T]$. The complement to the larger circle represents all of the $\mu$-optimal solutions which are at least distance $\nu_{2}$ from $\sigma_{0}$, again across all instances $t\in[0,T]$. All $\mu$-optimal solutions across all instances should fall into one of these two regions, according to the e-OGP. As the sequence of solutions $\mathcal{A}(\xi_{t}),t\in[0,T]$ has to cross between these two regions, at some point $t$ the distance between $\mathcal{A}(\xi_{t})$ and $\mathcal{A}(\xi_{t+1})$ will have to exceed $\kappa$, contradicting the stability property.

Suppose the model does not exhibit the OGP, but does exhibit the m-OGP (ensemble version). We now describe how this can also be used as an obstruction to stable algorithms. As above, the argument is based on first verifying that for two independent instance $\xi$ and $\tilde{\xi}$ the regime $\rho_{N}(\sigma,\tau)\leq\nu_{1}$ is not possible with overwhelming probability. Consider $m+1$ independent instances $\xi_{0},\xi_{1},\ldots,\xi_{m}$ and consider an interpolated sequence $\xi_{1,t},\ldots,\xi_{m,t},t\in[0,T]$ with the property that $\xi_{i,T}=\xi_{i}$ and $\xi_{i,0}=\xi_{0}$ for all $i=1,2,\ldots,m$. In other words the sequence starts with $m$ identical copies of instance $\xi_{0}$ and slowly interpolates towards $m$ instance $\xi_{1},\ldots,\xi_{m}$. The details of such a construction are usually guided by concrete problems. Typically, such constructions are also symmetric in distribution, so that, in particular, all pairwise expected distances between the algorithmic outputs $\mathbb{E}\!\left[\rho_{N}\left(\mathcal{A}(\xi_{i,t}),\mathcal{A}(\xi_{j,t})\right)\right]$ are the same, say denoted by $\Delta_{t},t\in[0,T]$. Furthermore, in some cases a concentration around the expectation can be also established. As an implication this set of identical pairwise distances $\Delta_{t}$ spans values from $0$ to value larger than $\nu_{1}$ by the assumption (a). But the stability of the algorithm $\mathcal{A}$ also implies that at some point $t$ it will be the case that $\Delta_{t}\in(\nu_{1},\nu_{2})$, contradicting the m-OGP. This is illustrated on Figure 5. The high concentration property discussed above was established using standard methods in [GS17b] and [Wei20], but the approach in [GK21] was based on a different arguments employing methods from Ramsey extremal combinatorics field. Here the idea is to generate many more $M\gg m$ independent instances than the value of $m$ arising in m-OGP and showing using Ramsey theory results that there should exist a subset of $m$-instances such that all pairwise distances fall into interval $(\nu_{1},\nu_{2})$.

We now illustrate the OGP and its variants for the Number Partitioning problem and the maximum clique problem as examples. The discussion will be informal and references containing detailed derivations will be provided. The instance $\xi$ of the Number Partitioning problem is a sequence $X_{1},\ldots,X_{N}$ of independent standard normal random variables. For every binary vector $\sigma\in\{-1,1\}^{N}$, the inner product $Z(\sigma)=\langle\xi,\sigma\rangle$ is a mean zero normal random variable with variance $N$. The likelihood that $Z(\sigma)$ takes value in an interval around zero with length $\sqrt{N}2^{-N}$ is roughly $(2\pi)^{-{1\over 2}}$ times the length of the interval, namely times $2^{-N}$. Thus the expected number of such vectors $\sigma$ is of constant order $(2\pi)^{-{1\over 2}}$ since there are $2^{N}$ choices for $\sigma$. This gives an intuition for why there do exist vectors achieving value $\sqrt{N}2^{-N}$. Details can be found in [KK82]. Any choice of order magnitude smaller length interval leads to expectation converging to zero and thus non-achievable with overwhelming probability. Now, to discuss the OGP, fix constants $\alpha,\rho\in(0,1)$ and consider pairs of vectors $\sigma,\tau$ which achieve objective value $\sqrt{N}2^{-\alpha N}$ and have the scaled inner product $N^{-1}\langle\sigma,\tau\rangle=\rho$. The expected number of such pairs is roughly ${N\choose{1-\rho\over 2}N}$ times the area of the square with side length approximately $2^{-\alpha N}$, namely $2^{-2\alpha N}$. This is because the likelihood that a pair of correlated gaussians $Z(\sigma),Z(\tau)$ falls into a very small square around zero is dominated by the area of this square up to a constant. Approximating ${N\choose{1-\rho\over 2}N}$ as $\exp\left(NH({1-\rho\over 2})\right)$, where $H(x)=-x\log x-(1-x)\log(1-x)$ is the standard binary entropy, the expectation of the number of such pairs evaluates to roughly $\exp\left(N\left(H({1-\rho\over 2})-2\alpha\log 2\right)\right)$. As the largest value of $H(\cdot)$ is $\log 2$, we obtain an important discovery: for every $\alpha\in(1/2,1)$ there is a region of $\rho$ of the form $(\rho_{0},1)$ for which the expectation is exponentially small in $N$, and thus the value $\sqrt{N}2^{-\alpha N}$ is not achievable by pairs of partitions $\sigma$ and $\tau$ with scaled inner products in $(\rho_{0},1)$, with overwhelming probability. Specifically, for every pair of $\mu$-optimal solutions $\sigma,\tau$ with $\mu=(2^{-\alpha N}-2^{-N})$, it is the case that $N^{-1}\langle\sigma,\tau\rangle$ is either $1$ or at most $\rho_{0}$. With this value of $\mu$ and $\nu_{1}=0,\nu_{2}=N(1-\rho_{0})/2$, we conclude that the model exhibits the OGP.

Showing the ensemble version of OGP (namely e-OGP) can be done using very similar calculations, but what about values of $\alpha$ smaller than $1/2$? After all, the state of the art algorithms achieve only order $2^{-O(\log^{2}N)}$ which corresponds to $\alpha=0$ at scale. It turns out [GK21] that in fact the m-OGP holds for this model for all strictly positive $\alpha$ with a judicious choice of constant value $m$. Furthermore, the m-OGP extends all the way to $2^{-O(\sqrt{N\log N})}$ by taking $m$ growing with $N$, but not beyond that value, at least using the available proof techniques. Thus, at this stage we may conjecture that the problem is algorithmically hard for objective values smaller than order $2^{-O(\sqrt{N\log N})}$, but beyond this value we don’t have a plausible predictions either for hardness or tractability. In conclusion, at least at the exponential scale $\exp(-\Theta(N))$ we see that the OGP gives a theory of algorithmic hardness consistent with the state of the art algorithms.

The largest clique problem is another example where the OGP based predictions are consistent with the state of the art algorithms. Recall from the earlier section, that while the largest clique in $\mathbb{G}(N,1/2)$ is roughly $2\log_{2}N$, the largest size clique achievable by known algorithm is roughly half-optimal with size approximately $\log_{2}N$. Fixing $\alpha\in(1,2)$ consider pairs of cliques $\sigma,\tau$ with sizes roughly $\alpha\log_{2}N$. This range of $\alpha$ corresponds to clique sizes known to be present in the graph existentially with overwhelming probability, but not achievable algorithmically. As it turns out, see [GS17a],[GJW20a], the model exhibits the OGP for $\alpha\in(1+1/\sqrt{2},2)$ and overlap parameters $\nu_{1}(\alpha)<\nu_{2}(\alpha)$, both of which are at the scale $\log_{2}N$. Specifically, every two cliques of size $\alpha\log_{2}N$ have intersection size either at least $\tilde{\nu}_{1}(\alpha)$ or at most $\tilde{\nu}_{2}(\alpha)$, for some values $\tilde{\nu}_{1}(\alpha)>\tilde{\nu}_{2}(\alpha)$, both at scale $\log_{2}n$. This easily implies OGP with $\nu_{j}(\alpha)=2\alpha-\tilde{\nu}_{j}(\alpha),j=1,2$. The calculations in [GS17a] and [GJW20a] were carried out for a similar problem of finding a largest independent set (a set with no internal edges) in sparse random graphs $G(N,p_{N})$ with $p_{N}$ of the order $O(1/N)$, but the calculation details for the dense graph $\mathbb{G}(N,1/2)$ are almost identical. The end result is that $\tilde{\nu}_{j}(\alpha)=x_{j}(\alpha)\log_{2}N$, where $x_{1}(\alpha)$ and $x_{2}(\alpha)$ are the two roots of the quadratic equation $x^{2}/2-x+2\alpha-\alpha^{2}=0$, namely $1\pm\sqrt{1-2(2\alpha-\alpha^{2})}$, and roots exist if and only if $\alpha>1+1/\sqrt{2}$. For recent algorithmic results for the related problem on random regular graphs with small degree see [MK20].

To illustrate the ensemble version of the OGP, consider an ensemble $G_{1},\ldots,G_{N\choose 2}$ of random $\mathbb{G}(N,1/2)$ graphs, constructed as follows. Generate $G_{0}$ according to the probability law of $\mathbb{G}(N,1/2)$. Introduce a random uniform order $\pi$ of ${N\choose 2}$ pairs of nodes $1,\ldots,N$ and generate graph $G_{t}$ from $G_{t-1}$ by resampling the pair $(i_{t},j_{t})$ – the $t$-th pair in the order $\pi$, and leaving other edges of $G_{t-1}$ intact. This way each graph $G_{t}$ individually has the law of $\mathbb{G}(N,1/2)$, but neighboring graphs $G_{t-1}$ and $G_{t}$ differ by at most one edge. The beginning and the end graphs $G_{0}$ and $G_{N\choose 2}$ are clearly independent. Now fix $\alpha\in(1+1/\sqrt{2},2)$ and $x\in(0,\alpha)$ A simple calculation shows that the expected number of $\alpha\log_{2}N$ size cliques $\sigma$ in $G_{t_{1}}$ and same size cliques $\tau$ in $G_{t_{2}}$, such that the size of the intersection of $\sigma$ and $\tau$ is $x\log_{2}N$ is approximately given by $\exp\left((1+o(1))\log_{2}^{2}N\left((1-\rho)x^{2}/2-x+2\alpha-\alpha^{2}\right)\right)$, where $\rho=(t_{2}-t_{1})/{N\choose 2}$ is the (rescaled) number of edges of $G_{t_{2}}$ which were resampled from $G_{t_{1}}$. Easy calculation shows that the function $(1-\rho)x^{2}/2-x+2\alpha-\alpha^{2}$ has two roots $x_{1}>x_{2}$ in the interval $(0,\alpha)$ given by $(1-\rho)^{-1}\left(1\pm\sqrt{1-2(1-\rho)(2\alpha-\alpha^{2})}\right)$, when the larger root is smaller than $\alpha$, namely when $\rho<{2\over\alpha}-1$. On the other hand, when $\rho>{2\over\alpha}-1$, including the extreme case $\rho=1$ corresponding to $t_{1}=0,t_{2}={N\choose 2}$, there is only one root in $(0,\alpha)$. The model thus not only does exhibit the e-OGP for the ensemble $G_{t},0\leq t\leq{N\choose 2}$. Additionally the value $\rho^{*}={2\over\alpha}-1$ represents a new type of phase transition, not known earlier to the best of the author’s knowledge. When $\rho<\rho^{*}$ every two cliques with size $\alpha\log_{2}N$ have intersection size either at least $x_{1}\log_{2}N$ or at most $x_{2}\log_{2}N$. On the other hand, when $\rho>\rho^{*}$, the second regime disappears, and any two such cliques have intersection size only at most $x_{2}\log_{2}N$. The situation is illustrated on the Figure 6 for the special case $\alpha=1.72$ and $\rho^{*}=2/\alpha-1=0.163..~{}$. This phase transition is related to the so-called chaos property of spin glasses which we discuss below, but has qualitatively different behavior. In particular, the analogous parameter $\rho^{*}$ in the context of spin glass models has value $\rho^{*}=0$. More on this below.

The value $\alpha=1+1/\sqrt{2}$ is not tight with respect to the apparent algorithmic hardness which occurs at $\alpha=1$ as discussed earlier. This is where the multi-OGP comes to rescue. A variant of an (assymetric) m-OGP has been established recently in [Wei20], building on an earlier symmetric version of m-OGP, discovered in [RV17], ruling out the class of stable algorithms as potential contenders for solving the Independent Set problem above $\alpha=1$. More specifically, in both works (for the case of local algorithms in [RV17] and for the case of low-degree polynomials based algorithms in [Wei20]) it is shown that for every fixed $\epsilon>0$ there exists a constant $m=m(\epsilon)$ such that the model exhibits m-OGP with this value of $m$ for independent sets corresponding to $\alpha=1+\epsilon$. While, it has not be formally verified, it appears based on the first moment argument that value $m$ growing with $\epsilon$ is needed, in the sense that no fixed value of $m$ achieves the OGP all the way down to $\alpha=1$, but constant values of $m$ which are $\epsilon$-dependent do. It is interesting to contrast this with the Number Partitioning problem where it was crucial to take $m$ growing with $N$ in order the bridge the gap between the algorithmic and existential thresholds.

How does one establish the link of the form OGP implies Class $\mathcal{C}$ of algorithms fails, and what classes $\mathcal{C}$ of algorithms can be proven to fail in presence of the OGP? As discussed earlier, the failure is established by showing stability (insensitivity) of the algorithms in class C to the changes of the input. This stability forces the algorithm to produce pairs of outputs with overlap falling into a region ”forbidden” by the OGP. The largest class of algorithms to the day which is shown to be stable is the class of algorithms informally dubbed as ”low-degree polynomials”. Roughly speaking this is a class of algorithms where the solution $\sigma\in\Sigma_{N}$ is obtained by constructing an $N$-sequence of multi-variate polynomials $p_{j}(\xi),j=1,\ldots,N$ with variables evaluated at entries of the instance $\xi\in\Xi_{N}$. The largest degree $d$ of the polynomial is supposed to be low, though depending on the problem it can take even significantly high value. Algorithms based on low-degree polynomials gained a lot of prominence recently due to connection with the so-called Sum-of-Squares method and represent arguably the strongest known class of polynomial time algorithms [HS17],[HKP⁺17],[Hop18]. What can be said about this method in the context of the problems exhibiting the OGP? It was shown in [GJW20a],[Wei20] and [BH21] that degree-$d$ polynomial based algorithms are stable for the problems of finding a ground state of a p-spin model, finding a large independent set of a sparse Erdös-Rényi graph $\mathbb{G}(N,c/N)$, and for the problem of finding a satisfying assignment of a random K-SAT problem. This is true even when $d$ is as large as $O(N/\log N)$. Thus algorithms based on polynomials even with degree $O(N/\log N)$ fail to find near optimum solutions for these problems due to the presence of the OGP. Many algorithms can be modeled as special cases of low degree polynomials, and therefore ruled out by OGP, including the so-called Approximate Message Passing algorithms [GJ19],[GJW20a], local algorithms considered in [GS17a],[RV17] and even quantum versions of local algorithms known as Quantum Approximate Optimization Algorithm (QAOA) [FGG20a].

In addition to the maximum clique problem, there is another large class of optimization problem for which the OGP approach provides a tight classification of solvable vs not yet solvable in polynomial time problems. It is the problem of finding ground states of p-spin models – the very class of optimization problems which led to studying the overlap distribution and overlap gap type properties to begin with. The problem is described as follows: suppose one is given a $p$-order tensor $J$ of side length $N$. Namely, $J$ is described as a collection of real values $J_{i_{1},\ldots,i_{p}}$ where $i_{1},\ldots,i_{p}$ range between $1$ and $N$. Given the solution space $\Sigma_{N}$, the goal is finding a solution $\sigma\in\Sigma_{N}$ (called ground state) which minimizes the inner product $\langle J,\sigma\rangle=\sum_{i_{1},\ldots,i_{p}}J_{i_{1},\ldots,i_{p}}\sigma_{i_{1}}\cdots\sigma_{i_{p}}$. The randomness in the model is derived from the randomness of the entries of $J$. A common assumption, capturing most of the structural and algorithmic complexity of the model, is that the entries $J_{i_{1},\ldots,i_{p}}$ are independent standard normal entries. Two important special cases of the solution space $\Sigma_{N}$ include the case when $\Sigma_{N}$ is a binary cube $\{-1,1\}^{N}$, and when it is a sphere of a fixed radius (say $1$) in the $N$-dimensional real space, the latter case being referred to as spherical spin glass model. The special case $p=2$ and $\Sigma_{N}=\{-1,1\}^{N}$ is the celebrated Sherrington-Kirkpatrick model [SK75] – the centerpiece of the spin glass theory. The problem of computing the value of this optimization problem above was at the core of the spin glass theory in the past four decades, which led to the replica symmetry breaking technique first introduced in the physics literature by Parisi [Par80], and then followed by a series of mathematically rigorous developments, including those by Talagrad [Tal10] and Panchenko [Pan13].

The algorithmic progress on this problem, however, is quite recent. While the power of the Monte Carlo based simulation results have been tested numerous times, the first rigorous progress has appeared only in the past few years. In the important development by Subag [Sub18] and Montanari [Mon19] a polynomial time algorithms were constructed for finding near ground states in these models. Remarkably, this was done precisely for regimes where the model does not exhibit the OGP as per a detailed analysis of the so-called Parisi measure of the associated Gibbs distribution. A follow-up development in [AMS20] extended this to models which do exhibit OGP, but in this case near ground states are not reached. Instead, one constructs the best solution within the part of the solution space not exhibiting the OGP. To put it differently, the algorithms produce a $\mu$-optimal solution for the smallest value of $\mu$ for which the OGP does not hold. Conversely, as shown in a series of recent developments [GJ19],[GJW20b],[Sel20], the optimization problem problem associated with finding near ground states cannot be solved within some classes of algorithms, the largest of which is the class of algorithms based on low-degree polynomials. The failure of this class of algorithms was established exactly along the lines described above: verifying stability of the algorithms of interest, and verifying the presence of OGP which presents an obstruction to stability. Interestingly, a class of algorithms, which is not described by low-degree polynomials but which is still ruled out by the OGP is the Langevin dynamics at a linear in $N$ scale, as shown in [GJW20b]. The Langevin dynamics is continuous version of the Markov Chain Monte Carlo type algorithm. Its stability stems from the Gronwald’s type bound stating that two time dependent Langevin trajectories $\sigma(\xi,s),\sigma(\tilde{\xi},s),s\in\mathbb{R}_{+}$ associated with the Langevin dynamics run on two instances $\xi$ and $\tilde{\xi}$, diverge at the rate order $\|\xi-\tilde{\xi}\|\exp(\kappa s)$ for some constant $\kappa>0$. Thus when $s$ is of order $N$ and $\xi$ and $\tilde{\xi}$ are at distance which is exponentially small in $N$, one can control this divergence. One then uses e-OGP for an interpolated sequence $\xi_{t},t\in[0,T]$ with discrete values of $t$ with $\exp(-\Theta(N))$ increments to argue stability. The approach fails at time scales larger than $N$, since the required concentration bounds underlying OGP hold only modulo exponentially in $N$ small probability, and as a result the union bound over more than $\exp(\Theta(N))$ terms is no longer effective. It is a very plausible conjecture, though, that the Langevin dynamics indeed still fails unless it is ran for exponentially long $s=\exp(\Theta(N))$ time. We leave this conjecture as an interesting open problem.

The analogue of the phase transition $\rho^{*}={2\over\alpha}-1$ discussed in the context of the largest clique problem takes place in the p-spin model as well in the more extreme form called the chaos property: any non-trivial perturbation of the instance $J$ whereby any fixed positive fraction of entries of $J$ are flipped, results in the instance $\tilde{J}$ for which every near ground state is nearly orthogonal to every near ground state of $J$. To put it differently $\rho^{*}$ is effectively zero for this model. This has been established in a series of works [Cha09],[CHL18],[Eld20]. Notably, the chaos property itself is not a barrier to polynomial time algorithms since the Sherrington-Kirkpatrick model is known to exhibit the chaos property, yet, it is amenable to poly-time algorithms as in [Sub18] and [Mon19]. The chaos property however is used as a tool to establish the ensemble version of the OGP (e-OGP) as was done in [CGPR19] and [GJ19].

We now return to the subject of weak and strong clustering property, and discuss it now from the perspective of the OGP and the implied algorithmic hardness. The relationship is interesting, non-trivial and perhaps best exemplified by yet another model which exhibits statistical to computation gap: the binary perceptron model. The input to the model is $M\times N$ matrix of i.i.d. standard normal entries $X_{ij},1\leq i\leq M,1\leq j\leq N$. A fixed parameter $\kappa>0$ is fixed. The goal is to find a binary vector $\sigma\in\{\pm 1\}^{N}$ such that for each $i,\sum_{1\leq j\leq N}X_{ij}\sigma_{j}\in[-\kappa,\kappa]$. In vector notation we need to find $\sigma$ such that $\|X\sigma\|_{\infty}\leq\kappa$, where $\|x\|_{\infty}=\max_{j}|x_{j}|$ for any vector $x\in\mathbb{R}^{N}$. This is also known as binary symmetric perceptron model, to contrast it with assymetric model, where the requirement is that $X\sigma\geq\kappa$, for some fixed parameter $\kappa$ (positive or negative), with inequalities interpreted coordinate-wise. In the assymetric case the a typical choice is $\kappa=0$. Replica symmetry breaking based heurstic methods developed in this context by Krauth and Mezard [KM89] predict a sharp threshold at $\alpha_{\rm SAT}=0.83$ for the case $\kappa=0$, so that when $\alpha<\alpha_{\rm SAT}$ and $M\leq\alpha N$ such a vector $\sigma$ exists, and when $\alpha>\alpha_{\rm SAT}$ such a vector $\sigma$ does not exist, both with high probability as $N\to\infty$. This was confirmed rigorously as an upper bound in [DS19]. For the symmetric case a similar sharp threshold $\alpha_{\rm SAT}(\kappa)$ is known rigorously as a $\kappa$ dependent constant $\alpha(\kappa)$, as established in [PX21] and [ALS21].

The known algorithmic results however are significantly weaker and scarce. The algorithm by Kim and Rouche [KR98] finds $\sigma$ for the assymetric $\kappa=0$ case when $\alpha<0.005$. While the algorithm has not been adopted to the symmetric case, it is quite likely that a version of it should work here as well for some positive sufficiently small $\kappa$-dependent constant $\alpha$. Heuristically, the message passing algorithm was found to be effective at small positive densities, as reported in [BZ06]. Curiously, though, it is known that the symmetric model exhibits the weak clustering property at all positive densities $\alpha>0$, as was rigorously verified recently in [PX21] and [ALS21]. Furthermore, quite remarkably, each cluster consist of singletons! Namely the cardinality of each cluster is one, akin to ”needles in the haystack” metaphor. A similar picture was established in the context of the Number Partitioning problem [GK21]. This interesting entropic (due to the subextensive cardinality of clusters) phenomena is fairly novel and its algorithmic implications have been also discussed in [BRTS21] in the context of another constraint satisfaction problem – the random K-XOR model. Thus at this stage, assuming the extendability of the Kim-Roche algorithm and/or validity of the message passing algorithm, we have an example of a model exhibiting weak clustering property, but amenable to polynomial time algorithms. This stands in in contrast to the random K-SAT model and in fact all other models known to the author. As an explanation of this phenomena, the aforementioned references point out that to the ”non-uniformity” in algorithmic choices of the solutions allowing it somehow to bypass the overwhelming clustering picture exhibited by the weak clustering property.

What about the strong clustering property and the OGP? First let us elucidate the relationship between the two properties. The pair-wise ($m=2$) OGP which holds for a single instance clearly implies the strong clustering property: if every pair of $\mu$-optimal solutions is at distance at most $\nu_{1}$ or at least $\nu_{2}>\nu_{1}$, and the second case is non-vacuous, clearly the set of solutions is strongly clustered. It furthermore, indicates that the diameter of each cluster is strictly smaller (at scale) than the distances between the clusters, see Figures 2,3. In fact this is precisely how the strong clustering property was discovered to begin with in [ART06] and [MMZ05]. However, the converse does not need to be the case, as one could not rule out an example of a strong clustering property where the cluster diameters are larger than the distances between them, and, as a result, the overlaps of pairs of solutions span a continuous intervals. At this stage we are not aware of any such examples.

Back to the symmetric perceptron model, it is known (rigorously, based on the moment computation), that it does exhibit the OGP, at a value $\alpha$ strictly smaller than the critical threshold $\alpha_{\rm SAT}(\kappa)$ [BDVLZ20]. As a result the strong clustering property holds as well above this $\alpha$. Naturally, we conjecture that the problem of finding a solution $\sigma$ is hard in this regime, and it is very likely that classes of algorithms, such as low-degree polynomial based algorithm and their implications can be ruled out by the OGP method along the lines discussed above.

Finally, as the strong clustering property appears to be the most closely related to the OGP, it raises a question as to whether it can be used as a ”signature” of hardness in lieu of OGP and/or whether it can be used as a method to rule out classes of algorithm, similarly to the OGP based method. There are two challenges associated with this proposal. First we are not aware of any effective method of establishing the strong clustering property other than the one based on the OGP. Second, and more importantly, it is not entirely clear how to link meaningfully the strong clustering property with m-OGP, which appears necessary for many problems in order to bridge the computational gaps to the known algorithmically achievable values. Likewise, it is not entirely clear what is the appropriate definition of either weak or strong clustering property in the ensemble version, when one considers a sequence of correlated instances, which is again another important ingredient in the implementation of the refutation type arguments. Perhaps some form of dynamically evolving clustering picture is of relevance here. Some recent progress on the former question regarding the geometry of the m-OGP was obtained recently in [BAJ21] in the context of the spherical spin glass model. We leave both questions as interesting open venues for future investigation.