Pith. sign in

REVIEW 1 major objections 5 minor 49 references

Detecting weighted hidden cliques

T0 review · 1 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read A weighted analogue of the hidden clique problem is statistically detectable once the planted set has logarithmically many vertices, with polynomial-time spectral tests when $k=\Omega(\sqrt{n})$.

desk verdict A useful information-theoretic extension of planted clique with a mostly sound KL/chi-square threshold, but the advertised polynomial-time test for all singular pairs rests on a false interval-separation claim and a backwards binomial bound. read the letter →

arxiv 2506.21543 v2 pith:YIUOCOAC submitted 2025-06-26 math.ST cs.ITmath.ITmath.PRstat.TH

Urmisha Chatterjee , Karissa Huang , Ritabrata Karmakar , B. R. Vinay Kumar , Gábor Lugosi , Nandan Malhotra , Anirban Mandal , Maruf Alam Tarafdar This is my paper · ORCID
classification math.STcs.ITmath.ITmath.PRstat.TH MSC 05C8062C2062G10
keywords weightedhiddencliqueplantedhypothesistestingedgeweightsKullback-Leiblerdivergencechi-squaredspectraltestrandomgraphs
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 studies a weighted version of the hidden clique problem: a complete graph on $n$ vertices has edge weights drawn independently from $P$, except that the edges among $k$ randomly chosen vertices are drawn from $Q$, and the statistician must decide which model produced the observed weights. The central result is that, when $P$ and $Q$ are known and $Q$ is absolutely continuous with respect to $P$, the optimal risk tends to $0$ as soon as $k_n \ge (2+\epsilon)\log n / D_{\mathrm{KL}}(Q\Vert P)$, and tends to $1$ when $k_n$ is below a threshold expressed through the $\chi^2$-divergence. If $Q$ is not absolutely continuous with respect to $P$, then $k_n\to\infty$ is enough for detection, and in the unknown-distribution case a polynomial-time scan over intervals can achieve this under an interval-positivity condition. The interest is that a canonical statistical-computational problem is extended to general weighted graphs, with an information-theoretic crossover expressed in standard divergences and polynomial-time spectral tests working at the $\sqrt{n}$ scale.

What carries the argument

Three objects carry the argument. The likelihood ratio is $L(X)=\frac{1}{\binom{n}{k}}\sum_{|S|=k}\prod_{e\in E(S)}\frac{q(X_e)}{p(X_e)}$; its second moment under the null reduces to a sum over subset pairs in which the overlap size $i$ contributes $\rho^{\binom{i}{2}}$, and this is what yields the logarithmic threshold in the lower-bound direction. The scan statistic maximizing $\prod_{e\in E(S)} q(X_e)/p(X_e)$ over all $k$-subsets and comparing with $n^k$ yields the detectability bound in the upper direction. The spectral test transforms each edge weight $x$ into the indicator of the set $A=\{x:p(x)>q(x)\}$; because $\mathbb{E}_0[\phi(X)]-\mathbb{E}_1[\phi(X)]=d_{TV}(P,Q)$, the centred maximum eigenvalue separates the two hypotheses at the $\sqrt{n}$ scale, and the same transform works with only a set where the densities are ordered instead of the full densities.

What would settle it

Take $P$ uniform on $[0,1]$ and $Q$ a countable mixture of point masses on the rationals: $Q$ is not absolutely continuous with respect to $P$, yet every interval has positive $P$-mass, so the interval-scan test in Theorem 3.7 loses its key guarantee that outside edges almost surely avoid the chosen interval; checking whether any polynomial-time test still achieves vanishing risk for $k_n\to\infty$ on this pair would settle whether the claimed conclusion holds beyond the proof.

Watch

Extended reading notes

Core claim

The paper claims that the weighted hidden clique problem has a logarithmically growing information-theoretic threshold for essentially every distinct pair of distributions. The optimal likelihood-ratio test has risk controlled by the second moment $\mathbb{E}_0[L(X)^2]$, which evaluates to an average of $\rho^{\binom{|S\cap T|}{2}}$ over pairs of $k$-subsets, where $\rho=\chi^2(Q\Vert P)+1$; this produces an indistinguishability bound near $k_n \approx 2\log_\rho n$ and, through a scan test, a detection guarantee near $k_n \ge (2+\epsilon)\log n / D_{\mathrm{KL}}(Q\Vert P)$. When $Q$ has mass on a set that $P$ assigns probability zero, a simple test looking for any edge weight in that set makes the risk at most $(1-Q(A))^{\binom{k}{2}}$, so $k_n\to\infty$ suffices. The paper also establishes that polynomial-time spectral tests succeed once $k_n=\Omega(\sqrt{n})$, both with full knowledge of the densities and, when the means differ and the supports are bounded, with knowledge of only the means.

