We now introduce a new approach for predicting and proving
algorithmic complexity for solving random constraint satisfaction problems and optimization problems
on random structures, such as the ones introduced in earlier sections. The approach bears a lot of similarity with the predictions based
on the clustering property described in the earlier section, but has important and nuanced differences,
which allows us to rule out
large classes of algorithms, something that did not seem possible before.
An important special case of such algorithms are stable algorithms, namely algorithms exhibiting low sensitivity to the data input.
A special yet very broad and powerful class of such algorithms are algorithms based on low-degree polynomials.
A fairly recent stream of research [1]},[2]},[3]}
puts forward an evidence that in fact algorithms based on low-degree polynomials might be the most
powerful class of polynomial time algorithms for optimization problem on random structures,
such as problems discussed in this paper.
