Pith. sign in

REVIEW 2 major objections 6 minor 1 cited by

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

T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that an optimized, symmetry-aware Franz-Parisi criterion is equivalent to Statistical Query lower bounds for detection tasks satisfying a group-averaged moment condition, unifying physics-style and query-based hardness.

desk verdict A real GFP-SQ theorem with a real regime gap: the abstract and Theorem 1.4 overstate what Theorem 3.7 proves, but the example-specific SQ bounds and the separation example are solid enough to referee. read the letter →

arxiv 2506.06259 v1 pith:5YYJJBX6 submitted 2025-06-06 math.ST cond-mat.stat-mechcs.CCstat.MLstat.TH

Siyu Chen , Theodor Misiakiewicz , Ilias Zadik , Peiyuan Zhang This is my paper
classification math.STcond-mat.stat-mechcs.CCstat.MLstat.TH MSC 62C2062H1568Q17
keywords Franz-Parisicriterionstatisticalqueryhardnesscomputational-statisticaltradeoffshigh-dimensionaldetectionGaussianadditivemodelsplantedsparsenon-Gaussiancomponentanalysisconvextruncation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to prove that a generalized, symmetry-aware version of the Franz-Parisi criterion—a statistical-physics-style test for computational hardness based on overlap geometry—is exactly equivalent to Statistical Query (SQ) lower bounds for a broad class of detection tasks. Under a mild moment condition (Assumption 3.1), the paper shows a task is hard for SQ algorithms if and only if it is hard for the generalized Franz-Parisi criterion, up to polynomial losses in the parameters. The equivalence matters because it connects two independent hardness frameworks: the physics-inspired geometric criterion and the complexity-theoretic SQ paradigm. It rederives known SQ lower bounds for non-Gaussian component analysis and single-index models, and yields new SQ lower bounds for mixed sparse linear regression and convex truncation detection. If the equivalence is right, the optimized overlap function ρ_G serves as a unified certificate of computational hardness across these models.

What carries the argument

The engine of the paper is the Generalized Franz-Parisi (GFP) criterion, defined as the infimum over G²-invariant events A of E[⟨$L_u^{{⊗m}}$, $L_v^{{⊗m}}$⟩_Q 1(A)] over events of prior mass at least 1 − $q^{{-2}}$; q is a runtime proxy. The second ingredient is Assumption 3.1, which demands that for all u,v and all k, E_{g,g'}[ (⟨L_{g(u)}, L_{g'(v)}⟩_Q − 1)^k ] ≥ 0 for a finite prior-preserving group G. The link between them is the overlap function ρ_G(u,v) = max_{g,g'∈G} |⟨L_{g(u)}, L_{g'(v)}⟩_Q − 1|: under Assumption 3.1, the optimal event in the GFP criterion is approximately {ρ_G(u,v) ≤ r(q)}, which reduces GFP-hardness to a statement about even moments of ⟨L_u, L_v⟩_Q − 1. Those moments are exactly what the Statistical Query hardness condition controls, and the proof passes between the two by a binomial expansion of ⟨$L_u^{{⊗m}}$, $L_v^{{⊗m}}$⟩_Q = (1 + (⟨L_u, L_v⟩_Q − 1))^m and by the equivalence between SQ hardness and unconditional moment bounds.

What would settle it

Take any detection task and compute, for k = 2, the quantity E_{g,g'}[ (⟨L_{g(u)}, L_{g'(v)}⟩_Q − 1)^2 ] for the candidate group G: if it is negative for some u,v, Assumption 3.1 fails and the theorem's conditions are not met. The paper's own Dirac-atom example (Section 6.2.1) is such a case with ⟨L_u, L_v⟩ = 2^n 1(u=v), and it is GFP-hard but not SQ-hard, so the assumption is genuinely load-bearing rather than decorative.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.7: for any null-versus-planted detection task satisfying Assumption 3.1, if the task is information-theoretically undetectable with m_IT samples (χ²($P^{{m_IT}}$|$Q^{{m_IT}}$) = O(1)) and q ≥ $m^{{m_IT}}$, then (q,m)-SQ hardness and (q,m,O(1))-GFP_G hardness are equivalent, with parameter losses. Here GFP_G hardness is the optimized Franz-Parisi criterion: one minimizes the annealed likelihood-ratio inner product over symmetry-invariant 'overlap' events that cover all but $q^{{-2}}$ of the signal pairs, and Assumption 3.1 requires that all moments of the group-averaged likelihood-ratio inner product minus one are nonnegative. The proof identifies the near-optimal overlap event as a sublevel set of ρ_G(u,v) = max_{g,g'} |⟨L_{g(u)}, L_{g'(v)}⟩_Q − 1|, which turns GFP-hardness into a bound on moments of ⟨L_u, L_v⟩_Q − 1, and the same moment bounds are exactly what SQ hardness measures. The paper further shows this equivalence holds for Gaussian additive models, planted sparse models, non-Gaussian component analysis, single-index models, and convex truncation, and that Assumption 3.1 is necessary: without it there are models that are GFP-hard but not SQ-hard.

Load-bearing premise

The whole equivalence rests on Assumption 3.1: after averaging over a finite symmetry group, every power of the likelihood-ratio inner product minus one must have nonnegative expectation for every pair of signals; for the trivial group this means ⟨L_u, L_v⟩_Q ≥ 1 for all u,v.

Editorial extensions

