Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries

Guy Bresler; Matthew Brennan

REVIEW 2 major objections 4 minor 1 cited by

Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 1908.06130 v2 pith:VTZEEO5W submitted 2019-08-08 cs.CC cs.LGmath.PRmath.STstat.MLstat.TH

Matthew Brennan , Guy Bresler This is my paper · ORCID

classification cs.CCcs.LGmath.PRmath.STstat.MLstat.TH MSC 68Q17

keywords average-casereductionsplantedcliqueconjecturestatistical-computationalgaprobustsparsemeanestimationsemirandomadversarydensesubgraphmixturesk-to-k^2gaps

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Dear colleague,

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

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

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

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

Referee Report

2 major / 4 minor

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.

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 (2)

[§7.3, Definition 7.4, Corollary 7.7] 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.
[§7.3 and Theorem 7.6] 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.

minor comments (4)

[§1.1 and §8] 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.
[Theorem 6.3 and Corollary 6.4] 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.
[Appendix A, proof of Proposition 8.3] 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.
[Figure 2, Step 5] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bounds are conditional reductions from an explicitly assumed k-partite planted-clique conjecture, not from the target problems.

full rationale

Every claimed lower bound (Theorems 2.6, 2.8, and 2.9) starts from the explicitly labeled k-pc/k-pds conjecture (Conjecture 2.5), constructs the intermediate ISGM problem, and then reduces to the target problem through total-variation maps (Lemmas 4.8, 4.11, 7.5). The target distributions are never assumed hard; instead a hypothetical solver for the target is compositionally converted into a solver for k-pds, which is the standard direction for hardness reductions. Section 8 is explicitly described as evidence for k-pc, and its low-degree/SQ arguments are adapted from [Hop18] and [FGR+13]; the main theorems do not rely on this evidence. The cited prior-work lemmas (Graph-Clone, Gaussianize, rejection kernels, and the total-variation lemma) are reused with stated assumptions and do not smuggle in the target lower bounds. The universality conditions in Definition 7.4 are assumptions on likelihood ratios, not consequences of the target problem's hardness; the examples are checked into the class rather than fitted from data. We therefore find no step in which a prediction reduces by construction to its inputs. The o(n^{-3d-1}) tail verification in Corollary 7.7 may raise a correctness/scope concern, but it is not a circularity issue.

Assumptions & free parameters 1 free parameters · 2 assumptions · 1 invented entities

The central claim is a conditional lower bound. Its only factual input from outside mathematics is the k-pc/k-pds conjecture. The reduction machinery either is proved in this paper or imported from the authors' prior work with cited proofs. No data are used, and no continuous constants are fitted to data.

free parameters (1)

slow-growing function w(n), also denoted w(N) = arbitrary omega(1), chosen after other parameters
Introduced in Theorems 4.2, 5.1, 6.3, and 7.6 to control total variation terms such as O(w^{-1} + k^2/(wN)) and to set N = Theta(w k^2). It is not fitted to data, but it is a hand-chosen asymptotic parameter of the reductions.

assumptions (2)

ad hoc to paper k-partite planted clique/dense subgraph conjecture (Conjecture 2.5): no randomized polynomial-time algorithm detects k-pc or k-pds for k=o(sqrt N) with fixed edge densities 0<q<p<=1.
The paper introduces the k-partite promise variant and assumes its hardness in all main theorems. Section 8 only gives low-degree and SQ evidence, not a proof, so the conjecture is a load-bearing, unproved premise.
domain assumption Randomized polynomial-time algorithms may sample N(0,1), Bern(p), and likelihood ratios exactly as oracles.
The reduction algorithms are stated under this idealization in Section 3.1. It is standard in average-case complexity, but technically an extra oracle assumption.

invented entities (1)

Imbalanced Sparse Gaussian Mixtures (ISGM) problem
purpose: Intermediate simple-versus-simple detection problem, Definition 4.1, through which k-pds is mapped to robust sparse mean estimation, semirandom community recovery, and general sparse mixtures.
ISGM is a constructed reduction target, not an empirically observed distribution. It has no falsifiable handle outside the paper, but it is a mathematical tool rather than an explanatory entity.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries." pith.science (2026). https://pith.science/paper/VTZEEO5W

@misc{pith2026190806130,
  author       = {Pith},
  title        = {Pith review of: Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VTZEEO5W}},
  note         = {Machine review of arXiv:1908.06130}
}

abstract

