Notes on computational-to-statistical gaps: predictions using statistical physics
This addresses the challenge of understanding unsolvable regimes in statistical problems for researchers in computational theory and statistical physics, but it is incremental as it builds on existing methods.
The authors tackled the problem of predicting computational-to-statistical gaps in statistical problems, where efficient algorithms are lacking despite information-theoretic feasibility, using non-rigorous tools from statistical physics.
In these notes we describe heuristics to predict computational-to-statistical gaps in certain statistical problems. These are regimes in which the underlying statistical problem is information-theoretically possible although no efficient algorithm exists, rendering the problem essentially unsolvable for large instances. The methods we describe here are based on mature, albeit non-rigorous, tools from statistical physics. These notes are based on a lecture series given by the authors at the Courant Institute of Mathematical Sciences in New York City, on May 16th, 2017.