If this is right

  • For Gaussian additive models with symmetric priors, GFP-hardness is equivalent to the original Franz-Parisi criterion, so FP-hardness now implies and is implied by SQ-hardness, not just by low-degree hardness.
  • For planted sparse models, including the mixed sparse linear regression problem, the equivalence yields a new SQ lower bound in the regime m ≤ ((SNR+1)^2/SNR^2) k^2 up to polylog factors, complementing the known low-degree bound.
  • For NGCA and single-index models with any symmetric prior, the known SQ lower bounds follow from a short GFP computation, and sparse-prior variants that were not previously available are obtained.
  • For convex truncation detection, Assumption 3.1 is exactly the Gaussian correlation inequality, and the resulting SQ lower bound of Θ(n/(α² polylog)) samples matches the best known polynomial-time algorithm, suggesting its sample complexity is optimal.
  • For noise-robust models, the GFP-SQ equivalence combined with the SQ-LD equivalence implies GFP-hardness also transfers to low-degree polynomial hardness, extending the original FP-LD connection beyond Gaussian additive models.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A practical recipe emerges: to certify SQ hardness of any new detection model, verify Assumption 3.1, often via symmetry or a geometric correlation inequality, and then compute GFP hardness; no explicit SQ adversary is needed.
  • The parameter losses in the equivalence mean the match is qualitative: it equates exponentially many queries with near-threshold sample sizes, but constants and polylog factors are not preserved, so sharp algorithmic thresholds should still be pinned down by direct analyses.
  • The necessity of Assumption 3.1 suggests that models with negative correlations between likelihoods, where signals 'repel', fall outside the physics-to-SQ dictionary and may need a genuinely different hardness witness; the Dirac-atom example shows such models exist naturally.
  • The equivalence supports the view that the annealed Franz-Parisi potential, rather than the quenched one, is the right object for detection hardness, echoing the paper's own open question about whether the quenched potential can also be connected.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper proposes a generalized Franz-Parisi (GFP) hardness criterion, in which the Euclidean-overlap event of the original FP criterion is replaced by an optimized event invariant under a finite symmetry group G; equivalently, the event is expressed through the functional ρ_G(u,v) = max_{g,g'} |⟨L_{g(u)}, L_{g'(v)}⟩_Q − 1|. Under Assumption 3.1 (group-averaged nonnegativity of all moments of the likelihood-ratio inner product), the authors prove a two-way implication between GFP hardness and SQ hardness, with parameter losses, provided the detection problem is information-theoretically undetectable with m_IT samples and the proxy runtime satisfies q ≥ m^{m_IT} in the GFP-to-SQ direction. The equivalence is applied to Gaussian additive models, planted sparse models, NGCA, single-index models, and convex truncation, yielding new SQ lower bounds for mixed sparse linear regression and convex truncation. The paper also gives an example separating the original FP criterion from the optimized GFP criterion.

Significance. If the equivalence were valid for the advertised q = m^{Ω(1)} regime, this would be a substantive conceptual bridge between physics-inspired hardness criteria and SQ lower bounds. The paper contains several valuable elements: the verification of Assumption 3.1 for a range of model families, the new SQ lower bounds for mixed sparse linear regression and convex truncation, and a clean separation between FP and GFP hardness. The proofs are lengthy, and I did not fully verify every computation in Appendix C; the central argument, however, is clear. The main obstacle is that the formal GFP-to-SQ direction in Theorem 3.7 requires q ≥ m^{m_IT}, which for typical m_IT = ω(log n) or m_IT = poly(n) forces q to be super-exponential in n, far beyond the q = m^{Ω(1)} regime claimed in Theorem 1.4 and the abstract. The abstract's unqualified 'equivalence with SQ lower bounds' is therefore not supported by the formal results.

major comments (2)
  1. [§1.1 (Theorem 1.4) and §3.2.2 (Theorem 3.7)] The informal Theorem 1.4 states the GFP–SQ equivalence for any proxy runtime q = m^{Ω(1)}, and the abstract makes an unqualified claim of equivalence. The formal Theorem 3.7(2), however, only yields the clean 'in particular' bound m1 = Θ(m^{1−O(δ)}/m_IT) under the condition q ≥ m^{m_IT} (Theorem 3.7(2)(b)). When m_IT = ω(log n), as the paper itself notes is typical (§3.2.2), this requires q to be super-exponential in n, not m^{Ω(1)}. Thus the central advertised equivalence is not established in the stated regime. The example-specific SQ bounds may survive because those proofs directly verify χ²(P^{⊗4t}‖Q^{⊗4t}) = O(1) and apply the non-simplified bound, but the blanket claim in Theorem 1.4 and the abstract needs to be either proved or substantially weakened.
  2. [§3.1, Assumption 3.1 (Eq. (2))] Assumption 3.1, described in the abstract and introduction as 'mild,' is in fact a strong positive-correlation condition. For the trivial group G = {id}, it requires ⟨L_u, L_v⟩_Q ≥ 1 pointwise for all signal pairs; the paper's own Section 6.2.1 exhibits a natural Dirac-atom model where this fails and where GFP-hardness and SQ-hardness separate. Even with G = ℤ_2, the condition requires nonnegativity of all group-averaged moments, which is not automatic. Since the entire GFP–SQ equivalence depends on this assumption, the phrase 'mild, verifiable assumption' overstates its scope. The authors should either justify the 'mild' terminology more carefully or qualify the applicability claims in the abstract and Theorem 1.4.
minor comments (6)
  1. [§3.2.2, Theorem 3.7(1)] The statement gives the error term as e^{|G|^{-1} m1/m}, but the proof (Appendix B.2) yields e^{|G| m1/m}; the exponent sign/position is inconsistent and should be corrected.
  2. [Definition 1.2] The expectation in the GFP definition is written as 𝔼[⟨L_u^{⊗m}, L_v^{⊗m}⟩_Q 1(A)], but A is a subset of Θ × Θ; the paper should clarify that the event A is in (u,v) and the inner product is over the sample space, e.g., by writing 𝔼_{(u,v)∼π²}[· 1{(u,v)∈A}].
  3. [§4.2.1 (mSLR)] In the proof of Theorem 4.5, the phrase 'using Theorem 3.7 for m_IT = (log n)^T' is potentially confusing because m_IT denotes the information-theoretic threshold sample size, which for mSLR is Θ(k/log(SNR²/(2SNR+1)+1)), much larger than (log n)^T when k = n^{Ω(1)}; what matters is that χ²(P^{⊗m_IT}‖Q^{⊗m_IT}) = O(1) for that specific m_IT, so the notation should be clarified.
  4. [Section 5 title and Section 6.2 heading] There are typographical errors: 'eqal' should be 'equal' in the Section 5 title, and 'Necessacity' should be 'Necessity' in Section 6.2.
  5. [Throughout] There are several minor typos and misspellings, e.g., 'suppport(𝑢)' in §4.2.1 and 'signficantly' in Section 7; a careful proofreading pass is recommended.
  6. [Theorem 3.7(2)] The condition 'any integer q1 > 0' should presumably read 'any integer q1 ≥ 1'; as written, q1 = 0 would make the denominator vanish.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the GFP-SQ equivalence is a genuine reduction, and the informal runtime gap in Theorem 1.4 is a strength issue, not a definitional or fitted equivalence.

full rationale

The central derivation is Theorem 3.7, which proves both directions of the rho_G-FP/SQ equivalence using substantive ingredients: the binomial expansion of the m-sample likelihood inner product, Assumption 3.1 (nonnegativity of group-averaged moments), and a chi-squared bound at 4t samples. SQ hardness is a first-moment condition over all large events, while rho_G-FP hardness is an m-th-moment condition over a quantile event; the proof transfers between them through moment inequalities and Markov/Chebyshev-type truncation, not by definition. The optimized event A in Definition 1.2 and the overlap rho_G are new objects, not restatements of the SQ criterion, and the examples verify Assumption 3.1 by explicit calculation (e.g., Lemma 4.1 for GAMs and Lemma 4.13 for convex truncation) rather than by assuming the target SQ conclusion. Self-citations to Bandeira et al. [6] are used for background and for the planted-sparse-model verification, but the cited result is a published proposition with assumptions independent of the present target theorem, so it does not make the argument circular. The advertised Theorem 1.4 is stronger than the formal Theorem 3.7, which needs q >= m^{m_IT} for the clean 'in particular' SQ bound; this is a scope/strength gap, not a circularity, and does not raise the circularity score.

Assumptions & free parameters 3 free parameters · 4 assumptions · 1 invented entities

The central claim rests on Assumption 3.1 (moment nonnegativity), the information-theoretic threshold condition, and the model-specific verifications in Section 4. No numerical parameters are fitted to data; the choice of the symmetry group G is a structural selection made per model class. The Gaussian correlation inequality is imported as an external theorem for the convex truncation example. The GFP criterion itself is a new definitional object, not an empirical entity.

free parameters (3)
  • Symmetry group G in Assumption 3.1 = Trivial group or Z_2 in all examples
    The main theorem applies only after choosing a pi-preserving group such that the moment nonnegativity (2) holds. The choice of G is a structural, hand-made selection per model class, not a number fitted to data.
  • Prior mass rho in the Section 5 counterexample = exp(-n^epsilon/2)
    Hand-chosen to make the two-point prior example GFP-hard while FP-easy; a construction parameter, not fitted to data.
  • Slice width kappa in the convex truncation prior = Phi(kappa) = 1 - alpha/2
    kappa is chosen so each slab K_v has Gaussian volume 1 - alpha; it is determined by alpha, not fitted to data.
assumptions (4)
  • domain assumption Assumption 3.1 (group-averaged moment nonnegativity of the likelihood-ratio inner product)
    Load-bearing condition of Theorems 3.5 and 3.7; verified model-by-model in Section 4, but it fails for natural models such as the Dirac-atom example in Section 6.2.1, where GFP-hardness holds and SQ-hardness fails.
  • domain assumption Information-theoretic undetectability at m_IT samples: chi^2(P^m_IT | Q^m_IT) = O(1)
    Required in Theorem 3.7(2) to control the even-moment terms E[(⟨L_u,L_v⟩-1)^{2t}]; the paper shows it is necessary via the dense planted clique variant in Section 6.2.2.
  • standard math Gaussian correlation inequality for symmetric convex bodies
    Used in Lemma 4.13 to verify Assumption 3.1 for convex truncation models; cited to Royen (2014) and Latała-Matlak (2017), externally proven.
  • domain assumption Noise robustness (Assumption A.8) for the LD-GFP equivalence in Appendix A
    Only needed for the appendix's LD implications, inherited from Brennan et al. (2021); not required for the main GFP-SQ theorems.
invented entities (1)
  • GFP hardness criterion and the rho_G overlap functional
    purpose: Refined hardness notion whose optimal event and overlap rho_G(u,v) = max_{g,g'} |⟨L_{g(u)},L_{g'(v)}⟩_Q - 1| are built to match the SQ correlation functional.
    A definitional object, not an empirical entity; it has no falsifiable handle outside the paper. Its value is measured by the proven equivalence and the new lower bounds it produces. It is not a new physical mediator, but it is a new theoretical object introduced to make the equivalence hold.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds." pith.science (2026). https://pith.science/paper/5YYJJBX6

@misc{pith2026250606259,
  author       = {Pith},
  title        = {Pith review of: An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5YYJJBX6}},
  note         = {Machine review of arXiv:2506.06259}
}
read the original abstract

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

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

    math.ST 2025-06 accept novelty 2.0 of 10

    A survey of the low-degree polynomial framework for predicting statistical-computational gaps, covering definitions, evidence, connections to other methods, and open problems.

