Notes on computational-to-statistical gaps: predictions using statistical physics

03/29/2018
by   Afonso S. Bandeira, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset