Pith. sign in

REVIEW 4 minor 300 references

A poly-time algorithm exactly recovers the hidden matching of high-dimensional correlated Gaussians at constant correlation ρ²>√α by counting wide trees.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-10 05:42 UTC pith:AD2AWTC7

load-bearing objection First poly-time exact recovery for high-d Procrustes matching at constant correlation, via a carefully engineered wide-tree signature and Weingarten moment control.

arxiv 2607.08538 v1 pith:AD2AWTC7 submitted 2026-07-09 stat.ML cs.ITcs.LGmath.ITmath.STstat.TH

High-Dimensional Procrustes Matching via Tree Counts

Xiaochun Niu , Tselil Schramm , Jiaming Xu This is my paper
classification stat.ML cs.ITcs.LGmath.ITmath.STstat.TH MSC 62H3068Q2505C8015B52
keywords Procrustes matchingtree countingOtter's constanthigh-dimensional statisticsWeingarten calculusgraph matchingcolor codinglow-degree polynomials
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies Procrustes matching: two sets of n Gaussian vectors in R^d are related by an unknown permutation and an unknown rotation, and one must recover the permutation. In high dimension (d much larger than log n) earlier work needed correlation near 1 even for information-theoretic recovery. The authors give a polynomial-time algorithm that succeeds at constant correlation whenever ρ² exceeds the square root of Otter’s tree enumeration constant α≈0.338 and d is at least polylogarithmic in n. The algorithm builds vector signatures for each data point by counting a carefully chosen family of wide rooted trees (many non-isomorphic small branches attached to a high-degree root) inside the bipartite weighted graphs defined by the data matrices, then matches points whose signatures are sufficiently similar. They also prove a stronger information-theoretic threshold that permits vanishing correlation, and a low-degree calculation indicating that the same √α barrier is essentially necessary inside the tree-counting family.

Core claim

Whenever d≥polylog(n) and ρ²>√α (α≈0.338 Otter’s constant), a polynomial-time tree-counting algorithm recovers the unknown permutation exactly with high probability. The same algorithm, after a seeded-boosting step, upgrades almost-exact recovery to exact recovery under the slightly weaker condition ρ²≧C max{log n/d,1/√log n}.

What carries the argument

Similarity scores formed from weighted counts of a family of “wide” bipartite trees (Definition 2.2): each tree consists of D≈K/log K non-isomorphic degree-2 branches of size M=K/D attached to a common high-degree root, with K=Θ(log n). Mean separation and variance of these scores are controlled by Weingarten calculus on alternating circuit decompositions of the trees’ n-unions; the scores are approximated in poly(n,d) time by color coding.

Load-bearing premise

The asymptotic formula for Weingarten functions is used under the standing hypothesis that dimension d grows faster than a fixed power of log n (specifically d>12(2K)^{7/2} with K=Θ(log n)); if that growth fails, the mean/variance analysis and the polynomial-time claim no longer hold.

What would settle it

For concrete parameters n=2^{20}, d=(log n)^{C} with C large enough that the Weingarten hypothesis holds, and ρ² just above √α, run the color-coding tree-counting procedure and check whether the recovered matching equals the planted permutation with high probability over many independent draws; failure on a non-vanishing fraction of trials would falsify the main theorem.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 4 minor

Summary. The paper studies high-dimensional Procrustes matching: recover an unknown permutation that aligns two n-point Gaussian clouds in R^d that are related by a latent orthogonal transformation and correlation ρ. Prior high-d guarantees required ρ o1. The main algorithmic result (Thm 1.1 / 2.1–2.2) is a polynomial-time exact-recovery procedure that succeeds for constant correlation ρ^{2}>√α (α≈0.338 Otter’s constant) once d≥polylog(n). The method builds similarity scores from weighted counts of a specially designed family of wide bipartite trees (Defs 2.1–2.2) whose d-nodes all have degree 2; the scores are approximated in poly time by color coding (Alg 2 / Prop 2.1) and then boosted from almost-exact to exact recovery by a seeded geometric matching step (Alg 3 / Thm 2.2). An improved information-theoretic guarantee via the quadratic-assignment estimator (Thm 2.3) shows exact recovery is possible for ρ^{2}≳max{log n/d,√(log n/n)}, and a low-degree calculation (Thm 10.1) indicates that √α is essentially optimal inside the tree-counting framework.