Reference graph

Works this paper leans on

41 extracted references · 36 canonical work pages · cited by 1 Pith paper

  1. [1]

    Group testing: an information theory perspective

    Matthew Aldridge, Oliver Johnson, Jonathan Scarlett, et al. Group testing: an information theory perspective. Foundations and Trends® in Communications and Information Theory , 15(3-4):196–392, 2019

    work page 2019

  2. [2]

    High-dimensional analysis of semidefinite relaxations for sparse principal com- ponents

    Arash A Amini and Martin J Wainwright. High-dimensional analysis of semidefinite relaxations for sparse principal com- ponents. In 2008 IEEE international symposium on information theory , pages 2454–2458. IEEE, 2008

    work page 2008

  3. [3]

    Algorithmic thresholds for tensor pca

    Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Algorithmic thresholds for tensor pca. The Annals of Probability, 48(4):2052–2087, 2020

    work page 2020

  4. [4]

    Free energy wells and overlap gap property in sparse pca.Communi- cations on Pure and Applied Mathematics , 76(10):2410–2473, 2023

    G ´erard Ben Arous, Alexander S Wein, and Ilias Zadik. Free energy wells and overlap gap property in sparse pca.Communi- cations on Pure and Applied Mathematics , 76(10):2410–2473, 2023

    work page 2023

  5. [5]

    Statistical-computational tradeoffs in mixed sparse linear regression

    Gabriel Arpino and Ramji Venkataramanan. Statistical-computational tradeoffs in mixed sparse linear regression. In The Thirty Sixth Annual Conference on Learning Theory , pages 921–986. PMLR, 2023

    work page 2023

  6. [6]

    The franz-parisi criterion and computational trade-offs in high dimensional statistics

    Afonso S Bandeira, Ahmed El Alaoui, Samuel Hopkins, Tselil Schramm, Alexander S Wein, and Ilias Zadik. The franz-parisi criterion and computational trade-offs in high dimensional statistics. Advances in Neural Information Processing Systems , 35:33831–33844, 2022

    work page 2022

  7. [7]

    Universality of computational lower bounds for submatrix detection

    Matthew Brennan, Guy Bresler, and Wasim Huleihel. Universality of computational lower bounds for submatrix detection. In Conference on Learning Theory , pages 417–468. PMLR, 2019

    work page 2019

  8. [8]

    Statistical query algorithms and low degree tests are almost equivalent

    Matthew S Brennan, Guy Bresler, Sam Hopkins, Jerry Li, and Tselil Schramm. Statistical query algorithms and low degree tests are almost equivalent. In Conference on Learning Theory , pages 774–774. PMLR, 2021

    work page 2021