Load-bearing premise

The proof of the unknown-distribution result assumes that whenever $Q$ is not absolutely continuous with respect to $P$, some interval has zero $P$-mass and positive $Q$-mass; singular pairs built from countable point masses can violate this, so the stated claim is not established for those pairs.

Editorial extensions

If this is right

  • For any distinct $P$ and $Q$, $k_n\ge c\log n$ makes the optimal risk vanish, so the weighted problem inherits the classical logarithmic information-theoretic threshold.
  • If $Q$ is not absolutely continuous with respect to $P$, detection requires only $k_n\to\infty$; with unknown distributions a polynomial-time interval scan achieves this whenever the singular set can be witnessed by an interval.
  • The spectral test based on the indicator transform decides with risk at most $\delta$ whenever $k_n > 4\sqrt{(\log 9)n + \log(4/\delta)}/d_{TV}(P,Q)$, using only the ordering of the densities.
  • When the densities are unknown but the means are known and differ, the same spectral test works at $k_n = \Omega(\sqrt{n}/|\mu_Q-\mu_P|)$ for bounded supports.
  • The classical hidden clique is the special case $P=\mathrm{Bernoulli}(p)$, $Q=\delta_1$; substituting gives the familiar $k_n\sim 2\log_{1/p} n$ detection threshold.

Reading between the lines

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

  • Editorial inference: the interval-positivity condition in Theorem 3.7 is not implied by non-absolute continuity; $P$ uniform on $[0,1]$ and $Q$ a countable sum of point masses on the rationals form a singular pair with no $P$-null interval of positive $Q$-mass, so the conclusion is not proved for such pairs even if it is true.
  • Editorial inference: the gap between the KL-based detectability threshold and the $\chi^2$-based indistinguishability threshold suggests that a sharp phase transition, if it exists, is governed by an intermediate divergence; computing the risk of the likelihood-ratio test near $k_n \sim \log n$ for pairs like $N(0,1)$ versus $N(1,1)$ would locate the crossover.
  • Editorial inference: the spectral transform is exactly the test built from total-variation separation, so the required $k_n=\Omega(\sqrt{n})$ is plausibly the price of discarding the likelihood structure; simulating the spectral gap for $k_n$ between $\log n$ and $\sqrt{n}$ would quantify the computational gap for weighted graphs.
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

1 major / 5 minor

Summary. This paper studies a weighted generalization of the hidden clique problem. Under the null hypothesis all edge weights of the complete graph are i.i.d. from P; under the alternative, a random set of k vertices has all internal edge weights drawn from Q. The paper gives statistical limits and tests in two scenarios. When P and Q are known, Theorem 3.1 shows that if Q is not absolutely continuous with respect to P then the optimal risk tends to 0 whenever k tends to infinity; Theorem 3.4 gives divergence-based bounds when Q is absolutely continuous with respect to P; Theorem 3.6 gives a spectral test for k=Omega(sqrt(n)). In the partial-information scenario, Theorem 3.7 claims a polynomial-time interval-scan test for unknown singular Q whenever k tends to infinity, and Theorem 3.8 gives a spectral test using only the means and support when k=Omega(sqrt(n)). The proofs of Theorems 3.1, 3.2, 3.3, 3.4, 3.6, and 3.8 are mostly standard second-moment and concentration arguments. The main gap is Theorem 3.7, whose key geometric assertion about singular measures is false.

Significance. The weighted hidden clique problem is a natural and timely generalization, and the divergence-based thresholds in Theorem 3.4 are clean and potentially useful. The spectral tests are explicit and apply in both information scenarios. If Theorem 3.7's claim could be established, the paper would make a strong contribution by showing that unknown singular alternatives are always polynomially detectable at any k tending to infinity. However, the central advertised result for unknown singular Q is currently unsupported: the proposed interval-scan test provably fails for continuous singular measures such as the Cantor distribution against Lebesgue measure. The remaining results appear sound and are likely publishable after substantial revision.

