## Free software from Google aims to protect political candidates from cyberattacks

An algorithmically hard phase was described in a range of inference problems:
even if the signal can be reconstructed with a small error from an information
theoretic point of view, known algorithms fail unless the noise-to-signal ratio
is sufficiently small. This hard phase is typically understood as a metastable
branch of the dynamical evolution of message passing algorithms. In this work
we study the metastable branch for a prototypical inference problem, the
low-rank matrix factorization, that presents a hard phase. We show that for
noise-to-signal ratios that are below the information theoretic threshold, the
posterior measure is composed of an exponential number of metastable glassy
states and we compute their entropy, called the complexity. We show that this
glassiness extends even slightly below the algorithmic threshold below which
the well-known approximate message passing (AMP) algorithm is able to closely
reconstruct the signal. Counter-intuitively, we find that the perform查看全文