Pith. sign in

REVIEW 2 major objections 5 minor 47 references

A Smooth Computational Transition in Tensor PCA

T0 review · 2 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read Counting weighted 2-regular hypergraphs solves tensor PCA at SNR λ n^{-p/4} in time n^{C(λ)}.

desk verdict A genuinely new algorithmic result for tensor PCA, but the main theorem currently leans on an unproved non-asymptotic enumeration bound. read the letter →

arxiv 2509.09904 v1 pith:YFPUNFLI submitted 2025-09-12 math.ST cs.DSmath.PRstat.MLstat.TH

Zhangsong Li This is my paper · ORCID
classification math.STcs.DSmath.PRstat.MLstat.TH MSC 62H2562F0305C6568Q25
keywords tensorPCAspikedmodelhypergraphcounting2-regularhypergraphscolorcodingdetectionandrecoverycomputational-statisticalgapsmoothcomputationaltransition
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 show that the computational threshold in tensor PCA is not a sharp wall but a smooth slope: as the signal-to-noise ratio decreases toward the conjectured limit λ n^{-p/4}, the running time of a polynomial-time algorithm grows continuously. The vehicle is a family of statistics built from counting weighted 2-regular hypergraphs of growing size. For any non-vanishing constant λ, the paper proves that these statistics achieve strong detection and weak recovery, while the counting can be implemented by hypergraph color coding in n^{C(λ)+o(1)} time. This confirms a predicted smooth tradeoff between statistical power and computational cost, and improves a poly-logarithmic factor over earlier polynomial-time algorithms.

What carries the argument

The central objects are the families H(m,p,ℓ) and J(m,p,ℓ) of unlabeled p-uniform hypergraphs assembled from ℓ 'blocks' U_i, where each block is a connected hypergraph on mp+1 vertices with 2m edges, every vertex of degree 1 or 2 (exactly two leaves in each block), and the blocks are glued cyclically (for H) or in a path (for J) by identifying leaves. The statistic f_H(Y) (detection) and the pairwise scores Φ^J_{i,j}(Y) (recovery) are normalized weighted subhypergraph counts. The key mechanism is that for these families the signal contributes to the mean as λ^{2mℓ} n^{pmℓ/2} √β, while the variance is suppressed because overlaps between distinct hypergraphs contribute only through configurati

What would settle it

Compute, for small m and p=3, the exact number of connected 2-regular hypergraphs on mp+1 vertices with 2m edges (or the sum β_U) and compare to the claimed lower bound; a counterexample to the enumeration bound at some m would invalidate the key variance estimate. Alternatively, simulate the detection statistic at SNR λ n^{-p/4} for a fixed small λ and check whether the empirical mean-to-standard-deviation ratio grows as predicted when m is chosen per the paper's condition.

Watch

Extended reading notes

Core claim

The central claim is that, for a fixed order p≥3 and SNR κ = λ n^{-p/4} with λ = Ω(1), there are explicit algorithms that decide whether the observed tensor contains a planted spike and recover the spike to constant correlation, each running in time n^{C+o(1)} with C = C(λ). The statistics are subhypergraph counts: for detection, count all connected 2-regular p-uniform hypergraphs on K = mpℓ vertices, weighting each occurrence by the product of the corresponding tensor entries; for recovery, count the same hypergraphs with two distinguished leaves to form a pairwise score that tracks x_i x_j. The paper shows via second-moment analysis that, under the SNR scaling, the signal dominates the flu

Load-bearing premise

The lower bounds on the number of admissible hypergraph blocks (β_U, β_H, β_J) rely on a sparse-hypergraph enumeration bound for degree sequences with maximum degree 2, whose claimed uniformity is invoked from an external result without proof; if that bound fails, the variance suppression collapses and the detection and recovery guarantees do not follow.

Editorial extensions

If this is right

  • For every constant SNR scaling coefficient λ, there is a polynomial-time algorithm for detection and a polynomial-time algorithm for weak recovery at κ = λ n^{-p/4}.
  • The exponent C(λ) grows like λ^{-4p/(p-2)} as λ→0, so there is no sharp polynomial-time threshold; weaker signals require higher but still constant polynomial powers.
  • The algorithm's success holds uniformly for all λ = Ω(1), including arbitrarily small constants, at the critical scaling.
  • In the regime λ = ω(1), the recovery guarantee can be upgraded to strong recovery.
  • The run time improves by a poly-logarithmic factor over earlier polynomial-time algorithms at the same SNR.