major comments (1)
  1. [Section 4.6, Theorem 3.7] The proof begins with the key assertion that if Q is not absolutely continuous with respect to P, then there exists an interval I with P(I)=0 and Q(I)>0. This is false for continuous singular measures: take P=Uniform[0,1] and Q the standard Cantor distribution. Then Q is singular with respect to P, but every interval with Q(I)>0 also has P(I)>0. For such a pair, the event E used to define the test cannot occur under H1: any interval with positive Q-mass has positive P-mass, so outside edges of the planted clique fall in I with positive probability, making the condition sum over e not in E(S) of 1{X_e in I}=0 fail. The Type II error of the proposed test therefore tends to 1 rather than 0 when k tends to infinity. Consequently Theorem 3.7 and the corresponding claim in the abstract are not established; a different test or a different argument is needed for singular continuous Q.
minor comments (5)
  1. [Section 3.1, Theorem 3.4] The statement should explicitly assume P is not equal to Q, or that rho = chi^2(Q||P)+1 > 1. Otherwise, for P=Q the conditions have D_KL=0 and chi^2=0, and part (a) would assert R(T*)->0 for k at least (2+epsilon) log n / 0, which is vacuous and false because H0 and H1 are identical.
  2. [Section 4.4, proof of Theorem 3.4(a)] The display after the inequality 'P1(Tscan <= n^k) <= P1(...)' is garbled; it contains stray factors such as '{k choose 2} k^2/2' and should be rewritten as P1( (1/{k choose 2}) * sum_{e in E(S*)} log(q(X_e)/p(X_e)) <= 2 log n / k ), so that the strong-law step is clear.
  3. [Section 4.7, proof of Theorem 3.8] The cardinality of the epsilon-net on the unit sphere should be 9^n, not 9n as written. With the printed '9n' the union bound in equation (5) does not yield the claimed delta/2; the later substitution t = 4(b-a) sqrt((log 9)n + log(4/delta)) explicitly requires the 9^n bound.
  4. [Section 4.6, Theorem 3.7] The polynomial-time implementation of the interval scan could be clarified: for a fixed interval I, the condition that all edges with weights in I lie inside some set S of size k depends only on the set V_I of vertices incident to those edges and the number of such edges. The check reduces to whether |V_I| <= k and the number of edges with weights in I is at least k, not to an explicit search over all k-subsets.
  5. [General] There are minor typographical issues, such as 'scantest' in Section 3.1, 'definea' in the introduction, and 'coloumns' in the proof of Theorem 3.8, which should be corrected in a revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the central results are derived from first principles and standard divergence and concentration inequalities.

full rationale

The derivation chain is self-contained. Theorem 3.4(a) is proved directly from the likelihood-ratio scan statistic via a union bound and the strong law of large numbers; Theorem 3.4(b) is a moment calculation of E0[L(X)^2] that invokes a standard threshold from Bollobás's random graph text, not the authors' own results. Theorem 3.6 is obtained by applying Theorem 3.8 to the indicator-transformed matrix Z, and Theorem 3.8 is proved from first principles using an epsilon-net argument and Hoeffding's inequality. There are no fitted parameters renamed as predictions, no self-definitional identities, and no load-bearing self-citations: citations to Lugosi and Devroye-Gyorfi-Lugosi are to textbook facts about epsilon nets and risk-divergence identities. The notable weakness in Theorem 3.7—the claim that if Q is not absolutely continuous with respect to P then some interval has P-mass zero and positive Q-mass, which fails for continuous singular distributions such as Cantor versus uniform—is a mathematical correctness gap, not a circularity: the test and its analysis are not equivalent to the theorem's assumptions by construction. Therefore no circular step is present and the circularity score is 0.

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

The paper's central results rest on standard probability tools and explicit modeling assumptions such as a random planted subset, absolute continuity, and a common dominating measure. No free parameters are fitted to data and no new entities are introduced. The problematic interval-existence assertion in Theorem 3.7 and the density construction in Proposition 3.3 are flagged as red flags rather than ledger axioms.

