Disordered systems insights on computational hardness
Disordered systems insights on computational hardness
Abstract 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 …