Reading between the lines

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

  • The construction suggests an interpolation between detection and recovery: the same block decomposition with different gluing yields both statistics, so one could design intermediate tasks (e.g., partial recovery with tunable fraction) with a smooth cost-power curve.
  • Because the statistics are low-degree polynomials whose degree nearly matches the known low-degree lower bound, the result can be read as the first algorithmic realization of the low-degree prediction for this problem, giving evidence that the low-degree framework captures the true computational threshold in this model.
  • The dependence on λ^{-4p/(p-2)} matches the predicted degree threshold; one could test sharpness by showing that no polynomial-time algorithm with a smaller exponent can succeed, or by constructing a matching lower bound at the level of the counting statistics.
  • A natural next step is to see whether the same weighted-hypergraph counting approach extends to other spiked tensor models with non-Gaussian noise or other priors, where the variance-covariance structure of subhypergraph counts may differ.
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 / 5 minor

Summary. This paper proposes efficient algorithms for order-p tensor PCA (p≥3 fixed) at SNR κ=λ n^{-p/4} with λ=Ω(1). The detection statistic is a normalized sum of weighted counts of a carefully chosen family H of connected 2-regular p-uniform hypergraphs; the recovery statistic uses a family J with two leaves. The paper proves second-moment bounds showing that the detection statistic has mean ω(1) and variance o(mean^2) under the spike and unit second moment under noise, and that the recovery statistic has conditional mean x_i x_j and MSE O(δ^2). It then shows these statistics can be approximated in polynomial time n^{C+o(1)} via hypergraph color coding, yielding strong detection and weak recovery. Formal results appear as Theorems 2.6/2.7 (detection) and 2.11/2.12 (recovery) under conditions (2.4) and (2.11), and the paper argues this confirms a smooth computational transition conjecture of KWB22.

Significance. If the technical gaps are repaired, this is a substantial contribution to the tensor PCA literature: it gives algorithms that rigorously achieve a smooth tradeoff between runtime exponent and SNR, matching the low-degree prediction, and it improves the previous polylogarithmic overhead of SOS/Kikuchi approaches. The statistics are explicit polynomial functionals of the data with no fitted parameters, and the analysis includes detailed second-moment and variance estimates as well as nontrivial hypergraph color-coding algorithms. The paper connects subhypergraph counting, low-degree polynomials, and statistical-computational gaps, and is likely to stimulate further work.

major comments (2)
  1. [Appendix B.1, Lemmas 2.2 and A.2] The lower bound on β_U is proved by applying the asymptotic enumeration Lemma A.2 to the class A_{2m,mp+1}, i.e., N=mp+1 and M=2m. In the main theorems, m is a fixed constant (see (2.4)–(2.6)), so N,M do not tend to infinity. Lemma A.2 is stated under N,M→∞; its 'in particular' d_max=2 clause is a corollary of that asymptotic statement, not a finite-N/M bound with an absolute constant R. The error term O(d_max^3/(pM)) is O(1/m), not small for fixed m. Since β_U feeds into β_H (Lemma 2.4) and β_J (Lemma 2.9), and conditions (2.4), (2.11) require λ^{4m}β_U and λ^{4m}β_J large, Theorems 2.6, 2.7, 2.11, 2.12 are not justified as written. A finite-N/M version of Lemma A.2 for d_max=2, or a direct proof of Lemma 2.2, is needed.
  2. [§2.1, before (2.6)] The displayed standard-estimates chain λ^{4m}(2pm)!/((p!)^m(mp)!(2m)!) < [λ^4(2pm)^{2p}/(p^p(pm)^p(2m))]^{2m} < [λ^4 m^{p-2}/p^{2p}]^{2m} is incorrect. The middle quantity simplifies to Θ(λ^4 m^{p-1}) (the p's cancel), not to λ^4 m^{p-2}; hence the final bound is not m^{p-2} but m^{p-1} inside the 2m power. This invalidates the sufficiency claim for the m-choice in (2.6) and the stated form of C(λ) in Remark 4.4. The existence of some constant m for each fixed λ may still follow from the corrected estimate and (2.4), but the displayed implication is false.
minor comments (5)
  1. [§3.3, around (3.25)] In the statement of (3.25), 'Part V I' should read 'Part IV'.
  2. [§4.2, (4.6)] The sentence 'For any p-uniform unlabeled hypergraph [J]∈J with mpℓ vertices' should say 'with mpℓ+1 vertices' (or 'colored with mpℓ+1 colors'), since Definition 2.8 gives |V(J)|=mpℓ+1.
  3. [Algorithms 4 and 6, Step 3] In Algorithm 6, Step 3 refers to 'Definition 2.3' but the recovery family is defined in Definition 2.8; the same confusion appears in the proof of Proposition 4.7.
  4. [Proof of Lemma 3.3] The reference 'Lemma A.1,(1)' for the count of embeddings S∼=H should be 'Lemma A.1,(2)'.
  5. [Proof of Proposition 4.3] The notation in the runtime bound for listing hypergraph sequences is garbled: O(((mp+1)^p)^{2m})^ℓ) should be written more carefully; with ℓ=o(log n/log log n) the step is n^{o(1)}, but the displayed expression is confusing.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the detection/recovery statistics are explicit polynomial statistics with no fitted parameters, and all load-bearing cited results are external to the present paper.