Show all 41 references
  1. [9]

    Can neural networks achieve optimal computational- statistical tradeoff? an analysis on single-index model

    Siyu Chen, Beining Wu, Miao Lu, Zhuoran Yang, and Tianhao Wang. Can neural networks achieve optimal computational- statistical tradeoff? an analysis on single-index model. InThe Thirteenth International Conference on Learning Representations

  2. [10]

    On the low-temperature mcmc threshold: the cases of sparse tensor pca, sparse regression, and a geometric rule

    Zongchen Chen, Conor Sheehan, and Ilias Zadik. On the low-temperature mcmc threshold: the cases of sparse tensor pca, sparse regression, and a geometric rule. arXiv preprint arXiv:2408.00746, 2024

    2024 arXiv

  3. [11]

    Statistical and computational phase transitions in group testing

    Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Alexander S Wein, and Ilias Zadik. Statistical and computational phase transitions in group testing. In Conference on Learning Theory , pages 4764–4781. PMLR, 2022

    2022

  4. [12]

    Computational-statistical gaps in gaussian single-index models

    Alex Damian, Loucas Pillaud-Vivien, Jason Lee, and Joan Bruna. Computational-statistical gaps in gaussian single-index models. In The Thirty Seventh Annual Conference on Learning Theory , pages 1262–1262. PMLR, 2024

    2024

  5. [13]

    Efficient statistics, in high dimen- sions, from truncated samples

    Constantinos Daskalakis, Themis Gouleakis, Chistos Tzamos, and Manolis Zampetakis. Efficient statistics, in high dimen- sions, from truncated samples. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages 639–649. IEEE, 2018

    2018

  6. [14]

    Computationally and statistically efficient truncated regression

    Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, and Manolis Zampetakis. Computationally and statistically efficient truncated regression. In Conference on learning theory , pages 955–960. PMLR, 2019

    2019

  7. [15]

    Testing convex truncation

    Anindya De, Shivam Nadimpalli, and Rocco A Servedio. Testing convex truncation. In Proceedings of the 2023 Annual ACM- SIAM Symposium on Discrete Algorithms (SODA) , pages 4050–4082. SIAM, 2023

    2023

  8. [16]

    Statistical query lower bounds for robust estimation of high- dimensional gaussians and gaussian mixtures

    Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high- dimensional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 73–84. IEEE, 2017

    2017

  9. [17]

    Efficient algorithms and lower bounds for robust linear regression

    Ilias Diakonikolas, Weihao Kong, and Alistair Stewart. Efficient algorithms and lower bounds for robust linear regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2745–2754. SIAM, 2019

    2019

  10. [18]

    Subexponential-time algorithms for sparse pca

    Yunzi Ding, Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Subexponential-time algorithms for sparse pca. Foundations of Computational Mathematics , 24(3):865–914, 2024

    2024

  11. [19]

    Curse of heterogeneity: Computational barriers in sparse mixture models and phase retrieval

    Jianqing Fan, Han Liu, Zhaoran Wang, and Zhuoran Yang. Curse of heterogeneity: Computational barriers in sparse mixture models and phase retrieval. arXiv preprint arXiv:1808.06996, 2018

    2018 arXiv

  12. [20]

    Statistical algorithms and a lower bound for detecting planted cliques

    Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. Journal of the ACM (JACM) , 64(2):1–37, 2017

    2017

  13. [21]

    Recipes for metastable states in spin glasses

    Silvio Franz and Giorgio Parisi. Recipes for metastable states in spin glasses. Journal de Physique I , 5(11):1401–1415, 1995

    1995

  14. [22]

    Effective potential in glassy systems: theory and simulations.Physica A: Statistical Mechanics and its Applications, 261(3-4):317–339, 1998

    Silvio Franz and Giorgio Parisi. Effective potential in glassy systems: theory and simulations.Physica A: Statistical Mechanics and its Applications, 261(3-4):317–339, 1998

    1998

  15. [23]

    An examination into the registered speeds of american trotting horses, with remarks on their value as hereditary data

    Francis Galton. An examination into the registered speeds of american trotting horses, with remarks on their value as hereditary data. Proceedings of the Royal Society of London , 62(379-387):310–315, 1898

  16. [24]

    Sharp thresholds imply circuit lower bounds: from random 2-sat to planted clique

    David Gamarnik, Elchanan Mossel, and Ilias Zadik. Sharp thresholds imply circuit lower bounds: from random 2-sat to planted clique. arXiv preprint arXiv:2311.04204, 2023

    2023 arXiv

  17. [25]

    Sparse high-dimensional linear regression

    David Gamarnik and Ilias Zadik. Sparse high-dimensional linear regression. estimating squared error and a phase transition. The Annals of Statistics, 50(2):880–903, 2022. AN OPTIMIZED FRANZ-PARISI CRITERION EQUIVALENT WITH SQ LOWER BOUNDS 21

    2022

  18. [26]

    Inequalities on the probability content of convex regions for elliptically contoured distributions

    S Das Gupta, Morris L Eaton, Ingram Olkin, Michael Perlman, Leonard J Savage, and Milton Sobel. Inequalities on the probability content of convex regions for elliptically contoured distributions. InProceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Prob...

    1970

  19. [27]

    Statistical Inference and the Sum of Squares Method

    Samuel Hopkins. Statistical Inference and the Sum of Squares Method . PhD thesis, Cornell University, 2018

    2018

  20. [28]

    Near-optimal statistical query lower bounds for agnostically learning intersections of halfspaces with gaussian marginals

    Daniel J Hsu, Clayton H Sanford, Rocco Servedio, and Emmanouil Vasileios Vlatakis-Gkaragkounis. Near-optimal statistical query lower bounds for agnostically learning intersections of halfspaces with gaussian marginals. InConference on Learning Theory, pages 283–312. PMLR, 2022

    2022

  21. [29]

    Semiparametric least squares (sls) and weighted sls estimation of single-index models

    Hidehiko Ichimura. Semiparametric least squares (sls) and weighted sls estimation of single-index models. Journal of econo- metrics, 58(1-2):71–120, 1993

    1993

  22. [30]

    Large cliques elude the metropolis process

    Mark Jerrum. Large cliques elude the metropolis process. Random Structures & Algorithms , 3(4):347–359, 1992

    1992

  23. [31]

    Efficient noise-tolerant learning from statistical queries

    Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM) , 45(6):983–1006, 1998

    1998

  24. [32]

    Notes on computational hardness of hypothesis testing: Pre- dictions using the low-degree likelihood ratio

    Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Notes on computational hardness of hypothesis testing: Pre- dictions using the low-degree likelihood ratio. In ISAAC Congress (International Society for Analysis, its Applications and Computation), pages 1–50. Springer, 2019

    2019

  25. [33]

    Royen’s proof of the gaussian correlation inequality

    Rafał Latała and Dariusz Matlak. Royen’s proof of the gaussian correlation inequality. In Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 2014–2016, pages 265–275. Springer, 2017

    2014

  26. [34]

    Generalized linear models

    Peter McCullagh. Generalized linear models. Routledge, 2019

    2019

  27. [35]

    On the limitation of spectral methods: From the gaussian hidden clique problem to rank-one perturbations of gaussian tensors

    Andrea Montanari, Daniel Reichman, and Ofer Zeitouni. On the limitation of spectral methods: From the gaussian hidden clique problem to rank-one perturbations of gaussian tensors. Advances in Neural Information Processing Systems , 28, 2015

    2015

  28. [36]

    On the systematic fitting of curves to observations and measurements

    Karl Pearson. On the systematic fitting of curves to observations and measurements. Biometrika, 1(3):265–303, 1902

    1902

  29. [37]

    A statistical model for tensor pca

    Emile Richard and Andrea Montanari. A statistical model for tensor pca. Advances in neural information processing systems , 27, 2014

    2014

  30. [38]

    A simple proof of the gaussian correlation conjecture extended to multivariate gamma distributions

    Thomas Royen. A simple proof of the gaussian correlation conjecture extended to multivariate gamma distributions. arXiv preprint arXiv:1408.1028, 2014

    2014 arXiv

  31. [39]

    Computational barriers to estimation from low-degree polynomials

    Tselil Schramm and Alexander S Wein. Computational barriers to estimation from low-degree polynomials. The Annals of Statistics, 50(3):1833–1858, 2022

    2022

  32. [40]

    Lattice-based methods surpass sum-of-squares in clustering

    Ilias Zadik, Min Jae Song, Alexander S Wein, and Joan Bruna. Lattice-based methods surpass sum-of-squares in clustering. In Conference on Learning Theory , pages 1247–1248. PMLR, 2022

    2022

  33. [41]

    low-degree likelihood ratio

    Lenka Zdeborov ´a and Florent Krzakala. Statistical physics of inference: Thresholds and algorithms. Advances in Physics , 65(5):453–552, 2016. 22 S. CHEN, T. MISIAKIEWICZ, I. ZADIK, AND P. ZHANG Appendix A. Eqivalence between LD, SQ, and GFP In this Appendix, we discuss the e...

    2016

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.