This paper develops several average-case reduction techniques to show new hardness results for three central high-dimensional statistics problems, implying a statistical-computational gap induced by robustness, a detection-recovery gap and a universality principle for these gaps. A main feature of our approach is to map to these problems via a common intermediate problem that we introduce, which we call Imbalanced Sparse Gaussian Mixtures. We assume the planted clique conjecture for a version of the planted clique problem where the position of the planted clique is mildly constrained, and from this obtain the following computational lower bounds: (1) a $k$-to-$k^2$ statistical-computational gap for robust sparse mean estimation, providing the first average-case evidence for a conjecture of Li (2017) and Balakrishnan et al. (2017); (2) a tight lower bound for semirandom planted dense subgraph, which shows that a semirandom adversary shifts the detection threshold in planted dense subgraph to the conjectured recovery threshold; and (3) a universality principle for $k$-to-$k^2$ gaps in a broad class of sparse mixture problems that includes many natural formulations such as the spiked covariance model. Our main approach is to introduce several average-case techniques to produce structured and Gaussianized versions of an input graph problem, and then to rotate these high-dimensional Gaussians by matrices carefully constructed from hyperplanes in $\mathbb{F}_r^t$. For our universality result, we introduce a new method to perform an algorithmic change of measure tailored to sparse mixtures. We also provide evidence that the mild promise in our variant of planted clique does not change the complexity of the problem.

Figures

Figures reproduced from arXiv: 1908.06130 by the authors.

**Figure 1.** Prior computational and statistical barriers in the detection and recovery of a single hidden community from the pc conjecture [HWX15, BBH18, BBH19]. The axes are parameterized by α and β where snr = (p−q) 2 q(1−q) = Θ( ˜ n −α) and k = Θ( ˜ n β ). The red region is conjectured to be computationally hard but no pc reductions showing this hardness are known. This is a formulation of robust sparse mean estimation in Hu… view at source ↗