full rationale

The paper's central claims (Theorems 2.6, 2.7, 2.11, 2.12) are derived by direct second-moment analysis of explicitly defined polynomial statistics f_H and Phi^J_{i,j} over subhypergraph counts. The parameters m and ell are chosen to satisfy explicit sufficient conditions (2.4) and (2.11); they are not fitted to the conclusions, and the thresholds tau are arbitrary constants scaled by E_P[f_H], not tuned to the data. The statistical estimates rest on the external asymptotic enumeration result of Blinovsky-Greenhill (Lemma A.2), on color coding (AYX95, AR02, HS17, MWXY24, MWXY23), and on standard hypergraph counting lemmas proved in the appendix; none of these are self-citations or constructed to force the target theorem. The paper does cite two papers with overlapping authorship (DDL23+, CDGL24+), but only as examples in a literature list and as background for low-degree methods; they are not load-bearing for the present proofs. The motivational 'confirmation' of the smooth-transition conjecture from KWB22 is an external conjecture and is not used as a premise: the paper proves its own upper bounds. The only notable caveat, flagged in the appendix, is that Lemma A.2 is stated as an asymptotic result (N, M -> infinity) but is applied at fixed m in Lemma 2.2 via the 'in particular, d_max = 2' clause; this is a possible correctness gap in the uniformity of the constant R, not a circular reduction, and it does not make any claimed prediction equivalent to an input by construction. No fitted input is renamed as a prediction, no uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled in via a self-citation. Accordingly, the appropriate circularity score is 0.

Assumptions & free parameters 3 free parameters · 3 assumptions · 0 invented entities

The central claim rests on external enumeration bounds from [BG16], the model definition, and the color-coding framework. The free parameters m, ell, delta are analytical design choices, not fitted to data. No new physical entities or mediators are introduced.

free parameters (3)
  • m
    Block size parameter (number of hyperedge pairs per block). Chosen as Theta(lambda^{-4/(p-2)}) in (2.6)/(2.11) to satisfy the second-moment conditions. It is an algorithm design parameter determined by the SNR lambda, not fitted to data.
  • ell
    Number of blocks chained. Chosen as omega(1) and o(log n/log log n) for detection (Prop 2.5) and log n for recovery (Prop 2.10). It sets the polynomial degree and the color-coding repetition count t, and is a free design parameter.
  • delta
    Target recovery error and failure probability in (2.11) and Theorem 2.11. Chosen as an arbitrary small constant; the paper shows it can tend to 0 if lambda = omega(1).
assumptions (3)
  • standard math Asymptotic enumeration of p-uniform hypergraphs with given degree sequence (Lemma A.2, from Blinovsky-Greenhill [BG16])
    Used in Lemmas 2.2, 2.4, and B.1 to lower-bound the number of hypergraphs in U and H. The 'in particular' case with d_max=2 is imported without proof.
  • domain assumption Model assumptions: Rademacher prior for the planted vector, symmetrized i.i.d. standard Gaussian noise, SNR kappa = lambda n^{-p/4}
    The entire analysis is for this specific spiked tensor model; the result does not claim universality beyond this prior and noise structure.
  • standard math Color coding randomized approximation framework (Alon-Yuster-Zwick, Arvind-Raman, Hopkins-Steurer, Mao-Wu-Xu-Yu)
    Used in Section 4 to approximate the subhypergraph counts in polynomial time; the paper relies on the correctness of the color-coding method and its own implementation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Smooth Computational Transition in Tensor PCA." pith.science (2026). https://pith.science/paper/YFPUNFLI