Significance. The work closes a long-standing gap: constant-correlation, polynomial-time exact matching in the high-dimensional Procrustes / geometric-graph-alignment model. The technical contribution is substantial—joint-moment analysis via Weingarten calculus on alternating circuit decompositions of decorated union graphs, a carefully engineered wide-tree family that simultaneously controls mean separation and variance, and a clean color-coding + seeding pipeline. The information-theoretic improvement and the matching low-degree barrier for tree polynomials further strengthen the contribution. The results are derived with explicit error terms under stated hypotheses; Otter’s constant enters as a classical combinatorial fact rather than a fitted parameter. If the claims hold, the paper will be a standard reference for high-dimensional matching and for the use of tree polynomials in geometric models.

minor comments (4)
  1. The standing hypothesis d>12(2K)^{7/2} for the Weingarten asymptotic (Lemma 4.4) is used throughout Sections 4–6; while it is absorbed into the polylog assumption of the main theorems, a short explicit remark in Section 2.4 that C2 is chosen large enough to satisfy this inequality would make the parameter hierarchy fully self-contained.
  2. In the variance decomposition (Lemma 6.2 and Props 6.1–6.2) the geometric-series bounds rely on several “poly(K)/min{d,n}<1/2” conditions; collecting these numerical requirements once (e.g., after (2.9)) would improve readability.
  3. Figure 1 and the schematic Figures 2–3 are helpful; adding a short caption sentence that explicitly marks the root degree D and branch size M would make the parameter choices easier to track.
  4. A few minor typos appear (e.g., “wheneverd”, “Notethat”). A light copy-edit pass would remove them.

Circularity Check

0 steps flagged

No significant circularity: threshold and guarantees are derived from classical combinatorial enumeration, external moment tools, and self-contained variance analysis under explicit hypotheses.

full rationale

The central algorithmic claim (exact recovery for ho^{2}>\sqrtα when d mid polylog(n)) is obtained by constructing wide trees whose branch count is governed by Otter’s classical asymptotic |J| mid( mid+o(1))^{-M} (Definition 2.1, citing [Ott48]), then verifying mean separation (Proposition 3.1 via Weingarten/Isserlis, Theorem 4.1) and variance bounds (Proposition 3.2) that force the same ho^{4}> mid condition for concentration. These moment calculations rest on the external asymptotic for the Weingarten function (Lemma 4.4 from [CM17]) under the paper’s explicit standing hypothesis d>12(2K)^{7}/^{2} with K= mid(log n); the hypothesis is already the operating regime of Theorems 2.1–2.2 and is not smuggled. The low-degree calculation (Theorem 10.1) independently recovers the same mid-barrier for any tree polynomial, confirming necessity within the tree-counting class rather than importing a uniqueness claim. Color-coding approximation and seeded exact-recovery boost inherit the same parameters without fitting or redefinition. No step reduces a claimed prediction to a fitted input, a self-definitional identity, or a load-bearing self-citation whose content is the target result. The derivation is therefore self-contained against external classical facts and standard probabilistic tools.

Axiom & Free-Parameter Ledger

2 free parameters · 6 axioms · 1 invented entities

The central algorithmic claim rests on classical combinatorial and probabilistic tools (Otter, Weingarten, Isserlis, color-coding, Gaussian concentration) plus modeling assumptions (i.i.d. Gaussians, Haar Q, uniform π). No free parameters are fitted to data; constants C1,c1,C2 are existential proof constants. The only invented object is the wide-tree family, which is an algorithmic construction rather than a physical postulate.

free parameters (2)
  • Tree parameters (K=C1 log n, D=c1 K/log K)
    Existential constants chosen large/small enough for variance bounds; not fitted to any dataset.
  • Score threshold τ=c|T|n^K d^K ρ^{2K}, c∈(1/4,3/4)
    Arbitrary constant in an open interval that works by Chebyshev; not data-driven.
