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

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

doi:10.4171/PM/2014

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

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

Mathematics

Research output: Contribution to journal › Article › peer-review

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	https://doi.org/10.4171/PM/2014
State	Published - 2018

Keywords

Approximate message passing
Cavity method
Computational-to-statistical gaps
Phase transitions
Replica method

ASJC Scopus subject areas

Mathematics(all)

Access to Document

10.4171/PM/2014

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

@article{9f3dcb10d73943c4af0fcb989506c325,

title = "Notes on computational-to-statistical gaps: Predictions using statistical physics",

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.",

keywords = "Approximate message passing, Cavity method, Computational-to-statistical gaps, Phase transitions, Replica method",

author = "Bandeira, {Afonso S.} and Amelia Perry and Wein, {Alexander S.}",

year = "2018",

doi = "10.4171/PM/2014",

language = "English (US)",

volume = "75",

pages = "159--186",

journal = "Portugaliae Mathematica",

issn = "0032-5155",

publisher = "European Mathematical Society Publishing House",

number = "2",

}

TY - JOUR

T1 - Notes on computational-to-statistical gaps

T2 - Predictions using statistical physics

AU - Bandeira, Afonso S.

AU - Perry, Amelia

AU - Wein, Alexander S.

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Approximate message passing

KW - Cavity method

KW - Computational-to-statistical gaps

KW - Phase transitions

KW - Replica method

UR - http://www.scopus.com/inward/record.url?scp=85058797852&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85058797852&partnerID=8YFLogxK

U2 - 10.4171/PM/2014

DO - 10.4171/PM/2014

M3 - Article

AN - SCOPUS:85058797852

VL - 75

SP - 159

EP - 186

JO - Portugaliae Mathematica

JF - Portugaliae Mathematica

SN - 0032-5155

IS - 2

ER -