assumptions (4)
  • domain assumption Under the alternative hypothesis, the set of k clique vertices is chosen uniformly at random and independently of the edge weights.
    This is the model definition in Section 3; all results are for this random-planting model.
  • domain assumption For Theorems 3.4 and 3.6, P and Q have densities with respect to a common dominating measure and Q is absolutely continuous with respect to P.
    Stated in the theorem hypotheses; needed for the likelihood ratio and for the set A = {p > q} used in the spectral test.
  • standard math Standard probabilistic tools: strong law of large numbers, Hoeffding's inequality, epsilon-net bound for the unit sphere with net size at most 9^n, and the second-moment convergence bound for the planted-clique likelihood ratio from Bollobas.
    Used in Sections 4.4, 4.5, 4.7 and in the proof of Theorem 3.4(b).
  • standard math Proposition A.3 relating the optimal risk to E0[sqrt(L)], and divergence inequalities such as D_KL <= log(1 + chi-squared).
    Used throughout the proofs; cited to standard references [20] and [46].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Detecting weighted hidden cliques." pith.science (2026). https://pith.science/paper/YIUOCOAC

@misc{pith2026250621543,
  author       = {Pith},
  title        = {Pith review of: Detecting weighted hidden cliques},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YIUOCOAC}},
  note         = {Machine review of arXiv:2506.21543}
}
abstract

We study a generalization of the classical hidden clique problem to graphs with real-valued edge weights. Formally, we define a hypothesis testing problem. Under the null hypothesis, edges of a complete graph on $n$ vertices are associated with independent and identically distributed edge weights from a distribution $P$. Under the alternate hypothesis, $k$ vertices are chosen at random and the edge weights between them are drawn from a distribution $Q$, while the remaining are sampled from $P$. The goal is to decide, upon observing the edge weights, which of the two hypotheses they were generated from. We investigate the problem under two different scenarios: (1) when $P$ and $Q$ are completely known, and (2) when there is only partial information of $P$ and $Q$. In the first scenario, we obtain statistical limits on $k$ when the two hypotheses are distinguishable, and when they are not. Additionally, in each of the scenarios, we provide bounds on the minimal risk of the hypothesis testing problem when $Q$ is not absolutely continuous with respect to $P$. We also provide computationally efficient spectral tests that can distinguish the two hypotheses as long as $k=\Omega(\sqrt{n})$ in both the scenarios.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

49 extracted references · 46 canonical work pages

  1. [1]

    Addario-Berry, O

    L. Addario-Berry, O. Angel, G. Lugosi, M. Z. Rácz, and T. Schramm. The statistical threshold for planted matchings and spanning trees.arXiv preprint arXiv:2602.07669, 2026

    work page arXiv 2026

  2. [2]

    Addario-Berry, N

    L. Addario-Berry, N. Broutin, L. Devroye, and G. Lugosi. On combinatorial testing prob- lems.The Annals of Statistics, 38(5):3063–3092, 2010

    work page 2010

  3. [3]

    Planted clique detection and recovery from the hypergraph adjacency matrix

    K. Alaluusua and B. R. Vinay Kumar. Planted clique detection and recovery from the hypergraph adjacency matrix.arXiv preprint arXiv:2604.08691, 2026

    work page Pith review arXiv 2026

  4. [4]

    N. Alon, M. Krivelevich, and B. Sudakov. Finding a large hidden clique in a random graph. Random Structures & Algorithms, 13(3-4):457–466, 1998

    work page 1998

  5. [5]

    B. P. Ames and S. A. Vavasis. Nuclear norm minimization for the planted clique and biclique problems.Mathematical programming, 129(1):69–89, 2011

    work page 2011

  6. [6]

    Arias-Castro, E

    E. Arias-Castro, E. J. Candes, and A. Durand. Detection of an anomalous cluster in a network.The Annals of Statistics, pages 278–304, 2011

    work page 2011

  7. [7]

    Arias-Castro, E

    E. Arias-Castro, E. J. Candès, H. Helgason, and O. Zeitouni. Searching for a trail of evidence in a maze.The Annals of Statistics, 36(4):1726 – 1757, 2008

    work page 2008

  8. [8]

    Arias-Castro and G

    E. Arias-Castro and G. R. Grimmett. Cluster detection in networks using percolation. Bernoulli, 19(2):676–719, 2013

    work page 2013