axioms (6)
  • standard math Otter’s asymptotic: number of unlabeled trees on k edges is (α+o(1))^{-k} with α≈0.338
    Used to size the branch family J and obtain |T|≥(α+ε/2)^{-K} (Def. 2.1, §2.3).
  • standard math Weingarten calculus asymptotic for Haar orthogonal moments (Collins–Matsumoto)
    Lemma 4.4 supplies the leading d-power for every joint moment; invoked throughout §§4–6,10.
  • standard math Isserlis/Wick theorem for Gaussian moments
    Lemma 4.1 converts E[X^G Y^H|Q] into matchings (Lemma 4.2).
  • standard math Color-coding counts colorful tree copies in poly time (Alon–Yuster–Zwick / Alon et al.)
    Section 7 reduces enumeration of Θ(log n)-size trees to O(n^C d) time.
  • domain assumption Data model: Xi~N(0,Id), Yi=ρ Q X_π(i)+√(1−ρ²)Zi, Q Haar on Od, π uniform
    Equation (1.1); all statistical claims are conditional on this generative model.
  • ad hoc to paper d>12(2K)^{7/2} for Weingarten error control
    Standing hypothesis after Theorem 4.1; forces d=polylog(n) once K=Θ(log n).
invented entities (1)
  • Wide tree family T (Defs. 2.1–2.2) no independent evidence
    purpose: Signature polynomials whose joint moments separate true from false pairs while remaining poly-time countable
    Algorithmic construction, not a physical postulate; independent_evidence is the success proof itself.

pith-pipeline@v1.1.0-grok45 · 62829 in / 2968 out tokens · 32742 ms · 2026-07-10T05:42:58.536879+00:00 · methodology

0 comments
read the original abstract

Suppose we observe two sets of $n$ Gaussian vectors in $\mathbb{R}^d$, with the promise that, after applying a permutation of $[n]$ and a rotation of $\mathbb{R}^d$, the two sets are $\rho$-correlated. The Procrustes matching problem asks us to recover the unknown permutation of $[n]$ that aligns the two sets. The problem is well-studied in the low-dimensional regime $d=O(\log n)$, but the high-dimensional regime $d\gg \log n$ has remained largely uncharted: prior matching guarantees require nearly perfect correlation $\rho=1-o(1)$, even for information-theoretic recovery. Our main result is a polynomial-time algorithm for exact recovery at constant correlation. The algorithm works by computing and comparing weighted counts of a specially chosen family of ``wide'' trees. So long as $d\ge \mathrm{polylog}(n)$, the algorithm succeeds with high probability for any $\rho^2>\sqrt{\alpha}$, where $\alpha\approx 0.338$ is Otter's tree-counting constant. We complement this algorithmic result with an improved information-theoretic guarantee, showing that exact recovery is possible when $\rho^2 \gtrsim \max\{\log n/d,\sqrt{\log n/n}\}$. We also carry out a low-degree advantage calculation, which suggests that the condition $\rho^2 > \sqrt{\alpha}$ is necessary for any tree-counting algorithm.

Figures

Figures reproduced from arXiv: 2607.08538 by Jiaming Xu, Tselil Schramm, Xiaochun Niu.

