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\le i\le M, 1\le j\le N\) . A fixed parameter \(\kappa >0\)  is fixed. The goal is to find
a binary vector \(\sigma \in \lbrace \pm 1\rbrace ^N\)  such that for each \(i, \sum _{1\le j\le N} X_{ij}\sigma _j\in [-\kappa ,\kappa ]\) .
In vector notation we need to find \(\sigma \)  such that \(\Vert X\sigma \Vert _{\infty }\le \kappa \) , where
\(\Vert x\Vert _\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 \ge \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 [1]}
predict a sharp threshold at \(\alpha _{\rm SAT}=0.83\)  for the case \(\kappa =0\) , so that when \(\alpha <\alpha _{\rm SAT}\) 
and \(M\le \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\rightarrow \infty \) . This was
confirmed rigorously as an upper bound in [2]}. 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 [3]} and [4]}.
