An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds

Siyu Chen, Theodor Misiakiewicz, Ilias Zadik +1

Bandeira et al. (2022) introduced the Franz-Parisi (FP) criterion for characterizing the computational hard phases in statistical detection problems. The FP criterion, based on an…