Portugaliae Mathematica


Full-Text PDF (288 KB) | Metadata | Table of Contents | PM summary
Volume 75, Issue 2, 2018, pp. 159–186
DOI: 10.4171/PM/2014

Published online: 2018-12-12

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

Afonso S. Bandeira[1], Amelia Perry and Alexander S. Wein[2]

(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