Glassy Nature of the Hard Phase in Inference Problems
Fabrizio Antenucci, Silvio Franz, Pierfrancesco Urbani, Lenka Zdeborová · Physical Review X · 2019
A new analysis of ``hard phase'' inference problems reveals glasslike behavior. Accounting for this insight does not improve algorithm performance, bolstering the notion that such problems cannot be solved in a practical amount of time.