Abstract
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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 159-186 |
| Number of pages | 28 |
| Journal | Portugaliae Mathematica |
| Volume | 75 |
| Issue number | 2 |
| DOIs | |
| State | Published - 2018 |
Keywords
- Approximate message passing
- Cavity method
- Computational-to-statistical gaps
- Phase transitions
- Replica method
ASJC Scopus subject areas
- Mathematics(all)
Fingerprint Dive into the research topics of 'Notes on computational-to-statistical gaps: Predictions using statistical physics'. Together they form a unique fingerprint.
Cite this
Bandeira, A. S., Perry, A., & Wein, A. S. (2018). Notes on computational-to-statistical gaps: Predictions using statistical physics. Portugaliae Mathematica, 75(2), 159-186. https://doi.org/10.4171/PM/2014