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

Afonso S. Bandeira, Amelia Perry, Alexander S. Wein

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)159-186
Number of pages28
JournalPortugaliae Mathematica
Volume75
Issue number2
DOIs
StatePublished - 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