### 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