{"id":"5aa59552-b360-4973-b6e1-ac05a1c241e7","arxiv_id":"1908.06130","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Assuming a k-partite planted clique conjecture, the authors prove tight k-to-k^2 sample-complexity lower bounds for robust sparse mean estimation, semirandom community recovery, and a universal class of sparse mixture problems.","lead":"This paper proves new conditional computational lower bounds for robust sparse mean estimation, semirandom community recovery, and sparse mixture learning, assuming a planted-clique-style conjecture. If the conjecture holds, efficient algorithms need roughly k^2 samples where information-theoretic limits only need k, and a semirandom adversary shifts the detection threshold to the recovery threshold.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The o(n^{-3d-1}) tail condition in Definition 7.4 is incompatible with the Gaussian sparse PCA example for d = ω(log n), so the universality class as stated is far smaller than claimed.","rationale":"The paper's central reductions to rsme and semi-cr appear sound and are based on k-pc. The universality result, however, rests on Definition 7.4 whose probability parameter o(n^{-3d-1}) is too strong to hold for Gaussian marginals when d grows faster than log n. Since Theorem 7.6 explicitly assumes k^2=o(d), the intended applications (e.g., sparse PCA) fall outside the stated class. This is a verifiable technical error in the manuscript, not a disagreement with consensus. The proof of Corollary 7.7 contains a mistaken tail estimate. If the probability bound is relaxed to o(1/(n d)) (which is all the TV argument needs), the example may satisfy the condition; thus the issue is fixable and does not invalidate the reduction framework. Hence ACCEPT should be CONDITIONAL: accept with revision.","tokens_in":63621,"tokens_out":18082,"duration_ms":174903,"concrete_test":"Fix n=10^6, take d=n^{1/2}=1000, k=10, θ=(log n)^{-5}. For Q=N(0,1), Pν=N(t,1) with t=√(3θ log n/k), compute the set S defined by the two inequalities in Definition 7.4 with the reduction's μ1=Θ(1/√(w k log n)). Numerically estimate P_Q(S^c) and compare with n^{-3d-1}≈10^{-6000}. The observed P_Q(S^c) will be ≈10^{-O(1)} (since M is polylogarithmic), demonstrating the condition fails. Analytically: verify that M ≥ √(6d log n) is required for the tail, but the L1 bound gives M = O(log^2 n / √w) for θ=(log n)^{-5}, and √(6d log n)=n^{1/4}√(6 log n) ≫ log^2 n.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Definition 7.4 requires the likelihood-ratio bounds to hold on a set of Q-probability 1 - o(n^{-3d-1}). In Corollary 7.7, Q=N(0,1) and Pν=N(t,1) with t=ν√(3θ log n/k), θ=o((log n)^{-4}). The first inequality |L1|≤1/√(k log n) forces |x| ≤ M = O(1/(√θ log n)) = o((log n)^C) (in fact ω(log n) but polylog), while the tail requirement forces M ≥ √(6d log n) to make exp(-M^2/2) ≤ n^{-3d-1}. For any d = n^γ with γ>0, √(6d log n) is n^{γ/2}√(6 log n), which dominates any polylogarithmic M. Hence Q(S^c) is not o(n^{-3d-1}); the sparse PCA marginals are not in uc(n,k,d). The proof's assertion that x=o(log n) has probability 1-o(n^{-3d-1}) for d=poly(n) is false; the Gaussian tail is n^{-Ω(log n)}, which is much larger than n^{-3d-1} for d=ω(1). Consequently Theorem 7.6's universality class does not contain the claimed examples, though Theorems 2.6 and 2.8 are unaffected.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops average-case reductions from a k-partite planted clique / planted dense subgraph conjecture to three high-dimensional statistical problems: robust sparse mean estimation, semirandom single-community recovery, and general sparse mixture detection. The reductions pass through a new intermediate problem, Imbalanced Sparse Gaussian Mixtures, and use rotation matrices built from hyperplanes over finite fields, together with a new 3-ary rejection-kernel gadget. The main theorems are Theorem 2.6 / 5.1 (hardness for robust sparse mean estimation at n = o(ε^3 k^2), with a tight k-to-k^2 gap for polylogarithmic ε), Theorem 2.8 / 6.3 (hardness of semirandom community recovery at snr = o(n/(k^2 log n)) for constant ambient density), and Theorem 2.9 / 7.6 (a universality class uc(n,k,d) for sparse-mixture detection at n = o(k^2)). Section 8 gives low-degree polynomial and statistical-query evidence for the k-partite planted clique assumption. The paper is careful about total-variation accounting and decomposes its reductions into modular lemmas.","tokens_in":63994,"tokens_out":9998,"duration_ms":114189,"significance":"If the main results are correct, they provide substantial structural insight: average-case evidence for the conjectured robust sparse mean gap, a demonstration that a semirandom adversary shifts the planted-dense-subgraph detection threshold to the recovery threshold, and a framework that unifies several k-to-k^2 statistical-computational gaps. The reduction machinery is novel and reusable, and the explicit total-variation bounds are a strength; the paper also gives concrete low-degree and SQ evidence for its nonstandard k-pc assumption. The main caveat is that the universality section, as written, contains a load-bearing inconsistency in the verification of its flagship example.","major_comments":[{"comment":"The proof of Corollary 7.7 asserts that the set x = o(log n) has Q-probability 1 - o(n^{-3d-1}) when d = poly(n), but this is false: under Q = N(0,1), the complement {|x| > C log n} has probability exp(-Ω(log^2 n)) = n^{-Ω(log n)}, which is far larger than n^{-3d-1} whenever d = ω(log n). Since the theorem's hypotheses n = o(k^2) and k^2 = o(d) imply d = ω(n), the Gaussian sparse PCA marginals are not in uc(n,k,d) under Definition 7.4 as stated. The claimed verification that sparse PCA lies in the universality class therefore fails for the relevant parameter regime.","section":"§7.3, Definition 7.4, Corollary 7.7"},{"comment":"Because of the tail condition in Definition 7.4, the 'nearly negligible dependence on n and d' remark in Section 7.3 is not justified: the o(n^{-3d-1}) probability level forces the occurrence set for the likelihood-ratio inequalities to have exponentially small complement, which excludes natural sub-Gaussian examples whenever d is superlogarithmic. The universality theorem is therefore stronger than what is actually established; the examples listed after Corollary 7.7, including sparse PCA in the spiked covariance model, are not shown to belong to uc(n,k,d). This issue is local to Section 7 and appears fixable by weakening the tail condition to something like o(1/(nd)) and re-verifying the concentrated-LLR examples under that condition, but as written it blocks the universality claim.","section":"§7.3 and Theorem 7.6"}],"minor_comments":[{"comment":"The paper is appropriately candid that k-pc is a new assumption, but the phrase 'mild promise' could mislead: Section 8 gives low-degree and SQ evidence, not a reduction from standard planted clique, so the main theorems should consistently say 'conditional on the k-partite planted clique/dense subgraph conjecture' rather than implying hardness follows from the standard pc conjecture alone.","section":"§1.1 and §8"},{"comment":"The parameter ν is used both as the SNR lower bound and as part of the notation ν^2 = o(n/k^2 log n) in Theorem 6.3, and Corollary 6.4 reuses ν with a different meaning; using separate symbols for the SNR threshold and the upper-bound rate would improve readability.","section":"Theorem 6.3 and Corollary 6.4"},{"comment":"The proof of Proposition 8.3 is presented as a sketch; in particular, the constant C in the degree bound D ≤ C log n for k-pc and the summation range in the k-pds calculation should be stated explicitly so that the O(1) Fourier-energy bound can be checked directly.","section":"Appendix A, proof of Proposition 8.3"},{"comment":"The notation (M_R)_{F'_i} = (M_G)_{F_i} H_{r,t}^T is slightly ambiguous because F_i refers to column blocks of the padded matrix while F'_i denotes row blocks of the rotated matrix; a sentence clarifying the index conventions would help the reader.","section":"Figure 2, Step 5"}],"recommendation":"major_revision","confidential_remarks":"The flaw in Section 7 is localized and does not appear to affect Theorems 2.6, 2.8, or the reduction framework in Sections 4-6. If the authors weaken the tail condition in Definition 7.4 to a level compatible with sub-Gaussian concentration (e.g., o(1/(nd))) and re-verify the listed examples, the universality claim would be credible. The paper is otherwise strong and suitable for a leading theory journal after this revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe first thing to know: this is a serious paper with two solid main results and one overclaimed universality theorem. The reductions from k-partite planted clique to robust sparse mean estimation at n=o(epsilon^3 k^2) and to semirandom community recovery at the recovery threshold are real. The rotation gadgets via hyperplanes in F_r^t and the ISGM intermediate are new and well-executed. I checked the total variation bounds in Lemmas 4.8 and 4.11; they hold up, and the parameter handling is careful.\n\nThe soft spot is Section 7. The definition of the universality class uc(n,k,d) requires the likelihood-ratio bounds to hold on a set of Q-probability 1 - o(n^{-3d-1}). The sparse PCA verification in Corollary 7.7 is wrong for d growing with n. With Q=N(0,1) and P_nu=N(t,1), t ~ sqrt(theta log n/k), the first bound forces |x| <= O(1/(sqrt(theta) log n)), which is at most polylogarithmic. But the tail requirement forces |x| >= sqrt(6d log n) to make the Gaussian tail o(n^{-3d}). For d = n^gamma, that lower bound is n^{gamma/2}, dominating any polylog. So the claimed marginals are not in uc(n,k,d) unless d is constant. The proof's assertion that x=o(log n) has probability 1-o(n^{-3d-1}) for d=poly(n) is false; the Gaussian tail is n^{-Omega(log n)}, much larger than n^{-3d}. This doesn't destroy the paper--Theorems 2.6 and 2.8 don't rely on it--but it undercuts the universality claim as advertised. The class may be nonempty (compactly supported likelihood ratios), but it doesn't include the canonical sparse PCA example.\n\nOne more caveat: Section 8 gives only low-degree and SQ evidence for the k-partite promise in k-pc, not a reduction from ordinary planted clique. That's a genuine assumption, but clearly stated and not circular. The paper leans heavily on the authors' own earlier lemmas; this is fine since the lemmas have stated proofs.\n\nBottom line: worth a serious referee. I'd send it out. The referee should demand a fix or a major qualification for the universality section--either loosen the tail condition, prove the Gaussian example differently, or state the theorem with d constant. The main reductions are publishable as is.","headline":"Solid average-case reductions for robust sparse mean and semirandom community recovery; the universality section overclaims because the sparse PCA example fails the tail condition.","tokens_in":64468,"tokens_out":4415,"would_cite":true,"duration_ms":43041,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that a partition-constrained planted clique conjecture forces $k$-to-$k^2$ sample-count barriers in robust sparse mean estimation, semirandom community recovery, and a universality class of sparse mixture problems.","keywords":["average-case reductions","planted clique conjecture","statistical-computational gap","robust sparse mean estimation","semirandom adversary","planted dense subgraph","sparse mixtures","k-to-k^2 gaps"],"falsifier":"A concrete way to refute the chain is to exhibit a randomized polynomial-time test that distinguishes $G(n,1/2)$ from the $k$-partite planted clique for some sequence with $k=o(\\sqrt n)$; through the paper's own reductions, such a test would also solve all three target problems, and conversely a polynomial-time robust sparse mean estimator with $n=o(k^2)$ samples at the signal level specified in Theorem 2.6 would produce exactly such a distinguisher.","tokens_in":63408,"feed_emoji":"📊","tokens_out":15706,"duration_ms":154187,"temperature":0.7,"pith_summary":"The paper sets out to prove that a single average-case hardness assumption, a partition-constrained planted-clique conjecture, forces strong sample-complexity lower bounds in three statistical problems: robust sparse mean estimation, semirandom community recovery, and general sparse-mixture detection. The common pattern is a $k$-to-$k^2$ gap: information-theoretic sample counts scale like $k$ while the paper derives computational barriers at $k^2$ (with auxiliary $\\epsilon$ and signal-to-noise factors in the robust and semirandom settings). All three lower bounds pass through a new intermediate detection problem, imbalanced sparse Gaussian mixtures, and are carried by total-variation reductions that turn any polynomial-time solver of a target problem into a polynomial-time solver of the assumed-hard planted subgraph problem. If the conjectured hardness holds, this is the first average-case evidence that robustness moves computational thresholds and that the $k$-to-$k^2$ gap is shared by a broad universality class of sparse mixture problems.","feed_headline":"Robust mean estimation needs k^2 samples under planted-clique hardness","feed_subtitle":"A partition-aware planted clique conjecture forces tight sample barriers in robust and semirandom statistics.","key_machinery":"The central object is the imbalanced sparse Gaussian mixture (ISGM): a simple-vs-simple detection problem in which the planted hypothesis draws $n$ independent $d$-dimensional vectors from $\\mathrm{mix}_\\epsilon(\\mathcal{N}(\\mu 1_S, I_d), \\mathcal{N}(\\mu' 1_S, I_d))$ for a uniform $k$-subset $S$, with imbalance imposed by $\\epsilon\\mu'+(1-\\epsilon)\\mu=0$. The reduction from $k$-pds to ISGM first symmetrizes the graph, plants diagonal entries, and Gaussianizes the resulting Bernoulli submatrix, then rotates the Gaussianized matrix by $H_{r,t}$, a matrix determined by point-hyperplane incidences in $\\mathbb{F}_r^t$. $H_{r,t}$ has orthonormal rows, contains only two distinct values, and has roughly a $1/r$ fraction of negative entries in each column; these three properties convert one planted subgraph into the imbalanced mixture structure while preserving the independence of the noise. For the universality result, the paper introduces symmetric 3-ary rejection kernels, which accept a ternary input and output one of three target distributions, performing an algorithmic change of measure whose total variation error is controlled by two likelihood-ratio differences.","core_discovery":"On its own terms, the paper establishes three conditional statements. Under the $k$-partite planted clique/dense subgraph conjecture (a known partition of the vertices, with a hidden dense $k$-subgraph containing exactly one vertex from each part and $k=o(\\sqrt n)$), no randomized polynomial-time test can have asymptotic Type I+II error below 1 for: robust sparse mean estimation with $n=o(\\epsilon^3 k^2)$ samples at signal floor $\\tau=\\Omega(\\sqrt{\\epsilon}/(\\log n)^{1+c})$, tight when $\\epsilon$ is inverse polylogarithmic; semirandom single-community recovery for $k=\\Theta(n^\\beta)$, $\\beta\\in[1/2,1)$, with constant ambient edge density and signal-to-noise ratio $o(n/(k^2\\log n))$; and generalized sparse mixture detection for any triple of distributions in the universality class at $n=o(k^2)$. The reductions are approximate in total variation and run in randomized polynomial time, so any polynomial-time solver of these problems would be converted into a distinguisher for the conjecturally hard planted subgraph problem.","pith_inferences":["A converse route for attacking the partition-constrained planted clique conjecture: construct a polynomial-time estimator for robust sparse mean estimation with $n=o(k^2)$ samples, and the reduction in this paper converts it into a distinguisher for $k$-pds.","Because the universality conditions are stated per marginal, moving a new sparse mixture model into the hard class reduces to checking two likelihood-ratio concentration bounds; this suggests a reusable recipe for transferring hardness to future models without redoing the reduction.","The paper's tradeoff between sample exponent and achievable $\\ell_2$ accuracy points to a two-parameter phase diagram for robust sparse mean estimation: lowering the accuracy requirement does not remove the gap, it only weakens the sample lower bound.","Since all reductions work in total variation, composite hypotheses (Huber contamination, $\\epsilon$-corruption, and monotone semirandom adversaries) inherit the hardness; the results likely extend to further robust formulations."],"forward_implications":["The robust sparse mean lower bound survives even when the required $\\ell_2$ accuracy is raised to about $\\sqrt{\\epsilon}$, far above the minimax $O(\\epsilon)$; the $k$-to-$k^2$ barrier does not depend on demanding optimal accuracy.","For constant ambient edge density, a semirandom adversary shifts the detection threshold in planted dense subgraph up to the recovery threshold $n/k^2$, so the classical detection-recovery gap disappears under monotone corruption.","Any sparse mixture problem whose marginal likelihood ratios satisfy two flatness bounds inherits an $n=\\tilde{\\Omega}(k^2)$ computational barrier; sparse PCA in the spiked covariance model, balanced sparse Gaussian mixtures, and Bernoulli or exponential mixtures are named examples.","The reductions preserve simple-vs-simple hypothesis testing structure in total variation, so the lower bounds apply to any polynomial-time algorithm of any kind, not only to one restricted model."],"supporting_citations":[{"why":"Conjectured the $k$-to-$k^2$ sample gap in robust sparse mean estimation that Theorem 2.6 targets, and provided the efficient estimator at roughly $k^2$ samples that must be beaten.","marker":"[Li17]"},{"why":"Introduced the same conjecture independently and supplied the polynomial-time robust sparse mean estimator at $n=\\tilde{\\Theta}(k^2)$, the computational baseline for the lower bound.","marker":"[BDLS17]"},{"why":"Established the average-case reduction framework in total variation and stated the planted dense subgraph recovery conjecture used as the semirandom community recovery target.","marker":"[BBH18]"},{"why":"Supplied the To-Submatrix reduction, computable pairs, and multivariate rejection kernels that the paper's $k$-partite submatrix reduction and universality class build on.","marker":"[BBH19]"},{"why":"Provided the Gaussianize primitive converting planted Bernoulli submatrix problems into planted Gaussian submatrix problems, reused in all three reductions.","marker":"[BB19]"},{"why":"Gave statistical query lower bounds for robust sparse mean estimation and the imbalanced sparse Gaussian mixture instance that motivates ISGM.","marker":"[DKS17]"},{"why":"Established statistical query hardness for planted clique, which Section 8 extends essentially unchanged to the $k$-partite promise.","marker":"[FGR+13]"},{"why":"Showed polynomial-time convexified maximum-likelihood recovery at signal strength about $n/k^2$, the recovery threshold that the semirandom lower bound says is unavoidable.","marker":"[CX16]"}],"fun_headline_variants":["Plant-clique hardness forces robust mean to need k^2 samples","Semirandom adversaries shift detection to recovery threshold","Universality: k-to-k^2 gaps in sparse mixtures under hardness","Average-case reduction ties robust estimation to planted clique"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that no randomized polynomial-time algorithm can detect a dense hidden $k$-vertex subgraph ($k=o(\\sqrt n)$) in a random graph when the hidden subgraph is promised to meet each part of a known $k$-part partition exactly once, a premise the paper supports only through limited-model evidence.","fun_headline_variants_meta":{"raw":{"variants":["Plant-clique hardness forces robust mean to need k^2 samples","Semirandom adversaries shift detection to recovery threshold","Universality: k-to-k^2 gaps in sparse mixtures under hardness","Average-case reduction ties robust estimation to planted clique"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000283,"raw_usage":{"total_tokens":1746,"prompt_tokens":1097,"completion_tokens":649,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":713,"completion_tokens_details":{"reasoning_tokens":581}},"tokens_in":713,"tokens_out":649,"duration_ms":8232,"temperature":1.0,"reasoning_tokens":581,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:19:25.904967+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete way to refute the chain is to exhibit a randomized polynomial-time test that distinguishes $G(n,1/2)$ from the $k$-partite planted clique for some sequence with $k=o(\\sqrt n)$; through the paper's own reductions, such a test would also solve all three target problems, and conversely a polynomial-time robust sparse mean estimator with $n=o(k^2)$ samples at the signal level specified in Theorem 2.6 would produce exactly such a distinguisher.","supporting_citations":[],"review_version":1}