Disordered Systems Insights on Computational Hardness

Understand

In this review article, we discuss connections between the physics of disordered systems, phase transitions in inference problems, and computational hardness.

• We introduce two models representing the behavior of glassy systems, the spiked tensor model and the generalized linear model.
• We discuss the random (non-planted) versions of these problems as prototypical optimization problems, as well as the planted versions (with a hidden solution) as prototypical problems in statistical inference and learning.
• Based on ideas from physics, many of these problems have transitions where they are believed to jump from easy (solvable in polynomial time) to hard (requiring exponential time).