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 [1]}
and Montanari [2]} 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 [3]} 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 [4]},[5]},[6]},
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 [5]}. 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 \(\Vert \xi -\tilde{\xi }\Vert \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.