Show all 49 references
  1. [9]

    Arias-Castro and N

    E. Arias-Castro and N. Verzelen. Community detection in dense random networks.The Annals of Statistics, pages 940–969, 2014

    2014

  2. [10]

    Avrachenkov, A

    K. Avrachenkov, A. Bobu, N. Litvak, and R. Michielan. Planted clique recovery in random geometric graphs.arXiv preprint arXiv:2510.12365, 2025

    2025 arXiv

  3. [11]

    Bagaria, J

    V. Bagaria, J. Ding, D. Tse, Y. Wu, and J. Xu. Hidden hamiltonian cycle recovery via linear programming.Operations research, 68(1):53–70, 2020

    2020

  4. [12]

    Barak, S

    B. Barak, S. Hopkins, J. Kelner, P. K. Kothari, A. Moitra, and A. 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]

    Blumer, A

    A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth. Learnability and the Vapnik- Chervonenkis dimension.Journal of the ACM, 36:929–965, 1989

    1989

  6. [14]

    Bollobás.Random graphs

    B. Bollobás.Random graphs. Springer, 1998

    1998

  7. [15]

    Bresler and T

    G. Bresler and T. Jiang. Detection-recovery and detection-refutation gaps via reductions from planted clique. InThe Thirty Sixth Annual Conference on Learning Theory, pages 5850–5889. PMLR, 2023

    2023

  8. [16]

    Butucea and Y

    C. Butucea and Y. I. Ingster. Detection of a sparse submatrix of a high-dimensional noisy matrix.Bernoulli, pages 2652–2688, 2013

    2013

  9. [17]

    Chen and J

    Y. Chen and J. Xu. Statistical-computational tradeoffs in planted problems and subma- trix localization with a growing number of clusters and submatrices.Journal of Machine Learning Research, 17(27):1–57, 2016. 18

    2016

  10. [18]

    Dekel, O

    Y. Dekel, O. Gurel-Gurevich, and Y. Peres. Finding hidden cliques in linear time with high probability.Combinatorics, Probability and Computing, 23(1):29–49, 2014

    2014

  11. [19]

    Deshpande and A

    Y. Deshpande and A. Montanari. Finding hidden cliques of size p N/ein nearly linear time.Foundations of Computational Mathematics, 15(4):1069–1128, 2015

    2015

  12. [20]

    Springer-Verlag, New York, 1996

    L.Devroye, L.Györfi, andG.Lugosi.A probabilistic theory of pattern recognition, volume31 ofApplications of Mathematics (New York). Springer-Verlag, New York, 1996

    1996

  13. [21]

    Dhawan, C

    A. Dhawan, C. Mao, and A. S. Wein. Detection of dense subhypergraphs by low-degree polynomials.Random Structures & Algorithms, 66(1):e21279, 2025

    2025

  14. [22]

    Elimelech and W

    D. Elimelech and W. Huleihel. Detecting arbitrary planted subgraphs in random graphs. arXiv preprint arXiv:2503.19069, 2025

    2025 arXiv

  15. [23]

    Feige and R

    U. Feige and R. Krauthgamer. Finding and certifying a large hidden clique in a semirandom graph.Random Structures & Algorithms, 16(2):195–208, 2000

    2000

  16. [24]

    Feige and D

    U. Feige and D. Ron. Finding hidden cliques in linear time. In21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA’10), pages 189–204. Discrete Mathematics and Theoretical Computer Science, 2010

    2010

  17. [25]

    Feldman, E

    V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala, and Y. Xiao. Statistical algorithms and a lower bound for detecting planted cliques.Journal of the ACM (JACM), 64(2):8, 2017

    2017

  18. [26]

    Gamarnik

    D. Gamarnik. The overlap gap property: A topological barrier to optimizing over random structures.Proceedings of the National Academy of Sciences, 118(41):e2108492118, 2021

    2021

  19. [27]

    Gamarnik and I

    D. Gamarnik and I. Zadik. The landscape of the planted clique problem: Dense subgraphs and the overlap gap property.The Annals of Applied Probability, 34(4):3375–3434, 2024

    2024

  20. [28]

    Hajek, Y

    B. Hajek, Y. Wu, and J. Xu. Computational lower bounds for community detection on random graphs. InConference on Learning Theory, pages 899–928. PMLR, 2015

    2015

  21. [29]

    Hajek, Y

    B. Hajek, Y. Wu, and J. Xu. Information limits for recovering a hidden community.IEEE Transactions on Information Theory, 63(8):4729–4745, 2017

    2017

  22. [30]

    Communitydetectioninthelabelledstochastic block model.arXiv preprint arXiv:1209.2910, 2012

    S.Heimlicher, M.Lelarge, andL.Massoulié. Communitydetectioninthelabelledstochastic block model.arXiv preprint arXiv:1209.2910, 2012

    2012 arXiv

  23. [31]

    Hirahara and N

    S. Hirahara and N. Shimizu. Planted clique conjectures are equivalent. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 358–366, 2024

    2024

  24. [32]

    Huleihel

    W. Huleihel. Inferring hidden structures in random graphs.IEEE Transactions on Signal and Information Processing over Networks, 8:855–867, 2022

    2022

  25. [33]

    S. Janson. Asymptotic equivalence and contiguity of some random graphs.Random Struc- tures & Algorithms, 36(1):26–45, 2010

    2010

  26. [34]

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

    1992

  27. [35]

    L. Kučera. Expected complexity of graph partitioning problems.Discrete Applied Mathe- matics, 57(2-3):193–212, 1995. 19

    1995

  28. [36]

    Lelarge, L

    M. Lelarge, L. Massoulié, and J. Xu. Reconstruction in the labeled stochastic block model. In2013 IEEE Information Theory Workshop (ITW), pages 1–5. IEEE, 2013

    2013

  29. [37]

    Robustalgorithmsforrecoveringplantedr-colorable graphs.Proceedings of Machine Learning Research vol, 291:1–29, 2025

    A.Louis, R.Paul, andP.Raghavendra. Robustalgorithmsforrecoveringplantedr-colorable graphs.Proceedings of Machine Learning Research vol, 291:1–29, 2025

    2025

  30. [38]

    G. Lugosi. Lectures on combinatorial statistics.47th Probability Summer School, Saint- Flour, pages 1–91, 2017

    2017

  31. [39]

    C. Mao, A. S. Wein, and S. Zhang. Information-theoretic thresholds for planted dense cycles.IEEE Transactions on Information Theory, 71(2):1266–1282, 2024

    2024

  32. [40]

    Massoulié, L

    L. Massoulié, L. Stephan, and D. Towsley. Planting trees in graphs, and finding them back. InConference on Learning Theory, pages 2341–2371. PMLR, 2019

    2019

  33. [41]

    R. Meka, A. Potechin, and A. Wigderson. Sum-of-squares lower bounds for planted clique. InProceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 87–96, 2015

    2015

  34. [42]

    Moharrami, C

    M. Moharrami, C. Moore, and J. Xu. The planted matching problem: Phase transitions and exact results.The Annals of Applied Probability, 31(6):2663–2720, 2021

    2021

  35. [43]

    Montanari, D

    A. Montanari, D. Reichman, and O. Zeitouni. On the limitation of spectral methods: From the gaussian hidden clique problem to rank-one perturbations of gaussian tensors. In Advances in Neural Information Processing Systems, pages 217–225, 2015

    2015

  36. [44]

    Narang, W

    I. Narang, W. Perkins, and T. L. Wee. Optimal detection of planted stars via a random energy model.arXiv preprint arXiv:2602.15585, 2026

    2026

  37. [45]

    Rotenberg, W

    A. Rotenberg, W. Huleihel, and O. Shayevitz. Planted bipartite graph detection.IEEE Transactions on Information Theory, 70(6):4319–4334, 2024

    2024

  38. [46]

    van Erven and P

    T. van Erven and P. Harremoes. Rényi divergence and Kullback-Leibler divergence.IEEE Transactions on Information Theory, 60(7):3797–3820, July 2014

    2014

  39. [47]

    Vapnik and A

    V. Vapnik and A. Chervonenkis.Theory of Pattern Recognition. Nauka, Moscow, 1974. (in Russian); German translation:Theorie der Zeichenerkennung, Akademie Verlag, Berlin, 1979

    1974

  40. [48]

    Verzelen and E

    N. Verzelen and E. Arias-Castro. Community detection in sparse random networks. 2015

    2015

  41. [49]

    M. Xu, V. Jog, and P.-L. Loh. Optimal rates for community estimation in the weighted stochastic block model.The Annals of Statistics, 48(1):183–204, 2020. 20

    2020

Pith tools

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