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

note = "Funding Information: The authors would like to thank the engaging audience at the Courant Institute when this material was presented, and their many insightful comments. The authors would also like to thank Soledad Villar and Lenka Zdeborov{\'a} for feedback on earlier versions of this manuscript. We also thank the anonymous reviewer for many helpful comments. A. S. Bandeira was partially supported by NSF DMS-1712730 and NSF DMS-1719545. A. Perry was supported in part by NSF CAREER Award CCF-1453261 and a grant from the MIT NEC Corporation. Part of this work was done while A. S. Wein was with the department of mathematics at the Massachusetts Institute of Technology. A. S. Wein received Government support under and awarded by DoD, Air Force Office of Scientific Research, National Defense Science and Engineering Graduate (NDSEG) Fellowship, 32 CFR 168a. A. S. Wein is also supported by NSF grant DMS-1712730 and by the Simons Collaboration on Algorithms and Geometry Funding Information: A. S. Bandeira was partially supported by NSF DMS-1712730 and NSF DMS-1719545. A. Perry was supported in part by NSF CAREER Award CCF-1453261 and a grant from the MIT NEC Corporation. Part of this work was done while A. S. Wein was with the department of mathematics at the Massachusetts Institute of Technology. A. S. Wein received Government support under and awarded by DoD, Air Force O‰ce of Scientific Research, National Defense Science and Engineering Graduate (NDSEG) Fellowship, 32 CFR 168a. A. S. Wein is also supported by NSF grant DMS-1712730 and by the Simons Collaboration on Algorithms and Geometry. Publisher Copyright: {\textcopyright} 2018 European Mathematical Society.",

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

}