Full-Text PDF (288 KB) | Metadata | Table of Contents | PM summary
Published online: 2018-12-12
Notes on computational-to-statistical gaps: predictions using statistical physicsAfonso S. Bandeira, Amelia Perry and Alexander S. Wein (1) Courant Institute, New York University, USA
(2) Courant Institute, New York University, USA
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.
Keywords: Computational-to-statistical gaps, phase transitions, cavity method, replica method, approximate message passing
Bandeira Afonso, Perry Amelia, Wein Alexander: Notes on computational-to-statistical gaps: predictions using statistical physics. Port. Math. 75 (2018), 159-186. doi: 10.4171/PM/2014