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
[1]},[2]},[3]}.
What can be said about this method in the context of the problems exhibiting the OGP?
It was shown in [4]},[5]} and [6]}
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 [7]},[4]},
local algorithms considered in [9]},[10]} and even quantum versions of local algorithms known
as Quantum Approximate Optimization Algorithm (QAOA) [11]}.