**Figure 2.** Reduction from k-partite planted dense subgraph to exactly imbalanced sparse Gaussian mixtures. 17 [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗

**Figure 3.** Subroutine Graph-Clone for producing independent samples from planted graph problems from [BBH19]. Lemma 4.4 (Gaussian Rejection Kernels – Lemma 5.4 in [BBH18]). Let n be a parameter and suppose that p = p(n) and q = q(n) satisfy that 0 < q < p ≤ 1, min(q, 1 − q) = Ω(1) and p − q ≥ n −O(1). Let δ = min n log p q , log 1−q 1−p o. Suppose that µ = µ(n) ∈ (0, 1) satisfies that µ ≤ δ 2 p 6 log n + 2 log(p − q)−1 … view at source ↗

Figures from the paper (6 more)

**Figure 4.** Figure 4: Gaussian instantiation of the rejection kernel algorithm from [BBH18] and the reduction Gaussianize for mapping from Bernoulli to Gaussian planted submatrix problems from [BB19]. for all subsets S ⊆ [m] and T ⊆ [n] where ◦ denotes the Hadamard product between two matri…

**Figure 5.** Figure 5: Subroutine To-k-Partite-Submatrix for mapping from an instance of k-partite planted dense subgraph to a k-partite Bernoulli submatrix problem. for To-k-Partite-Submatrix. We remark that the total variation upper bound in this lemma is tight in the following sense. When…

**Figure 6.** Figure 6: Sample cloning subroutine in the reduction from a planted dense subgraph instance to robust sparse mean estimation. We remark that in intermediate parameter regimes where ǫ = (log n) −ω(1) is not yet polynomially small in n, such as ǫ = e −Θ(√ log n) , our result esse…

**Figure 7.** Figure 7: Reduction from k-partite planted dense subgraph to semirandom community recovery. 36 [PITH_FULL_IMAGE:figures/full_fig_p036_7.png]

**Figure 8.** Figure 8: 3-ary symmetric rejection kernel algorithm. 7.1 Symmetric 3-ary Rejection Kernels and Truncating Gaussians In this section, we introduce symmetric 3-ary rejection kernels, which will be the key gadget in our reduction showing universality of lower bounds for learning s…

**Figure 9.** Figure 9: Reduction from k-partite planted dense subgraph to general learning sparse mixtures. Lemma 7.5 (isgm to glsm). Suppose that τ > 0 is a fixed constant and µ = Ω(1/ √ wk log n) for a sufficiently slow-growing function w. If (D, Q, {Pν }ν∈R) ∈ uc(n, k, d), then dTV (A2 (i…

Discussion (0). Continue with ORCID 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

On optimal distinguishers for Planted Clique
cs.CC 2025-05 conditional novelty 8.0 of 10

Under the Planted Clique Hypothesis, the optimal efficient distinguishing advantage for Planted Clique is (1+o(1))*k^2/(sqrt(pi)*n), and there exist planted distributions that are much harder to detect than the usual one.

Reference graph

Works this paper leans on

27 extracted references · 14 canonical work pages · cited by 1 Pith paper

[5]

A nearly tight sum-of-squares lower bound for the planted clique problem

[BHK+16] Boaz Barak, Samuel B Hopkins, Jonathan Kelner, Pravesh K othari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 428–437. IEEE,

work page 2016
[9]

Tony Cai and Yihong Wu

[CW18] T. Tony Cai and Yihong Wu. Statistical and computatio nal limits for sparse matrix detection. arXiv preprint arXiv:1801.00518 ,

arXiv
[10]

Robust estimators in high dimensions wit hout the computational intractability

[DKK+16] Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions wit hout the computational intractability. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 655–664. IEEE,

work page 2016
[11]

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

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

work page 2017
[14]

The landscape of the p lanted clique problem: Dense subgraphs and the overlap gap property

[GZ19] David Gamarnik and Ilias Zadik. The landscape of the p lanted clique problem: Dense subgraphs and the overlap gap property. arXiv preprint arXiv:1904.07174 ,

arXiv 1904
[15]

How hard is robust mean e stimation? arXiv preprint arXiv:1903.07870,

[HL19] Samuel B Hopkins and Jerry Li. How hard is robust mean e stimation? arXiv preprint arXiv:1903.07870,

arXiv 1903
[16]

Eﬃcient bayesian estimation from few samples: community detection and related problems

[HS17] Samuel B Hopkins and David Steurer. Eﬃcient bayesian estimation from few samples: community detection and related problems. In Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on , pages 379–390. IEEE,

work page 2017
[18]

How to play unique games against a semi-random adversary: Study of semi-rando m models of unique games

[KMM11] Alexandra Kolla, Konstantin Makarychev, and Yury Makarychev. How to play unique games against a semi-random adversary: Study of semi-rando m models of unique games. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Sci ence, pages 443–452. IEEE,

work page 2011

Show all 27 references

[19]

Sum of squares lower bounds for refuting any csp

[KMOW17] Pravesh K Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer. Sum of squares lower bounds for refuting any csp. arXiv preprint arXiv:1701.04521 ,

arXiv
[20]

Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering

[LDBB+16] Thibault Lesieur, Caterina De Bacco, Jess Banks, Floren t Krzakala, Cris Moore, and Lenka Zdeborov´ a. Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering. In Communication, Control, and Computing (Allerton), 2016 54th Annual Alle...

2016
[23]

Agnosti c estimation of mean and covariance

61 [LRV16] Kevin A Lai, Anup B Rao, and Santosh Vempala. Agnosti c estimation of mean and covariance. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 665–674. IEEE,

2016
[25]

Mathematics and the picturing of data

62 [Tuk75] John W Tukey. Mathematics and the picturing of data. In Proceedings of the In- ternational Congress of Mathematicians, Vancouver, 1975 , volume 2, pages 523–531,

1975
[26]

Detection a nd feature selection in sparse mixture models

[VAC17] Nicolas Verzelen and Ery Arias-Castro. Detection a nd feature selection in sparse mixture models. The Annals of Statistics , 45(5):1920–1950,

1920
[1977]

Eﬃc ient algorithms for outlier- robust regression

[KKM18] Adam Klivans, Pravesh K Kothari, and Raghu Meka. Eﬃc ient algorithms for outlier- robust regression. arXiv preprint arXiv:1803.03241 ,

arXiv
[1986]

Robust sparse estimation tasks in high dime nsions

[Li17] Jerry Li. Robust sparse estimation tasks in high dime nsions. arXiv preprint arXiv:1702.05860,

arXiv
[1992]

Mmse of probabilistic low- rank matrix estimation: Universality with respect to the ou tput channel

[LKZ15] Thibault Lesieur, Florent Krzakala, and Lenka Zdeb orov´ a. Mmse of probabilistic low- rank matrix estimation: Universality with respect to the ou tput channel. In Commu- nication, Control, and Computing (Allerton), 2015 53rd Annua l Allerton Conference on, pages 680–6...

2015
[1997]

Tight lower b ounds for planted clique in the degree-4 sos program

[RS15] Prasad Raghavendra and Tselil Schramm. Tight lower b ounds for planted clique in the degree-4 sos program. arXiv preprint arXiv:1507.05136 ,

arXiv
[2001]

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

[FLWY18] Jianqing Fan, Han Liu, Zhaoran Wang, and Zhuoran Ya ng. Curse of heterogeneity: Computational barriers in sparse mixture models and phase r etrieval. arXiv preprint arXiv:1808.06996,

arXiv
[2010]

Sparse cc a: Adaptive estimation and computational barriers

[GMZ17] Chao Gao, Zongming Ma, and Harrison H Zhou. Sparse cc a: Adaptive estimation and computational barriers. The Annals of Statistics , 45(5):2074–2101,
[2011]

Optimal average-ca se reductions to sparse pca: From weak assumptions to strong hardness

[BB19] Matthew Brennan and Guy Bresler. Optimal average-ca se reductions to sparse pca: From weak assumptions to strong hardness. arXiv preprint arXiv:1902.07380 ,

1902 arXiv
[2013]

Computational hardness of certifying bounds on constrained pca problems

[BKW19] Afonso S Bandeira, Dmitriy Kunisky, and Alexander S Wein. Computational hardness of certifying bounds on constrained pca problems. arXiv preprint arXiv:1902.07324 ,

1902 arXiv
[2014]

Algorit hmic barriers from phase transi- tions

[ACO08] Dimitris Achlioptas and Amin Coja-Oghlan. Algorit hmic barriers from phase transi- tions. In 2008 49th Annual IEEE Symposium on Foundations of Computer Sci ence, pages 793–802. IEEE,

2008
[2015]

Co mputational and statisti- cal boundaries for submatrix localization in a large noisy m atrix

[CLR15] Tony Cai, Tengyuan Liang, and Alexander Rakhlin. Co mputational and statisti- cal boundaries for submatrix localization in a large noisy m atrix. arXiv preprint arXiv:1502.01988,

arXiv
[2016]

Statistical and com- putational trade-oﬀs in estimation of sparse principal comp onents

[WBS16] Tengyao Wang, Quentin Berthet, and Richard J Samwor th. Statistical and com- putational trade-oﬀs in estimation of sparse principal comp onents. The Annals of Statistics, 44(5):1896–1930,

1930
[2017]

Algorithmic thresholds for tensor pca

[BGJ18] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagann ath. Algorithmic thresholds for tensor pca. arXiv preprint arXiv:1808.00921 ,

arXiv
[2018]

U niversality of computational lower bounds for submatrix detection

[BBH19] Matthew Brennan, Guy Bresler, and Wasim Huleihel. U niversality of computational lower bounds for submatrix detection. arXiv preprint arXiv:1902.06916 ,

1902 arXiv
[2019]

The landscape of the spiked tensor model

[BMMN17] Gerard Ben Arous, Song Mei, Andrea Montanari, and M ihai Nica. The landscape of the spiked tensor model. arXiv preprint arXiv:1711.05424 ,

arXiv

Pith tools

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

[1] [5]

A nearly tight sum-of-squares lower bound for the planted clique problem

[BHK+16] Boaz Barak, Samuel B Hopkins, Jonathan Kelner, Pravesh K othari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 428–437. IEEE,

work page 2016

[2] [9]

Tony Cai and Yihong Wu

[CW18] T. Tony Cai and Yihong Wu. Statistical and computatio nal limits for sparse matrix detection. arXiv preprint arXiv:1801.00518 ,

arXiv

[3] [10]

Robust estimators in high dimensions wit hout the computational intractability

[DKK+16] Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions wit hout the computational intractability. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 655–664. IEEE,

work page 2016

[4] [11]

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

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

work page 2017

[5] [14]

The landscape of the p lanted clique problem: Dense subgraphs and the overlap gap property

[GZ19] David Gamarnik and Ilias Zadik. The landscape of the p lanted clique problem: Dense subgraphs and the overlap gap property. arXiv preprint arXiv:1904.07174 ,

arXiv 1904

[6] [15]

How hard is robust mean e stimation? arXiv preprint arXiv:1903.07870,

[HL19] Samuel B Hopkins and Jerry Li. How hard is robust mean e stimation? arXiv preprint arXiv:1903.07870,

arXiv 1903

[7] [16]

Eﬃcient bayesian estimation from few samples: community detection and related problems

[HS17] Samuel B Hopkins and David Steurer. Eﬃcient bayesian estimation from few samples: community detection and related problems. In Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on , pages 379–390. IEEE,

work page 2017

[8] [18]

How to play unique games against a semi-random adversary: Study of semi-rando m models of unique games

[KMM11] Alexandra Kolla, Konstantin Makarychev, and Yury Makarychev. How to play unique games against a semi-random adversary: Study of semi-rando m models of unique games. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Sci ence, pages 443–452. IEEE,

work page 2011