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

arXiv: https://arxiv.org/abs/2506.06259 · HTML: https://mlsanity.com/paper/2506.06259/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 52 references that are in the map.
- First posted on arXiv 6 Jun 2025.

## Builds on (most cited first, 21 of 21)

- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014)
- [Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent](https://mlsanity.com/paper/2009.06107/) (2020)
- [Computational-Statistical Gaps in Gaussian Single-Index Models](https://mlsanity.com/paper/2403.05529/) (2024)
- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020)
- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Efficient Statistics, in High Dimensions, from Truncated Samples](https://mlsanity.com/paper/1809.03986/) (2018)
- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [Computationally and Statistically Efficient Truncated Regression](https://mlsanity.com/paper/2010.12000/) (2020)
- [Universality of Computational Lower Bounds for Submatrix Detection](https://mlsanity.com/paper/1902.06916/) (2019)
- [Statistical and Computational Phase Transitions in Group Testing](https://mlsanity.com/paper/2206.07640/) (2022)
- [Free Energy Wells and Overlap Gap Property in Sparse PCA](https://mlsanity.com/paper/2006.10689/) (2020)
- [Testing Convex Truncation](https://mlsanity.com/paper/2305.03146/) (2023)
- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval](https://mlsanity.com/paper/1808.06996/) (2018)
- [Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals](https://mlsanity.com/paper/2202.05096/) (2022)
- [On the Low-Temperature MCMC threshold: the cases of sparse tensor PCA, sparse regression, and a geometric rule](https://mlsanity.com/paper/2408.00746/) (2024)

## Built on by (most cited first, 2 of 2)

- [High-Dimensional Statistics: Reflections on Progress and Open Problems](https://mlsanity.com/paper/2605.05076/) (2026)
- [A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Models](https://mlsanity.com/paper/2603.17896/) (2026)

## Abstract (arXiv)

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 annealed version of the celebrated Franz-Parisi potential from statistical physics, was shown to be equivalent to low-degree polynomial (LDP) lower bounds for Gaussian additive models, thereby connecting two distinct approaches to understanding the computational hardness in statistical inference. In this paper, we propose a refined FP criterion that aims to better capture the geometric ``overlap" structure of statistical models. Our main result establishes that this optimized FP criterion is equivalent to Statistical Query (SQ) lower bounds -- another foundational framework in computational complexity of statistical inference. Crucially, this equivalence holds under a mild, verifiable assumption satisfied by a broad class of statistical models, including Gaussian additive models, planted sparse models, as well as non-Gaussian component analysis (NGCA), single-index (SI) models, and convex truncation detection settings. For instance, in the case of convex truncation tasks, the assumption is equivalent with the Gaussian correlation inequality (Royen, 2014) from convex geometry. In addition to the above, our equivalence not only unifies and simplifies the derivation of several known SQ lower bounds -- such as for the NGCA model (Diakonikolas et al., 2017) and the SI model (Damian et al., 2024) -- but also yields new SQ lower bounds of independent interest, including for the computational gaps in mixed sparse linear regression (Arpino et al., 2023) and convex truncation (De et al., 2023).