@misc{pith2026250909904,
  author       = {Pith},
  title        = {Pith review of: A Smooth Computational Transition in Tensor PCA},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YFPUNFLI}},
  note         = {Machine review of arXiv:2509.09904}
}
abstract

We propose an efficient algorithm for tensor PCA based on counting a specific family of weighted hypergraphs. For the order-$p$ tensor PCA problem where $p \geq 3$ is a fixed integer, we show that when the signal-to-noise ratio is $\lambda n^{-\frac{p}{4}}$ where $\lambda=\Omega(1)$, our algorithm succeeds and runs in time $n^{C+o(1)}$ where $C=C(\lambda)$ is a constant depending on $\lambda$. This algorithm improves a poly-logarithmic factor compared to previous algorithms based on the Sum-of-Squares hierarchy \cite{HSS15} or based on the Kikuchi hierarchy in statistical physics \cite{WEM19}. Furthermore, our result shows a smooth tradeoff between the signal-to-noise ratio and the computational cost in this problem, thereby confirming a conjecture posed in \cite{KWB22}.

Figures

Figures reproduced from arXiv: 2509.09904 by the authors.

Figure 1
Figure 1. An unlabeled hypergraph in H(m, p, ℓ) with ℓ = 6 Proposition 2.5. Suppose p ≥ 3, m ≥ 1011R 3 , λ 4m(2pm)! 2 pm(p!)m(mp)!(2m)! > 10pmR and ω(1) = ℓ = o( log n log log n ). (2.4) Then we have EP [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. An unlabeled hypergraph in J (m, p, ℓ) with ℓ = 5 Then we have for p ≥ 3 [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 3 linked inside Pith

  1. [1]

    Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery

    Emmanuel Abbe and Colin Sandon. Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) , pages 670--688. IEEE, 2015

    2015

  2. [2]

    Proof of the achievability conjectures for the general stochastic block model

    Emmanuel Abbe and Colin Sandon. Proof of the achievability conjectures for the general stochastic block model. Communications on Pure and Applied Mathematics , 71(7):1334--1406, 2018

    2018

  3. [3]

    Cenk Sahinalp

    Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S. Cenk Sahinalp. Biomolecular network motif counting and discovery by color coding. Bioinformatics , 24(13):i241--i249, 2008

    2008

  4. [4]

    Color-coding

    Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM , 42(4):844--856, 1995

    1995

  5. [5]

    Approximation algorithms for some parameterized counting problems

    Vikraman Arvind and Venkatesh Raman. Approximation algorithms for some parameterized counting problems. In Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC) , pages 453--464. Springer, 2002

    2002

  6. [6]

    Bandeira, Giorgio Cipolloni, Dominik Schr o der, and Ramon van Handel

    Afonso S. Bandeira, Giorgio Cipolloni, Dominik Schr o der, and Ramon van Handel. Matrix concentration inequalities and free probability II. Two-sided bounds and applications. arXiv preprint, arXiv:2406.11453

    arXiv

  7. [7]

    Bandeira, Ahmed El Alaoui, Samuel B

    Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins, Tselil Schramm, Alexander S. Wein, and Ilias Zadik. The Franz-Parisi criterion and computational trade-offs in high dimensional statistics. In Advances in Neural Information Processing Systems (NIPS) , volume 35, pages 33831--33844. Curran Associates, Inc., 2022

    2022

  8. [8]

    Bandeira, Anastasia Kireeva, Antoine Maillard, and Almut R o dder

    Afonso S. Bandeira, Anastasia Kireeva, Antoine Maillard, and Almut R o dder. Randomstrasse101: Open problems of 2024. arXiv preprint, arXiv:2504.20539

    arXiv 2024