Figure 1
Figure 1. Figure 1: Schematic illustration of a tree in T . Each dashed triangle represents the descendant subtree of a branch. We will later choose the parameters K and D carefully to meet our statistical requirements, taking K = Θ(log n) and D = Θ(K/ log K). The resulting trees are wide, with large root degree and small branch size (M = Θ(log K)). These choices will be explained in Section 2.3. 2.3 Statistical Properties of… view at source ↗
Figure 2
Figure 2. Figure 2: Dominant contribution to the true-pair mean. Every [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Dominant configurations for the false-pair variance. [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: shows an example of a graph J and its circuit decompositions. 1 1 2 e1 e2 e3 e4 [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Different cases of fully overlapping branches. [PITH_FULL_IMAGE:figures/full_fig_p027_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Schematic illustration of decomposition of a decorated union [PITH_FULL_IMAGE:figures/full_fig_p028_6.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

300 extracted references · 300 canonical work pages · 24 internal anchors

  1. [1]

    Biennial International Conference on Information Processing in Medical Imaging , pages=

    The softassign procrustes matching algorithm , author=. Biennial International Conference on Information Processing in Medical Imaging , pages=. 1997 , organization=

    work page 1997

  2. [2]

    ISAAC Congress (International Society for Analysis, its Applications and Computation) , pages=

    Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio , author=. ISAAC Congress (International Society for Analysis, its Applications and Computation) , pages=. 2019 , organization=

    work page 2019

  3. [3]

    Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

    Computational complexity of statistics: New insights from low-degree polynomials , author=. arXiv preprint arXiv:2506.10748 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  4. [4]

    Bioinformatics , volume=

    Biomolecular network motif counting and discovery by color coding , author=. Bioinformatics , volume=. 2008 , publisher=

    work page 2008

  5. [5]

    Journal of the ACM (JACM) , volume=

    Color-coding , author=. Journal of the ACM (JACM) , volume=. 1995 , publisher=

    work page 1995

  6. [6]

    Annals of Mathematics , volume=

    The number of trees , author=. Annals of Mathematics , volume=. 1948 , publisher=

    work page 1948

  7. [7]

    The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime

    The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime , author=. arXiv preprint arXiv:2402.15095 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  8. [8]

    Conference on Learning Theory , pages=

    Random graph matching in geometric models: the case of complete graphs , author=. Conference on Learning Theory , pages=. 2022 , organization=

    work page 2022

  9. [9]

    Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing , pages=

    Localization from mere connectivity , author=. Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing , pages=

    work page

  10. [10]

    Proceedings of the 26th International Conference on Scientific and Statistical Database Management , pages=

    Geometric graph matching and similarity: A probabilistic approach , author=. Proceedings of the 26th International Conference on Scientific and Statistical Database Management , pages=

    work page

  11. [11]

    L. Proc. 3DOR , volume=

    work page

  12. [12]

    The 22nd International Conference on Artificial Intelligence and Statistics , pages=

    Unsupervised alignment of embeddings with wasserstein procrustes , author=. The 22nd International Conference on Artificial Intelligence and Statistics , pages=. 2019 , organization=

    work page 2019

  13. [13]

    SIAM Journal on Optimization , volume=

    Exact recovery with symmetries for procrustes matching , author=. SIAM Journal on Optimization , volume=. 2017 , publisher=

    work page 2017

  14. [14]

    ACM Transactions on Graphics (TOG) , volume=

    Point registration via efficient convex relaxation , author=. ACM Transactions on Graphics (TOG) , volume=. 2016 , publisher=

    work page 2016

  15. [15]

    Physical Review E , volume=

    Recovery thresholds in the sparse planted matching problem , author=. Physical Review E , volume=. 2020 , publisher=

    work page 2020

  16. [16]

    2020 IEEE International Symposium on Information Theory (ISIT) , pages=

    Achievability of nearly-exact alignment for correlated Gaussian databases , author=. 2020 IEEE International Symposium on Information Theory (ISIT) , pages=. 2020 , organization=

    work page 2020

  17. [17]

    Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference , pages =

    Sharp threshold for alignment of graph databases with Gaussian weights , author =. Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference , pages =. 2022 , volume =

    work page 2022

  18. [18]

    13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , year=

    Correlation Detection in Trees for Planted Graph Alignment , author=. 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , year=

    work page 2022

  19. [19]

    From tree matching to sparse graph alignment

    From tree matching to sparse graph alignment , author=. arXiv preprint arXiv:2002.01258 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 2002

  20. [20]

    Advances in Neural Information Processing Systems , pages=

    (Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs , author=. Advances in Neural Information Processing Systems , pages=

    work page

  21. [21]

    Probability Theory and Related Fields , volume=

    Efficient random graph matching via degree profiles , author=. Probability Theory and Related Fields , volume=. 2021 , publisher=

    work page 2021

  22. [22]

    Partial Recovery in the Graph Alignment Problem

    Partial Recovery in the Graph Alignment Problem , author=. arXiv preprint arXiv:2007.00533 , year=

    work page internal anchor Pith review Pith/arXiv arXiv 2007

  23. [23]

    , journal=

    Wu, Yihong and Xu, Jiaming and Yu, Sophie H. , journal=. Settling the Sharp Reconstruction Thresholds of Random Graph Matching , year=

    work page

  24. [24]

    Probability Theory and Related Fields , volume =

    Mao, Cheng and Rudelson, Mark and Tikhomirov, Konstantin , title =. Probability Theory and Related Fields , volume =. 2023 , doi =

    work page 2023

  25. [25]

    Proceedings of Thirty Fourth Conference on Learning Theory , pages =

    Random Graph Matching with Improved Noise Robustness , author =. Proceedings of Thirty Fourth Conference on Learning Theory , pages =. 2021 , volume =

    work page 2021

  26. [26]

    2020 , journal =

    Jian Ding and Zongming Ma and Yihong Wu and Jiaming Xu , Month =. 2020 , journal =

    work page 2020

  27. [27]

    Bulletin of the EATCS , number=

    The computer science and physics of community detection: Landscapes, phase transitions, and hardness , author=. Bulletin of the EATCS , number=

    work page

  28. [28]

    Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , pages=

    Reconciling graphs and sets of sets , author=. Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , pages=. 2018 , organization=

    work page 2018

  29. [29]

    Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining , pages=

    On the privacy of anonymized networks , author=. Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining , pages=. 2011 , organization=

    work page 2011

  30. [30]

    Partial Recovery of

    Cullina, Daniel and Kiyavash, Negar and Mittal, Prateek and Poor, H Vincent , journal=. Partial Recovery of

    work page

  31. [31]

    Slashdot social network , Month =

    work page

  32. [32]

    Distributed optimization and statistical learning via the alternating direction method of multipliers , Volume =

    Boyd, Stephen and Parikh, Neal and Chu, Eric and Peleato, Borja and Eckstein, Jonathan , Journal =. Distributed optimization and statistical learning via the alternating direction method of multipliers , Volume =

    work page

  33. [33]

    Exact distribution of the max/min of two

    Nadarajah, Saralees and Kotz, Samuel , Journal =. Exact distribution of the max/min of two

    work page

  34. [34]

    Some inequalities relating to the partial sum of binomial probabilities , Url =

    Okamoto, Masashi , Date-Added =. Some inequalities relating to the partial sum of binomial probabilities , Url =. Annals of the Institute of Statistical Mathematics , Month =. 1959 , Bdsk-Url-1 =. doi:10.1007/BF02883985 , Issn =

    work page doi:10.1007/bf02883985 1959

  35. [35]

    Estimation in the Spiked Wigner Model: A Short Proof of the Replica Formula , Year =

    Alaoui, Ahmed El and Krzakala, Florent , Journal =. Estimation in the Spiked Wigner Model: A Short Proof of the Replica Formula , Year =

    work page

  36. [36]

    Finite Size Corrections and Likelihood Ratio Fluctuations in the Spiked Wigner Model , Year =

    Alaoui, Ahmed El and Krzakala, Florent and Jordan, Michael I , Journal =. Finite Size Corrections and Likelihood Ratio Fluctuations in the Spiked Wigner Model , Year =

    work page

  37. [37]

    Tensor SVD: Statistical and Computational Limits , Year =

    Zhang, Anru and Xia, Dong , Journal =. Tensor SVD: Statistical and Computational Limits , Year =

    work page

  38. [38]

    Hopkins and Jonathan A

    Boaz Barak and Samuel B. Hopkins and Jonathan A. Kelner and Pravesh Kothari and Ankur Moitra and Aaron Potechin , Booktitle =. A

    work page

  39. [39]

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

    Thibault Lesieur and Caterina De Bacco and Jess Banks and Florent Krzakala and Cris Moore and Lenka Zdeborov. Arxiv preprint arxiv:1610.02918 , Title =

    work page internal anchor Pith review Pith/arXiv arXiv

  40. [40]

    Rate-optimal graphon estimation , Volume =

    Gao, Chao and Lu, Yu and Zhou, Harrison H , Date-Added =. Rate-optimal graphon estimation , Volume =. The Annals of Statistics , Number =

    work page

  41. [41]

    Rates of Convergence of Spectral Methods for Graphon Estimation , Year =

    Jiaming Xu , Booktitle =. Rates of Convergence of Spectral Methods for Graphon Estimation , Year =

    work page

  42. [42]

    Oracle inequalities for network models and sparse graphon estimation

    Klopp, Olga and Tsybakov, Alexandre B and Verzelen, Nicolas , Date-Added =. arXiv preprint arXiv:1507.04118 , Title =

    work page internal anchor Pith review Pith/arXiv arXiv

  43. [43]

    Optimal graphon estimation in cut distance

    Klopp, Olga and Verzelen, Nicolas , Date-Added =. arXiv preprint arXiv:1703.05101 , Title =

    work page internal anchor Pith review Pith/arXiv arXiv

  44. [44]

    Optimal Estimation and Completion of Matrices with Biclustering Structures , Volume =

    Gao, Chao and Lu, Yu and Ma, Zongming and Zhou, Harrison H , Date-Added =. Optimal Estimation and Completion of Matrices with Biclustering Structures , Volume =. Journal of Machine Learning Research , Number =

    work page

  45. [45]

    Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure , Year =

    Matthew Brennan and Guy Bresler and Wasim Huleihel , Date-Added =. Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure , Year =

    work page

  46. [46]

    Tensor principal component analysis via sum-of-square proofs

    Hopkins, Samuel B and Shi, Jonathan and Steurer, David , Booktitle =. Tensor principal component analysis via sum-of-square proofs. , Year =

    work page

  47. [47]

    Statistical and computational phase transitions in spiked tensor estimation , Year =

    Thibault Lesieur and L. Statistical and computational phase transitions in spiked tensor estimation , Year =

    work page

  48. [48]

    and Lim, Lek-Heng , Date-Added =

    Hillar, Christopher J. and Lim, Lek-Heng , Date-Added =. Most Tensor Problems Are NP-Hard , Volume =. J. ACM , Month = nov, Number =

    work page

  49. [49]

    A Statistical Model for Tensor PCA , Year =

    Montanari, Andrea and Richard, Emile , Booktitle =. A Statistical Model for Tensor PCA , Year =

    work page

  50. [50]

    Phase transitions in sparse

    Lesieur, Thibault and Krzakala, Florent and Zdeborov. Phase transitions in sparse. IEEE International Symposium on Information Theory , Date-Added =

    work page

  51. [51]

    Fundamental limits of symmetric low-rank matrix estimation , Volume =

    Marc Lelarge and L. Fundamental limits of symmetric low-rank matrix estimation , Volume =. Proceedings of the 2017 Conference on Learning Theory , Editor =

    work page 2017

  52. [52]

    The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices , Volume =

    Benaych-Georges, Florent and Nadakuditi, Raj Rao , Date-Added =. The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices , Volume =. Advances in Mathematics , Number =

    work page

  53. [53]

    The largest eigenvalue of small rank perturbations of Hermitian random matrices , Volume =

    P. The largest eigenvalue of small rank perturbations of Hermitian random matrices , Volume =. Probability Theory and Related Fields , Number =

    work page

  54. [54]

    Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices , Year =

    Baik, Jinho and Ben Arous, G. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices , Year =. Annals of Probability , Pages =

    work page

  55. [55]

    Deshpande and A

    Y. Deshpande and A. Montanari , Booktitle =. Information-theoretically optimal sparse. 2014 , Bdsk-Url-1 =. doi:10.1109/ISIT.2014.6875223 , Month =

    work page doi:10.1109/isit.2014.6875223 2014

  56. [56]

    Neyman, E

    J. Neyman, E. S. Pearson , Date-Added =. On the Problem of the Most Efficient Tests of Statistical Hypotheses , Volume =. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character , Pages =

    work page

  57. [57]

    Wein and Afonso S

    Amelia Perry and Alexander S. Wein and Afonso S. Bandeira and Ankur Moitra , Date-Added =. Optimality and Sub-optimality of

    work page

  58. [58]

    Wein and Afonso S

    Amelia Perry and Alexander S. Wein and Afonso S. Bandeira , Date-Added =. Statistical limits of spiked tensor models , Year =

    work page

  59. [59]

    Extremal cuts of sparse random graphs , Volume =

    Dembo, Amir and Montanari, Andrea and Sen, Subhabrata , Date-Added =. Extremal cuts of sparse random graphs , Volume =. The Annals of Probability , Number =

    work page

  60. [60]

    On the Liapunoff limit of error in the theory of probability

    C.-G. Esseen , Date-Added =. "On the Liapunoff limit of error in the theory of probability" , Volume =. Arkiv f

    work page

  61. [61]

    The dynamics of message passing on dense graphs, with applications to compressed sensing , Volume =

    Bayati, Mohsen and Montanari, Andrea , Journal =. The dynamics of message passing on dense graphs, with applications to compressed sensing , Volume =

    work page

  62. [62]

    State evolution for general approximate message passing algorithms, with applications to spatial coupling , Volume =

    Javanmard, Adel and Montanari, Andrea , Journal =. State evolution for general approximate message passing algorithms, with applications to spatial coupling , Volume =

    work page

  63. [63]

    Probability and measure , Year =

    Billingsley, Patrick , Publisher =. Probability and measure , Year =

    work page

  64. [64]

    The divergence and

    Kailath, Thomas , Date-Added =. The divergence and. IEEE transactions on communication technology , Number =

    work page

  65. [65]

    Hajek and Y

    B. Hajek and Y. Wu and J. Xu , Booktitle =. Information Limits for recovering a Hidden Community , Year =

    work page

  66. [66]

    Learning the graph of epidemic cascades , Volume =

    Netrapalli, Praneeth and Sanghavi, Sujay , Booktitle =. Learning the graph of epidemic cascades , Volume =

    work page

  67. [67]

    Xu , Booktitle =

    Bruce Hajek and Sewoong Oh and J. Xu , Booktitle =. Minimax-optimal Inference from Partial Rankings , Year =

    work page

  68. [68]

    Budget-optimal task allocation for reliable crowdsourcing systems , Volume =

    Karger, David R and Oh, Sewoong and Shah, Devavrat , Date-Added =. Budget-optimal task allocation for reliable crowdsourcing systems , Volume =. Operations Research , Number =

    work page

  69. [69]

    Beyond Spectral: Tight Bounds for Planted Gaussians , Year =

    Ravi Kannan and Santosh Vempala , Date-Added =. Beyond Spectral: Tight Bounds for Planted Gaussians , Year =

    work page

  70. [70]

    Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic

    Emmanuel Abbe and Colin Sandon , Date-Added =. Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic

    work page

  71. [71]

    Information-theoretic thresholds for community detection in sparse networks , Year =

    Jess Banks and Cristopher Moore and Joe Neeman and Praneeth Netrapalli , Booktitle =. Information-theoretic thresholds for community detection in sparse networks , Year =

    work page

  72. [72]

    Convexified Modularity Maximization for Degree-corrected Stochastic Block Models

    Y. Chen and X. Li and J. Xu , Date-Added =. Convexified Modularity Maximization for Degree-corrected Stochastic Block Models , Year =. 1512.08425 , Month =

    work page internal anchor Pith review Pith/arXiv arXiv

  73. [73]

    Yun and Alexandre Proutiere , Date-Added =

    S. Yun and Alexandre Proutiere , Date-Added =. Optimal Cluster Recovery in the Labeled Stochastic Block Model , Year =

    work page

  74. [74]

    Jog and P.-L

    V. Jog and P.-L. Loh , Date-Modified =. Information-theoretic bounds for exact recovery in weighted stochastic block models using the

    work page

  75. [75]

    Information Theory: Coding Theorems for Discrete Memoryless Systems , Year =

    Imre Csisz. Information Theory: Coding Theorems for Discrete Memoryless Systems , Year =

    work page

  76. [76]

    Yury Polyanskiy and Yihong Wu , Date-Modified =

    work page

  77. [77]

    Large deviations techniques and applications , Year =

    Dembo, Amir and Zeitouni, Ofer , Publisher =. Large deviations techniques and applications , Year =

    work page

  78. [78]

    The Hidden Subgraph Problem , Year =

    Hamid Javadi and Andrea Montanari , Date-Added =. The Hidden Subgraph Problem , Year =

    work page

  79. [79]

    Phase Transitions in Semidefinite Relaxations , Year =

    Adel Javanmard and Andrea Montanari and Federico Ricci-Tersenghi , Date-Added =. Phase Transitions in Semidefinite Relaxations , Year =

    work page

  80. [80]

    Chernoff , Date-Added =

    H. Chernoff , Date-Added =. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations , Year =. The Annals of Mathematical Statistics , Pages =

    work page

Showing first 80 references.