{"id":"bba9735f-7a88-4bdc-8a7d-7830260a1d9d","arxiv_id":"2506.06259","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"An optimized Franz-Parisi hardness criterion is proven equivalent to statistical query lower bounds under a verifiable correlation assumption, yielding new average-case hardness results for mixed sparse regression and convex truncation.","lead":"This paper modifies the Franz-Parisi criterion, a statistical physics tool for predicting when detection problems are computationally hard, by letting the overlap structure be optimized rather than fixed to the Euclidean inner product. The authors prove the optimized criterion is equivalent to statistical query lower bounds for a broad class of models and use it to derive new lower bounds for mixed sparse regression and convex truncation detection.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The GFP–SQ equivalence is only proven for q ≥ m^{m_IT}; the advertised q = m^{Ω(1)} regime in Theorem 1.4 and the abstract does not follow from Theorem 3.7.","rationale":"I read the paper in good faith and found the core idea plausible: optimizing the overlap event in the Franz–Parisi criterion can match SQ hardness, provided the correlation structure of likelihood ratios is sufficiently positive. The verification of Assumption 3.1 for GAMs, planted sparse models, NGCA, single-index models, and convex truncation is a genuine strength, and the paper's willingness to exhibit counterexamples where the assumption fails and the equivalence breaks is scientifically honest. The reader's CONDITIONAL verdict is reasonable. My concern is different from the reader's weakest assumption: rather than Assumption 3.1 itself, the most load-bearing issue for the central advertised claim is the runtime regime mismatch. The formal Theorem 3.7(2) only yields the clean SQ-hardness statement when q is at least m^{m_IT} (up to constants), which is super-exponential for typical m_IT = poly(n). Theorem 1.4 and the abstract, however, claim the equivalence for q = m^{Ω(1)}. This is not a mere cosmetic issue: the proof's choice of t and q1 requires t ≈ m_IT to absorb the χ² term, and q = m^{Ω(1)} would only allow t = O(1), producing a much weaker SQ-hardness statement. The examples avoid this by directly controlling χ²(P^{⊗4t} ‖ Q^{⊗4t}), so the specific lower bounds in Sections 4.2–4.5 may be correct, but the blanket equivalence advertised as the main contribution is not established in the stated regime. I therefore recommend keeping the reader's CONDITIONAL verdict rather than upgrading to ACCEPT, and I would not move it to REJECT because the formal theorem, if read with its explicit q ≥ m^{m_IT} condition, is a coherent and nontrivial result.","tokens_in":39376,"tokens_out":40648,"duration_ms":385536,"concrete_test":"Independently re-derive the 'In particular' passage of Theorem 3.7(2) from the proof in Appendix B.2, fixing t = m_IT/4 and q1 = m^{δ m_IT}. Verify step by step whether the claimed bound m1 = Θ(m^{1-O(δ)}/m_IT) follows using only the assumption χ²(P^{⊗m_IT} ‖ Q^{⊗m_IT}) = O(1), without any bound on χ²(P^{⊗4t} ‖ Q^{⊗4t}) for 4t > m_IT. If the derivation requires t = m_IT rather than m_IT/4, or if it needs an additional moment bound, then the formal theorem does not imply the abstract's equivalence for q = m^{Ω(1)}, and Theorem 1.4 must be revised to state the q ≥ m^{m_IT} restriction explicitly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central advertised claim is that the optimized Franz–Parisi criterion is equivalent to SQ lower bounds, with Theorem 1.4 stating this for any proxy runtime q = m^{Ω(1)}. The formal Theorem 3.7(2) is strictly weaker. Its SQ-hardness conclusion for a (q,m,ε)-ρ_G-FP hard task is m1 = m / ((t(1+ε)^{1/t} + χ²(P^{⊗4t} ‖ Q^{⊗4t}))(q1)^{2/t}) for some even t ≤ log q / log m. The clean 'in particular' statement m1 = Θ(m^{1-O(δ)}/m_IT) is obtained only by taking t ≈ m_IT (or m_IT/4) and q1 = m^{δ m_IT}, which forces log q ≥ (m_IT/4) log m, i.e., q ≥ m^{m_IT/4}. The theorem states the even stronger q ≥ m^{m_IT}. When m_IT = ω(log n), as the paper says is typical, this requires q to be super-exponential in n, far beyond the q = m^{Ω(1)} regime advertised in Theorem 1.4. The abstract states the equivalence without any such runtime restriction, so the blanket claim is unsupported. The example-specific SQ bounds may survive because those proofs directly verify χ²(P^{⊗4t} ‖ Q^{⊗4t}) = O(1) and apply the non-simplified bound rather than the 'in particular' step, but the main equivalence as advertised is not established in the q = m^{Ω(1)} regime.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":39577,"tokens_out":9752,"duration_ms":93514,"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":[{"comment":"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.","section":"§1.1 (Theorem 1.4) and §3.2.2 (Theorem 3.7)"},{"comment":"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.","section":"§3.1, Assumption 3.1 (Eq. (2))"}],"minor_comments":[{"comment":"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.","section":"§3.2.2, Theorem 3.7(1)"},{"comment":"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}].","section":"Definition 1.2"},{"comment":"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.","section":"§4.2.1 (mSLR)"},{"comment":"There are typographical errors: 'eqal' should be 'equal' in the Section 5 title, and 'Necessacity' should be 'Necessity' in Section 6.2.","section":"Section 5 title and Section 6.2 heading"},{"comment":"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.","section":"Throughout"},{"comment":"The condition 'any integer q1 > 0' should presumably read 'any integer q1 ≥ 1'; as written, q1 = 0 would make the denominator vanish.","section":"Theorem 3.7(2)"}],"recommendation":"major_revision","confidential_remarks":"The paper contains useful results, especially the example-specific SQ lower bounds and the FP/GFP separation, but the advertised equivalence is not established for q = m^{Ω(1)}; the formal condition q ≥ m^{m_IT} makes the GFP-to-SQ direction super-polynomial in typical settings. The abstract and Theorem 1.4 substantially overclaim. I recommend a major revision in which the authors either prove a better dependence on m_IT or explicitly restate the main equivalence in the narrower q regime that the proof supports. The Assumption 3.1 also deserves a more careful presentation of its strength and limitations."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here is my take on Chen et al. The core is a genuine result: a formal equivalence between the optimized Franz-Parisi criterion and SQ hardness under Assumption 3.1, with the assumption checked for several important models, plus two new SQ lower bounds and a clean separation example. That part is worth serious attention.\n\nThe problem is the packaging. Theorem 3.7(2) only yields the clean \"in particular\" SQ bound under q ≥ m^{m_IT} (or m^{m_IT/4} after the calculation), and the paper's own examples have m_IT = ω(log n) or worse. The abstract and informal Theorem 1.4 advertise q = m^{Ω(1)}, which does not follow. The stress-test note is right: the non-simplified bound may save the mSLR and convex truncation applications, because those proofs directly verify χ²(P^{⊗4t}||Q^{⊗4t}) = O(1) and choose t accordingly, but the headline equivalence in the q = m^{Ω(1)} regime is unproven. This is not a cosmetic issue; it changes the scope of the main claim.\n\nI also think the \"equivalence\" is partly engineered. The rho_G overlap function and the optimized event in Definition 1.2 are chosen so that GFP-hardness looks like SQ-hardness. That does not make Theorem 3.7 trivial—there is real work in proving the moment inequalities and the group averaging—but it lowers the conceptual novelty: the paper is less \"two frameworks turn out to be equivalent\" and more \"a carefully designed geometric criterion reproduces SQ.\" The Section 5 separation example is a nice addition, and the necessity discussions in Section 6 are honest.\n\nThe lengthy computations in Appendices B and C I could not fully verify. There are exponent inconsistencies between Theorem 4.5 and its proof that need checking, and the importation of technical lemmas from other papers without restatement makes independent verification hard. None of this obviously breaks the formal results, but it is enough to keep me at conditional.\n\nBottom line: a serious paper that deserves a serious referee, but the authors should be pushed to correct the mismatch between the informal claims and Theorem 3.7. If the q = m^{Ω(1)} version is false, the abstract and Theorem 1.4 need to be rewritten; if it is true, they need to show the stronger proof. I would send it to peer review with that expectation.","headline":"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.","tokens_in":40342,"tokens_out":2871,"would_cite":true,"duration_ms":26224,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62C20","62H15","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Franz-Parisi criterion","statistical query hardness","computational-statistical tradeoffs","high-dimensional detection","Gaussian additive models","planted sparse models","non-Gaussian component analysis","convex truncation"],"falsifier":"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.","tokens_in":38983,"feed_emoji":"🔗","tokens_out":9139,"duration_ms":81064,"temperature":0.7,"pith_summary":"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.","feed_headline":"Franz-Parisi criterion proven equivalent to SQ hardness","feed_subtitle":"The equivalence unifies two hardness frameworks and yields new lower bounds for mixed sparse regression and convex truncation.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces the original Franz-Parisi criterion for detection hardness and proves its equivalence with low-degree hardness for Gaussian additive models; this is the starting point the paper generalizes.","marker":"[6]"},{"why":"Establishes the equivalence between Statistical Query hardness and low-degree hardness under noise robustness; the paper adapts these proofs for the GFP-SQ and GFP-LD connections.","marker":"[8]"},{"why":"Defines the statistical dimension and SQ-hardness framework that the paper uses as the target notion of hardness.","marker":"[20]"},{"why":"Provides the Gaussian correlation inequality used to verify Assumption 3.1 for convex truncation models in Lemma 4.13.","marker":"[38]"},{"why":"Gives the state-of-the-art polynomial-time algorithm for convex truncation detection whose sample complexity the new SQ lower bound shows cannot be improved.","marker":"[15]"},{"why":"Supplies the mixed sparse linear regression model and its low-degree lower bound that the new SQ lower bound complements.","marker":"[5]"},{"why":"Proves the original SQ lower bound for non-Gaussian component analysis that this paper rederives via GFP hardness.","marker":"[16]"},{"why":"Proves the SQ lower bound for single-index models that this paper reproduces and extends to sparse priors.","marker":"[12]"}],"fun_headline_variants":["Optimized FP criterion matches SQ hardness","Franz-Parisi and SQ frameworks unified","New proof: FP criterion ↔ SQ lower bounds","Equivalence yields fresh SQ hardness results"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Optimized FP criterion matches SQ hardness","Franz-Parisi and SQ frameworks unified","New proof: FP criterion ↔ SQ lower bounds","Equivalence yields fresh SQ hardness results"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000228,"raw_usage":{"total_tokens":1584,"prompt_tokens":1162,"completion_tokens":422,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":778,"completion_tokens_details":{"reasoning_tokens":367}},"tokens_in":778,"tokens_out":422,"duration_ms":4826,"temperature":1.0,"reasoning_tokens":367,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:59:49.969239+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"The franz-parisi criterion and computational trade-offs in high dimensional statistics","cited_arxiv_id":null,"evidence_quote":"Introduces the original Franz-Parisi criterion for detection hardness and proves its equivalence with low-degree hardness for Gaussian additive models; this is the starting point the paper generalizes."},{"cited_title":"Statistical query algorithms and low degree tests are almost equivalent","cited_arxiv_id":null,"evidence_quote":"Establishes the equivalence between Statistical Query hardness and low-degree hardness under noise robustness; the paper adapts these proofs for the GFP-SQ and GFP-LD connections."},{"cited_title":"Statistical algorithms and a lower bound for detecting planted cliques","cited_arxiv_id":null,"evidence_quote":"Defines the statistical dimension and SQ-hardness framework that the paper uses as the target notion of hardness."},{"cited_title":"Testing convex truncation","cited_arxiv_id":null,"evidence_quote":"Gives the state-of-the-art polynomial-time algorithm for convex truncation detection whose sample complexity the new SQ lower bound shows cannot be improved."},{"cited_title":"Statistical-computational tradeoffs in mixed sparse linear regression","cited_arxiv_id":null,"evidence_quote":"Supplies the mixed sparse linear regression model and its low-degree lower bound that the new SQ lower bound complements."},{"cited_title":"Statistical query lower bounds for robust estimation of high- dimensional gaussians and gaussian mixtures","cited_arxiv_id":null,"evidence_quote":"Proves the original SQ lower bound for non-Gaussian component analysis that this paper rederives via GFP hardness."},{"cited_title":"Computational-statistical gaps in gaussian single-index models","cited_arxiv_id":null,"evidence_quote":"Proves the SQ lower bound for single-index models that this paper reproduces and extends to sparse priors."}],"review_version":1}