In this review article, we discuss the relationship between the physics of chaotic systems, phase transitions in inference problems, and computational difficulties. We introduce two models that describe the behavior of glassy systems: the spike tensor model and the generalized linear model. We describe the random (non-seeded) versions of these problems as prototype optimization problems, and the seeded versions (including hidden solutions) as prototype problems in statistical inference and learning. Based on ideas from physics, many of these problems have transitions that can be thought of as jumping from easy (solvable in polynomial time) to hard (requires exponential time). We discuss several new ideas in theoretical computer science and statistics that provide rigorous proof of the hard by proving that a large class of algorithms fail in the inferred hard regime. This includes the overlap gap property, which is a specific mathematization of clustering or dynamic symmetry breaking. It can be used to show that many algorithms that are robust to local or input changes fail. We also discuss sum-of-squares hierarchies that bound proofs and algorithms that use low-order polynomials, such as the standard spectrum method and semi-definite relaxation. This includes the Sherrington-Kirkpatrick model. Throughout the manuscript, we present connections to the physics of chaotic systems and the associated replica symmetry-breaking properties.