Show all 47 references
  1. [9]

    Bandeira, Dmitriy Kunisky, and Alexander S

    Afonso S. Bandeira, Dmitriy Kunisky, and Alexander S. Wein. Computational hardness of certifying bounds on constrained PCA problems. In 11th Innovations in Theoretical Computer Science Conference (ITCS) , pages 78:1--78:29. Schloss Dagstuhl-Leibniz-Zentrumf u r Informatik, 2020

    2020

  2. [10]

    Contiguity and non-reconstruction results for planted partition models: the dense case

    Debapratim Banerjee. Contiguity and non-reconstruction results for planted partition models: the dense case. Electronic Journal of Probability , 23:1--28, 2018

    2018

  3. [11]

    Optimal hypothesis testing for stochastic block models with growing degrees

    Debapratim Banerjee and Zongming Ma. Optimal hypothesis testing for stochastic block models with growing degrees. arXiv preprint, arXiv:1705.05305

    arXiv

  4. [12]

    Hopkins, Jonathan Kelner, Pravesh K

    Boaz Barak, Samuel B. Hopkins, Jonathan Kelner, Pravesh K. Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. SIAM Journal on Computing , 48(2):687--735, 2019

    2019

  5. [13]

    Algorithmic threshold for tensor PCA

    G\'erard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Algorithmic threshold for tensor PCA. Annals of Probability , 48(4):2052--2087, 2020

  6. [14]

    Asymptotic enumeration of sparse uniform hypergraphs with given degrees

    Vladimir Blinovsky and Catherine Greenhill. Asymptotic enumeration of sparse uniform hypergraphs with given degrees. European Journal of Combinatorics , 51:287--296, 2016

    2016

  7. [15]

    Non-backtracking spectrum of random graphs: Community detection and non-regular Ramanujan graphs

    Charles Bordenave, Marc Lelarge, and Laurent Massouli\'e. Non-backtracking spectrum of random graphs: Community detection and non-regular Ramanujan graphs. In Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1347--1357. IEEE, 2015

    2015

  8. [16]

    Reducibility and statistical-computational gaps from secret leakage

    Matthew Brennan and Guy Bresler. Reducibility and statistical-computational gaps from secret leakage. In Proceedings of the 33rd Conference on Learning Theory (COLT) , pages 648--847. PMLR, 2020

    2020

  9. [17]

    The algorithmic phase transition of random k -SAT for low degree polynomials

    Guy Bresler and Brice Huang. The algorithmic phase transition of random k -SAT for low degree polynomials. In Proceedings of the IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 298--309. IEEE, 2022

    2022

  10. [18]

    Testing for high-dimensional geometry in random graphs

    S\'ebastien Bubeck, Jian Ding, Ronen Eldan, and Mikl\'os Z R\'acz. Testing for high-dimensional geometry in random graphs. Random Structures and Algorithms , 49(3):503--532, 2016

    2016

  11. [19]

    A computational transition for detecting correlated stochastic block models by low-degree polynomials

    Guanyi Chen, Jian Ding, Shuyang Gong, and Zhangsong Li. A computational transition for detecting correlated stochastic block models by low-degree polynomials. to appear in Annals of Statistics

  12. [20]

    Abhishek Dhawan, Cheng Mao, and Alexander S. Wein. Detection of dense subhypergraphs by low-degree polynomials. to appear in Random Structures and Algorithms

  13. [21]

    Low-degree hardness of detection for correlated Graphs

    Jian Ding, Hang Du, and Zhangsong Li. Low-degree hardness of detection for correlated Graphs. to appear in Annals of Statistics

  14. [22]

    Wein, and Afonso S

    Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, and Afonso S. Bandeira. Subexponential-time algorithms for sparse PCA. Foundations of Computational Mathematics , 22(1):1--50, 2022

    2022

  15. [23]

    Hypertree decompositions and tractable queries

    Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree decompositions and tractable queries. Journal of Computer and System Sciences , 64(3):579--627, 2002

    2002

  16. [24]

    David Gamarnik, Aukosh Jagannath, and Alexander S. Wein. Hardness of random optimization problems for Boolean circuits, low-degree polynomials, and Langevin dynamics. SIAM Journal on Computing , 53(1):1--46, 2024

    2024

  17. [25]

    Samuel B. Hopkins. Statistical inference and the sum of squares method. PhD thesis, Cornell University, 2018

    2018

  18. [26]

    Hopkins, Pravesh K

    Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer. The power of sum-of-squares for detecting hidden structures. In Proceedings of the IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 720--73...

    2017

  19. [27]

    Hopkins, Jonathan Shi, and David Steurer

    Samuel B. Hopkins, Jonathan Shi, and David Steurer. Tensor principal component analysis via sum-of-square proofs. In Proceedings of the 28th Conference on Learning Theory (COLT) , pages 956--1006. PMLR, 2015

    2015

  20. [28]

    Hopkins and David Steurer

    Samuel B. Hopkins and David Steurer. Efficient Bayesian estimation from few samples: community detection and related problems. In Proceedings of the IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 379--390. IEEE, 2017

    2017

  21. [29]

    Dmitriy Kunisky, Cristopher Moore, and Alexander S. Wein. Tensor cumulants for statistical inference on invariant distributions. In Proceedings of the IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1007--1026. IEEE, 2024

    2024

  22. [30]

    Wein, and Afonso S

    Dmitriy Kunisky, Alexander S. Wein, and Afonso S. Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. In Mathematical Analysis, its Applications and Computation: ISAAC 2019 , pages 1--50. Springer, 2022

    2019

  23. [31]

    Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs

    Dmitriy Kunisky and Xifan Yu. Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs. In Proceedings of the IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1621--1633. IEEE, 2024

    2024

  24. [32]

    Statistical and computational phase transitions in spiked tensor estimation

    Thibault Lesieur, L\'eo Miolane, Marc Lelarge, Florent Krzakala, and Lenka Zdeborov\'a. Statistical and computational phase transitions in spiked tensor estimation. In IEEE International Symposium on Information Theory (ISIT) , pages 511--515. IEEE, 2017

    2017

  25. [33]

    Cheng Mao and Alexander S. Wein. Optimal spectral recovery of a planted vector in a subspace. Bernoulli , 31(2):1114--1139, 2025

    2025

  26. [34]

    Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H. Yu. Testing network correlation efficiently via counting trees. Annals of Statistics , 52(6):2483--2505, 2024

    2024

  27. [35]

    Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H. Yu. Random graph matching at Otter's threshold via counting chandeliers. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC) , pages 1345--1356. ACM, 2023

    2023

  28. [36]

    Community detection thresholds and the weak Ramanujan property

    Laurent Massouli\'e. Community detection thresholds and the weak Ramanujan property. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC) , pages 694--703. ACM, 2014

    2014

  29. [37]

    Network motifs: simple building blocks of complex networks

    Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: simple building blocks of complex networks. Science , 298(5594):824--827, 2002

    2002

  30. [38]

    Phase transitions in spiked matrix estimation: information-theoretic analysis

    L\'eo Miolane. Phase transitions in spiked matrix estimation: information-theoretic analysis. arXiv preprint arXiv:1806.04343

    arXiv

  31. [39]

    Reconstruction and estimation in the planted partition model

    Elchanan Mossel, Joe Neeman, and Allan Sly. Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields , 162(3):431--461, 2015

    2015

  32. [40]

    A proof of the block model threshold conjecture

    Elchanan Mossel, Joe Neeman, and Allan Sly. A proof of the block model threshold conjecture. Combinatorica , 38(3):665--708, 2018

    2018

  33. [41]

    Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs

    Elchanan Mossel, Allan Sly, and Youngtak Sohn. Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC) , pages 2062--2073, 2025

  34. [42]

    Silva, David Aparicio, and Fernando Silva

    Pedro Ribeiro, Pedro Paredes, Miguel E.P. Silva, David Aparicio, and Fernando Silva. A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets. ACM Computing Surveys , 54(2):1--36, 2021

    2021

  35. [43]

    A statistical model for tensor PCA

    Emile Richard and Andrea Montanari. A statistical model for tensor PCA. In Advances in Neural Information Processing Systems (NIPS) , volume 27, pages 2897--2905. MIT Press, 2014

    2014

  36. [44]

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

    2022

  37. [45]

    Average-case hardness of RIP certification

    Tengyao Wang, Quentin Berthet, and Yaniv Plan. Average-case hardness of RIP certification. In Advances in Neural Information Processing Systems (NIPS) , volume 29, pages 3826--3834. Curran Associates, Inc., 2016

    2016

  38. [46]

    Alexander S. Wein. Optimal low-degree hardness of maximum independent set. Mathematical Statistics and Learning , pages 221--251, 2022

    2022

  39. [47]

    Wein, Ahmed El Alaoui, and Cristopher Moore

    Alexander S. Wein, Ahmed El Alaoui, and Cristopher Moore. The Kikuchi hierarchy and tensor PCA. In Proceedings of the IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1446--1468. IEEE, 2019

    2019

Pith tools

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