Pith. sign in

REVIEW 2 major objections 3 minor 300 references

The number of edge queries needed to detect a planted subgraph is governed by three structural mechanisms, with near-tight bounds for broad graph families.

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 · deepseek-v4-flash

2026-08-01 18:59 UTC pith:MO6DOIEK

load-bearing objection A genuinely useful framework with a broken step in the main upper-bound proof; the lemma is almost certainly repairable, but as written Theorem 3 is not proven. the 2 major comments →

arxiv 2607.17118 v1 pith:MO6DOIEK submitted 2026-07-19 math.ST cs.ITmath.ITstat.TH

Fundamental Limits of Query-Based Subgraph Detection

Wasim Huleihel This is my paper
classification math.ST cs.ITmath.ITstat.TH MSC 62C2062F0305C80
keywords planted subgraph detectionnon-adaptive edge queriesquery complexityrandom graph detectionvertex coverscan testdegree-on-a-cut testhypothesis testing
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 tries to establish that, when detection is limited to a fixed number of non-adaptive edge queries into a random graph, the minimum query budget for detecting an arbitrary planted subgraph is set by a short list of structural features: how many dense local witnesses the subgraph contains, how much degree is concentrated on a small 'hub' set, and how many edges the subgraph has overall. If true, this gives a unified query-complexity theory that contains planted clique, planted biclique, star forests, and bounded-cover graphs as special cases, with lower and upper bounds that match up to polylogarithmic factors.

Core claim

The central claim is that the query budget needed to detect an arbitrary planted subgraph splits into three regimes, each with its own optimal algorithm: dense local witnesses make a scan test succeed at Q ≍ n²/N(H,Γ)^{2/v(H)}; high-degree hubs make a degree-on-a-cut test succeed at Q ≍ n³/κ(Γ); and counting queried edges alone detects the subgraph once the edge-count signal is large. The unifying tool is a vertex-cover reduction (Theorem 2) showing that a planted graph is undetectable whenever the subgraph induced by a vertex cover is undetectable and a certain weighted attachment term vanishes. Together these give near-optimal bounds, up to polylog factors, for cliques, bicliques, star for

What carries the argument

The load-bearing machinery is the vertex-cover reduction (Theorem 2), which compares the true planted model to an auxiliary model that plants only the subgraph induced by a vertex cover U. It expresses the chi-squared distance between transcript distributions as a sum over r of Θ_{r,n}ζ_{r,n}, where Θ_{r,n} counts how many residual-layer vertices share r common neighbors in the cover and ζ_{r,n} measures the query set's capacity to probe r cover vertices simultaneously. On the upper-bound side, the scan test is controlled by the concentration inequality of Lemma 2 for a uniformly random M-subset, which bounds the probability that no planted copy of a witness falls in the queried set; the deg

Load-bearing premise

The scan-test upper bounds rest on the concentration inequality of Lemma 2 for a uniformly random M-subset; the appendix proof of that lemma applies Jensen's inequality in the wrong direction, so the lemma is unproven as written and the upper bounds stand or fall with it.

What would settle it

Enumerate or Monte-Carlo check the inequality P(Z=0) ≤ exp(−µ²/(µ+∆)) for a specific family of subsets B_c under the uniform M-subset model; any instance where the true probability exceeds the bound would refute Lemma 2 and invalidate the scan-test upper bounds for cliques and bicliques.

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

If this is right

  • For clique-like graphs, detection is possible with Q ≈ (n²/k_n²) polylog(n) queries and impossible, by the edge-hit lower bound, when Q = o(n²/k_n²).
  • For star forests with squared degree sum S₂, weak detection is impossible at Q = o(n³/S₂), while the degree-on-a-cut test succeeds at Q ≈ (n³/κ) polylog(n), with κ within a log factor of S₂.
  • For sparse low-density structures (bounded-degree trees, paths, disjoint triangles) with k_n = o(n) vertices, detection is impossible even under full observation, so query access cannot help.
  • For complete bipartite graphs K_{a,b}, the balanced regime behaves like a clique (scan-optimal) and the unbalanced regime behaves like a star (degree-optimal), leaving only the intermediate a ≪ log n regime open.
  • In the full-observation limit, the three algorithms recover the known statistical thresholds, so the query model is a genuine restriction and not a new model in disguise.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the concentration inequality in Lemma 2 is repaired (the appendix's Jensen step has the wrong direction), the scan upper bounds for cliques and bicliques stand; otherwise those upper bounds would need a different second-moment argument, while the lower bounds and the degree-based upper bounds would remain intact.
  • The vertex-cover reduction suggests a natural adaptive analogue: in hub-dominated regimes, a handful of adaptive queries aimed at candidate high-degree vertices could plausibly reduce the budget by a log factor relative to the non-adaptive degree-on-a-cut test.
  • The unresolved a ≪ log n regime for complete bipartite graphs might be closed by a lower bound that uses the second-moment structure of Lemma 1 in a different way—perhaps weighting edge-intersections rather than counting them—since neither the edge-hit nor the bounded-cover argument is tight there.
  • The framework implicitly predicts that any planted family with a small vertex cover and concentrated high-degree mass will have query complexity n³/κ up to polylogs, which could be tested on new families such as subdivided stars or windmills.

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

2 major / 3 minor

Summary. The paper studies the non-adaptive edge-query complexity of detecting an arbitrary planted subgraph Γ_n in G(n,q), where the observer may query only Q_n vertex pairs before seeing responses. The authors propose two general lower-bound mechanisms (an edge-hit bound and a vertex-cover core-reduction bound) and three algorithmic upper bounds (witness scan, degree-on-a-cut, and edge count). They claim matching bounds up to polylogarithmic factors for clique-like graphs, hub-dominated/bounded-cover families, and balanced bicliques, and they formulate a unified scan-optimal scale Q_n ≍ n² / N(H_n,Γ_n)^{2/v_n} (Eq. (21)). The central result is Theorem 2, which reduces undetectability of the full planted graph to undetectability of a cover-induced core plus a weighted attachment-layer condition.

Significance. If the results are correct, this is a substantial contribution: it moves query-based planted-subgraph detection from bespoke examples (clique, dense subgraph) to a general theory for arbitrary Γ_n, and it identifies three structural mechanisms that determine query complexity. The lower-bound framework in Theorem 2 is genuinely general and the accompanying examples are informative. The paper also explicitly names the unresolved intermediate biclique regime 1 ≪ a_n ≪ log n, which is useful for follow-up work. The main caveat is that the scan-test upper bound rests on Lemma 2, whose proof in Appendix A.1 contains an invalid Jensen step and a sign error; until that lemma is correctly proved or cited, the upper-bound half of the central claim is not established as written. The issue appears standard and local, so the result is likely repairable within the scope of the paper.

major comments (2)
  1. [Appendix A.1, Eq. (335)–(338), Lemma 2] The proof of Lemma 2 is invalid. After Eq. (335), the text applies Jensen to the convex map x↦e^x and claims E[e^Y] ≤ e^{E[Y]}; this has the wrong direction (Jensen gives E[e^Y] ≥ e^{E[Y]}). Consequently the upper bound E[e^{−θZ+θ²Σ}] ≤ exp(−θμ+θ²Δ) is unjustified. There is also a sign error in the optimization line (338): with θ=μ/(μ+Δ), one gets −θμ+θ²Δ = −μ³/(μ+Δ)², which is ≥ −μ²/(μ+Δ), not ≤. Since Lemma 2 is the only mechanism controlling P(Z=0) for the scan test, Theorem 3 and the scan-based upper bounds in Corollaries 7–10 are not proven as written. The lemma is standard and likely repairable via Suen's inequality or a correct hypergeometric Janson proof, but the manuscript must supply such a proof or an external citation.
  2. [Section 5.1 / Theorem 3] Even apart from Lemma 2, the proof of Theorem 3 uses a slightly informal Janson setup. The lemma is stated for a deterministic family {B_c}; in the application, C is described as 'unlabeled copies' while the paper's global notation defines N(H,Γ) as labeled copies. This ambiguity matters for μ_n and Δ_n when H has nontrivial automorphisms (the t=v overlap term in Eq. (144)–(146) is omitted). The asymptotic polylog conclusions are probably unaffected, but the definitions should be made consistent.
minor comments (3)
  1. [Section 3.3, Eq. (32)] The statement that the three query algorithms 'reduce to the corresponding optimal full-observation tests' in the full-observation regime is informal. Please state precisely which theorem from [EH25] is being recovered and under which limiting conditions on M_n, m_d, and Q_n.
  2. [Section 6.4, proof of Corollary 4] The proof invokes a 'sharp full-observation lower bound for arbitrary planted graphs' to conclude that the matching core H_n is undetectable when μ(H_n)=1/2, |e(H_n)|=m_n=o(n), and d_max(H_n)²=o(n). Since this is a load-bearing external black box, please quote the exact theorem from [EH25] being used.
  3. [Notation, p. 4] N(H,Γ) is first defined as the number of labeled copies, but later uses (e.g., Corollary 9, where N(H_n,Γ_n)=binom(a_n,s_n)binom(b_n,s_n)) count unlabeled copies. Please fix the convention throughout, or explicitly divide by |Aut(H)| where needed.

Circularity Check

0 steps flagged

No circularity in the main derivation: lower and upper bounds are proved from the likelihood-ratio/chi-square framework and direct algorithm analyses. Only minor author-overlap citations appear in auxiliary full-observation comparisons.

full rationale

The central derivation is self-contained. Theorem 1 follows from a coupling/union-bound argument: if the query set misses the planted edges with high probability, the transcript is exactly null. Theorem 2 is a chi-square decomposition of the attachment layer versus an auxiliary core-planted model; it is a genuine reduction, not a definitional loop, because the core-undetectability condition (15) and the attachment bound (16) are separately checkable sufficient conditions. The scan upper bound (Theorem 3) computes Type-I error by a union bound and Type-II error by a hypergeometric Janson bound; the scale Q_n ≍ n^2/N(H_n,Γ_n)^{2/v_n} is an outcome of the moment computation, not an input fitted to match the lower bound. The degree-on-a-cut and edge-count upper bounds (Theorems 4 and 5) are direct Chernoff/Bernstein analyses. No fitted parameter is renamed as a prediction, and no uniqueness theorem is imported from the authors' earlier work. The only author-overlap citations, [EH25] and [Hul26], are used for context and for a known full-observation undetectability threshold in auxiliary corollaries (e.g., the matching core in Corollary 4 and the bounded-degree tree core in Corollary 5); these are external published results and do not feed back into the query-complexity theorems. For completeness, I flag a non-circularity concern: Appendix A.1's proof of Lemma 2 applies Jensen to the convex map x↦e^x in the wrong direction (E[e^X] ≤ e^{E[X]}), and Eq. (338) has a sign inconsistency. This is a correctness gap in the scan upper bound as written, but it is not a circular reduction, so it does not raise the circularity score.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

The paper introduces no fitted constants or new physical/mathematical entities; constants C1, C2, L are universal algorithmic constants. The main auxiliary assumption with a validity concern is Lemma 2.

axioms (4)
  • standard math Standard statistical inequalities: Le Cam's lemma, χ²-TV bound, Bernstein/Chernoff and hypergeometric concentration.
    Used throughout the lower and upper bound proofs; standard and correctly applied.
  • standard math Janson-type inequality for a uniform M-subset (Lemma 2).
    Load-bearing for the scan-test upper bound. The paper's proof in Appendix A.1 contains an invalid Jensen step (E[e^X]≤e^{E[X]} for convex e^X); the lemma is standard but needs a correct reference or proof.
  • standard math Full-observation planted-subgraph detection thresholds from [EH25].
    Used in Corollaries 4 and 5 and in the full-observation regime discussion to certify undetectability of small cores; an external published result, though sharing an author with this paper.
  • domain assumption Model assumptions: Γ_n arbitrary simple graphs without isolated vertices, |v(Γ_n)|≤n, q∈(0,1) fixed, uniform random embedding, non-adaptive queries.
    These define the setting; results are stated only for this dense non-adaptive query model.

pith-pipeline@v1.3.0-alltime-deepseek · 34034 in / 29691 out tokens · 289574 ms · 2026-08-01T18:59:14.351979+00:00 · methodology

0 comments
read the original abstract

The planted subgraph detection problem asks whether a random graph contains a hidden structured subgraph. In the classical formulation, the entire adjacency matrix is observed and one distinguishes between an Erd\H{o}s--R\'enyi random graph and one obtained by planting a copy of a prescribed graph inside an Erd\H{o}s--R\'enyi random graph. The statistical and computational limits of this problem under full observation are now well understood, even for arbitrary planted subgraphs. In this paper, we investigate an information-limited version of the problem in which the planted structure is an arbitrary sequence of graphs $\Gamma=(\Gamma_n)_{n\geq1}$, where $\Gamma_n$ is embedded in an ambient graph on $n$ vertices, but the observer does not have access to the full adjacency matrix. Instead, information is acquired through a limited number of non-adaptive edge queries. We study the minimum query complexity required for reliable detection. We derive general information-theoretic lower bounds and complementary algorithmic upper bounds on the query complexity as functions of the query budget and structural properties of the planted graph. The proposed algorithms exploit three distinct structural mechanisms: dense local motifs, high-degree vertices, and global edge density. We establish matching bounds, up to polylogarithmic factors, for several broad families of planted graphs, including clique-like, bounded-cover, and hub-dominated graph classes. Our framework substantially generalizes existing query-complexity results for planted clique and planted dense subgraph models, providing a unified treatment of arbitrary planted subgraphs under restricted graph access.

Figures

Figures reproduced from arXiv: 2607.17118 by Wasim Huleihel.

Figure 1
Figure 1. Figure 1: Illustration of the edge-query model. The graph contains a planted complete bipartite subgraph supported on the blue vertices, while the remaining vertices are colored red. Dashed black edges denote the queried vertex pairs, and gray edges denote unqueried edges. The algorithm selects all queried pairs in advance, before observing any responses from the edge oracle. 3 Main results In this section we presen… 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 · 32 linked inside Pith

  1. [1]

    Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices , Volume =

    Chen, Yudong and Xu, Jiaming , Date-Added =. Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices , Volume =. Journal of Machine Learning Research , Number =

  2. [2]

    In Proceedings of the 31st Conference On Learning Theory , volume =

    Reducibility and computational lower bounds for problems with planted sparse structure , author=. In Proceedings of the 31st Conference On Learning Theory , volume =

  3. [3]

    In Proceedings of The 28th Conference on Learning Theory , volume =

    Computational lower bounds for community detection on random graphs , author=. In Proceedings of The 28th Conference on Learning Theory , volume =

  4. [4]

    Proceedings of the Thirty Eighth Conference on Learning Theory , series =

    Detecting Arbitrary Planted Subgraphs in Random Graphs , author =. Proceedings of the Thirty Eighth Conference on Learning Theory , series =. 2025 , publisher =

    2025

  5. [5]

    IEEE Transactions on Signal and Information Processing over Networks , volume =

    Inferring Hidden Structures in Random Graphs , author=. IEEE Transactions on Signal and Information Processing over Networks , volume =

  6. [6]

    Proceedings of the Thirty-Second Conference on Learning Theory , pages =

    Universality of Computational Lower Bounds for Submatrix Detection , author =. Proceedings of the Thirty-Second Conference on Learning Theory , pages =. 2019 , volume =

    2019

  7. [7]

    Random Structures & Algorithms , volume=

    The number of spanning trees in graphs with a given degree sequence , author=. Random Structures & Algorithms , volume=. 1995 , publisher=

    1995

  8. [8]

    Testing k-wise and almost k-wise independence , Year =

    Alon, Noga and Andoni, Alexandr and Kaufman, Tali and Matulef, Kevin and Rubinfeld, Ronitt and Xie, Ning , Booktitle =. Testing k-wise and almost k-wise independence , Year =

  9. [9]

    Computational and statistical boundaries for submatrix localization in a large noisy matrix

    Cai, Tony and Liang, Tengyuan and Rakhlin, Alexander. Computational and statistical boundaries for submatrix localization in a large noisy matrix. Annals of Statistics. 2017

    2017

  10. [10]

    Sparse pca via covariance thresholding , Year =

    Deshpande, Yash and Montanari, Andrea , Booktitle =. Sparse pca via covariance thresholding , Year =

  11. [11]

    Large cliques elude the Metropolis process , Volume =

    Jerrum, Mark , Date-Added =. Large cliques elude the Metropolis process , Volume =. Random Structures & Algorithms , Number =

  12. [12]

    Finite exchangeable sequences , Year =

    Diaconis, Persi and Freedman, David , Date-Added =. Finite exchangeable sequences , Year =. The Annals of Probability , Pages =

  13. [13]

    Finding hidden cliques of size

    Deshpande, Yash and Montanari, Andrea , Date-Added =. Finding hidden cliques of size. Foundations of Computational Mathematics , Number =

  14. [14]

    Using More Data to Speed-up Training Time

    Shalev-Shwartz, Shai and Shamir, Ohad and Tromer, Eran , Booktitle =. Using More Data to Speed-up Training Time. , Year =

  15. [15]

    Bulletin of the American Mathematical Society , number =

    Robert Frucht , title =. Bulletin of the American Mathematical Society , number =

  16. [16]

    Minimax Rates of Estimation for Sparse PCA in High Dimensions

    Vu, Vincent Q and Lei, Jing , Booktitle =. Minimax Rates of Estimation for Sparse PCA in High Dimensions. , Volume =

  17. [17]

    Do semidefinite relaxations solve sparse PCA up to the information limit? , Volume =

    Krauthgamer, Robert and Nadler, Boaz and Vilenchik, Dan , Date-Added =. Do semidefinite relaxations solve sparse PCA up to the information limit? , Volume =. The Annals of Statistics , Number =

  18. [18]

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

    Baik, Jinho and Arous, G. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices , Volume =. The Annals of Probability , Number =

  19. [19]

    Regularized estimation of large covariance matrices , Year =

    Bickel, Peter J and Levina, Elizaveta , Date-Added =. Regularized estimation of large covariance matrices , Year =. The Annals of Statistics , Pages =

  20. [20]

    Adaptive thresholding for sparse covariance matrix estimation , Volume =

    Cai, Tony and Liu, Weidong , Date-Added =. Adaptive thresholding for sparse covariance matrix estimation , Volume =. Journal of the American Statistical Association , Number =

  21. [21]

    On information plus noise kernel random matrices , Volume =

    El Karoui, Noureddine , Date-Added =. On information plus noise kernel random matrices , Volume =. The Annals of Statistics , Number =

  22. [22]

    Optimal solutions for sparse principal component analysis , Volume =

    d'Aspremont, Alexandre and Bach, Francis and Ghaoui, Laurent El , Date-Added =. Optimal solutions for sparse principal component analysis , Volume =. Journal of Machine Learning Research , Number =

  23. [23]

    Unpublished manuscript , Title =

    Johnstone, Iain M and Lu, Arthur Yu , Date-Added =. Unpublished manuscript , Title =

  24. [24]

    Asymptotics of sample eigenstructure for a large dimensional spiked covariance model , Year =

    Paul, Debashis , Date-Added =. Asymptotics of sample eigenstructure for a large dimensional spiked covariance model , Year =. Statistica Sinica , Pages =

  25. [25]

    Detecting positive correlations in a multivariate sample , Volume =

    Arias-Castro, Ery and Bubeck, S. Detecting positive correlations in a multivariate sample , Volume =. Bernoulli , Number =

  26. [26]

    Detection of correlations , Volume =

    Arias-Castro, Ery and Bubeck, S. Detection of correlations , Volume =. The Annals of Statistics , Number =

  27. [27]

    On combinatorial testing problems , Volume =

    Addario-Berry, Louigi and Broutin, Nicolas and Devroye, Luc and Lugosi, G. On combinatorial testing problems , Volume =. The Annals of Statistics , Number =

  28. [28]

    Finding a large hidden clique in a random graph , Volume =

    Alon, Noga and Krivelevich, Michael and Sudakov, Benny , Date-Added =. Finding a large hidden clique in a random graph , Volume =. Random Structures and Algorithms , Number =

  29. [29]

    High-dimensional analysis of semidefinite relaxations for sparse principal components , Volume =

    Amini, Arash A and Wainwright, Martin J , Date-Added =. High-dimensional analysis of semidefinite relaxations for sparse principal components , Volume =. The Annals of Statistics , Number =

  30. [30]

    Detection of a sparse submatrix of a high-dimensional noisy matrix , Volume =

    Butucea, Cristina and Ingster, Yuri I , Date-Added =. Detection of a sparse submatrix of a high-dimensional noisy matrix , Volume =. Bernoulli , Number =

  31. [31]

    Computational and statistical tradeoffs via convex relaxation , Volume =

    Chandrasekaran, Venkat and Jordan, Michael I , Date-Added =. Computational and statistical tradeoffs via convex relaxation , Volume =. Proceedings of the National Academy of Sciences , Number =

  32. [32]

    A Direct Formulation for Sparse PCA Using Semidefinite Programming

    d'Aspremont, Alexandre and El Ghaoui, Laurent and Jordan, Michael I and Lanckriet, Gert RG , Date-Added =. A Direct Formulation for Sparse PCA Using Semidefinite Programming. , Volume =. SIAM review , Number =

  33. [33]

    Optimal rates of convergence for covariance matrix estimation , Volume =

    Cai, T Tony and Zhang, Cun-Hui and Zhou, Harrison H , Date-Added =. Optimal rates of convergence for covariance matrix estimation , Volume =. The Annals of Statistics , Number =

  34. [34]

    On consistency and sparsity for principal components analysis in high dimensions , Volume =

    Johnstone, Iain M and Lu, Arthur Yu , Date-Added =. On consistency and sparsity for principal components analysis in high dimensions , Volume =. Journal of the American Statistical Association , Number =

  35. [35]

    arXiv preprint arXiv:1604.07449 , Title =

    Arias-Castro, Ery and Liu, Yuchao , Date-Added =. arXiv preprint arXiv:1604.07449 , Title =

    Pith/arXiv arXiv

  36. [36]

    Wein , Journal =

    Abhishek Dhawan, Cheng Mao, Alexander S. Wein , Journal =. Detection of Dense Subhypergraphs by Low-Degree Polynomials , Year =

  37. [37]

    Resource Allocation for Statistical Estimation , Volume =

    Berthet, Quentin and Chandrasekaran, Venkat , Date-Added =. Resource Allocation for Statistical Estimation , Volume =. Proceedings of the IEEE , Number =

  38. [38]

    arXiv preprint arXiv:1607.02435 , Title =

    Flammarion, Nicolas and Mao, Cheng and Rigollet, Philippe , Date-Added =. arXiv preprint arXiv:1607.02435 , Title =

    Pith/arXiv arXiv

  39. [39]

    Volume ratio, sparsity, and minimaxity under unitarily invariant norms , Volume =

    Ma, Zongming and Wu, Yihong , Date-Added =. Volume ratio, sparsity, and minimaxity under unitarily invariant norms , Volume =. IEEE Transactions on Information Theory , Number =

  40. [40]

    Sparse PCA via Covariance Thresholding , Volume =

    Deshpande, Yash and Montanari, Andrea , Date-Added =. Sparse PCA via Covariance Thresholding , Volume =. Journal of Machine Learning Research , Pages =

  41. [41]

    Lower bounds on the performance of polynomial-time algorithms for sparse linear regression

    Zhang, Yuchen and Wainwright, Martin J and Jordan, Michael I , Booktitle =. Lower bounds on the performance of polynomial-time algorithms for sparse linear regression. , Year =

  42. [42]

    Sparse principal component analysis and iterative thresholding , Volume =

    Ma, Zongming , Date-Added =. Sparse principal component analysis and iterative thresholding , Volume =. The Annals of Statistics , Number =

  43. [43]

    arXiv preprint arXiv:1311.0851 , Title =

    Donoho, David L and Gavish, Matan and Johnstone, Iain M , Date-Added =. arXiv preprint arXiv:1311.0851 , Title =

    Pith/arXiv arXiv

  44. [44]

    arXiv preprint arXiv:1509.07269 , Title =

    Johnstone, Iain M and Onatski, Alexei , Date-Added =. arXiv preprint arXiv:1509.07269 , Title =

    Pith/arXiv arXiv

  45. [45]

    Joint density of eigenvalues in spiked multivariate models , Volume =

    Dharmawansa, Prathapasinghe and Johnstone, Iain M , Date-Added =. Joint density of eigenvalues in spiked multivariate models , Volume =. Stat , Number =

  46. [46]

    Testing for high-dimensional geometry in random graphs , Year =

    Bubeck, S. Testing for high-dimensional geometry in random graphs , Year =. Random Structures & Algorithms , Publisher =

  47. [47]

    Minimax estimation in sparse canonical correlation analysis , Volume =

    Gao, Chao and Ma, Zongming and Ren, Zhao and Zhou, Harrison H , Date-Added =. Minimax estimation in sparse canonical correlation analysis , Volume =. The Annals of Statistics , Number =

  48. [48]

    Sum-of-squares lower bounds for sparse pca , Year =

    Ma, Tengyu and Wigderson, Avi , Booktitle =. Sum-of-squares lower bounds for sparse pca , Year =

  49. [49]

    ETH hardness for densest-k-subgraph with perfect completeness , Year =

    Braverman, Mark and Ko, Young Kun and Rubinstein, Aviad and Weinstein, Omri , Booktitle =. ETH hardness for densest-k-subgraph with perfect completeness , Year =

  50. [50]

    On the limitation of spectral methods: From the gaussian hidden clique problem to rank-one perturbations of gaussian tensors , Year =

    Montanari, Andrea and Reichman, Daniel and Zeitouni, Ofer , Booktitle =. On the limitation of spectral methods: From the gaussian hidden clique problem to rank-one perturbations of gaussian tensors , Year =

  51. [51]

    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 =

  52. [52]

    Computational Limits for Matrix Completion

    Hardt, Moritz and Meka, Raghu and Raghavendra, Prasad and Weitz, Benjamin , Booktitle =. Computational Limits for Matrix Completion. , Year =

  53. [53]

    Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow , Volume =

    Cai, T Tony and Li, Xiaodong and Ma, Zongming , Date-Added =. Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow , Volume =. The Annals of Statistics , Number =

  54. [54]

    Proceedings of The 28th Conference on Learning Theory , pages =

    Computational Lower Bounds for Community Detection on Random Graphs , author =. Proceedings of The 28th Conference on Learning Theory , pages =. 2015 , volume =

    2015

  55. [55]

    Optimal estimation and rank detection for sparse spiked covariance matrices , Volume =

    Cai, Tony and Ma, Zongming and Wu, Yihong , Date-Added =. Optimal estimation and rank detection for sparse spiked covariance matrices , Volume =. Probability theory and related fields , Number =

  56. [56]

    Computational barriers in minimax submatrix detection , Volume =

    Ma, Zongming and Wu, Yihong , Date-Added =. Computational barriers in minimax submatrix detection , Volume =. Annals of Statistics , Number =

  57. [57]

    Estimation of functionals of sparse covariance matrices , Volume =

    Fan, Jianqing and Rigollet, Philippe and Wang, Weichen , Date-Added =. Estimation of functionals of sparse covariance matrices , Volume =. Annals of statistics , Number =

  58. [58]

    Average-case hardness of RIP certification , Year =

    Wang, Tengyao and Berthet, Quentin and Plan, Yaniv , Booktitle =. Average-case hardness of RIP certification , Year =

  59. [59]

    Statistical and computational trade-offs in estimation of sparse principal components , Volume =

    Wang, Tengyao and Berthet, Quentin and Samworth, Richard J , Date-Added =. Statistical and computational trade-offs in estimation of sparse principal components , Volume =. The Annals of Statistics , Number =

  60. [60]

    Optimal detection of sparse principal components in high dimension , Volume =

    Berthet, Quentin and Rigollet, Philippe , Date-Added =. Optimal detection of sparse principal components in high dimension , Volume =. The Annals of Statistics , Number =

  61. [61]

    Proceedings of the 26th Annual Conference on Learning Theory , pages =

    Complexity Theoretic Lower Bounds for Sparse Principal Component Detection , author =. Proceedings of the 26th Annual Conference on Learning Theory , pages =. 2013 , volume =

    2013

  62. [62]

    Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting , Volume =

    Wainwright, Martin J , Date-Added =. Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting , Volume =. Information Theory, IEEE Transactions on , Number =

  63. [63]

    Fourier pca , Year =

    Goyal, Naveen and Vempala, Santosh and Xiao, Ying , Booktitle =. Fourier pca , Year =

  64. [64]

    Improved approximation of linear threshold functions , Volume =

    Diakonikolas, Ilias and Servedio, Rocco A , Date-Added =. Improved approximation of linear threshold functions , Volume =. computational complexity , Number =

  65. [65]

    , Date-Added =

    Niedermeier, R. , Date-Added =. Invitation to fixed-parameter algorithms , Year =

  66. [66]

    CoSaMP: Iterative signal recovery from incomplete and inaccurate samples , Volume =

    Needell, Deanna and Tropp, Joel A , Date-Added =. CoSaMP: Iterative signal recovery from incomplete and inaccurate samples , Volume =. Applied and Computational Harmonic Analysis , Number =

  67. [67]

    Subspace pursuit for compressive sensing signal reconstruction , Volume =

    Dai, Wei and Milenkovic, Olgica , Date-Added =. Subspace pursuit for compressive sensing signal reconstruction , Volume =. Information Theory, IEEE Transactions on , Number =

  68. [68]

    Adaptive forward-backward greedy algorithm for learning sparse representations , Volume =

    Zhang, Tong , Date-Added =. Adaptive forward-backward greedy algorithm for learning sparse representations , Volume =. Information Theory, IEEE Transactions on , Number =

  69. [69]

    On the consistency of feature selection using greedy least squares regression , Year =

    Zhang, Tong , Booktitle =. On the consistency of feature selection using greedy least squares regression , Year =

  70. [70]

    Atomic decomposition by basis pursuit , Volume =

    Chen, Scott Shaobing and Donoho, David L and Saunders, Michael A , Date-Added =. Atomic decomposition by basis pursuit , Volume =. SIAM journal on scientific computing , Number =

  71. [71]

    Greedy approximation , Year =

    Temlyakov, Vladimir , Date-Added =. Greedy approximation , Year =

  72. [72]

    Additive logistic regression: a statistical view of boosting (with discussion and a rejoinder by the authors) , Volume =

    Friedman, Jerome and Hastie, Trevor and Tibshirani, Robert , Date-Added =. Additive logistic regression: a statistical view of boosting (with discussion and a rejoinder by the authors) , Volume =. The annals of statistics , Number =

  73. [73]

    High dimensional variable selection , Volume =

    Wasserman, Larry and Roeder, Kathryn , Date-Added =. High dimensional variable selection , Volume =. Annals of statistics , Number =

  74. [74]

    , Date-Added =

    Toshiyuki, T. , Date-Added =. Mean-field theory of Boltzmann machine learning , Volume =. Physical Review E , Number =

  75. [75]

    and Banavar, J

    Lezon, T. and Banavar, J. and Cieplak, M. and Maritan, A. and Fedoroff, N. , Date-Added =. Using the principle of entropy maximization to infer genetic interaction networks from gene expression patterns , Volume =. Proceedings of the National Academy of Sciences , Number =

  76. [76]

    and Ollion, C

    Aurell, E. and Ollion, C. and Roudi, Y. , Date-Added =. Dynamics and performance of susceptibility propagation on synthetic data , Volume =. The European Physical Journal B-Condensed Matter and Complex Systems , Number =

  77. [77]

    Constraint satisfaction problems and neural networks: A statistical physics perspective , Volume =

    M. Constraint satisfaction problems and neural networks: A statistical physics perspective , Volume =. Journal of Physiology-Paris , Number =

  78. [78]

    , Date-Added =

    Ricci-Tersenghi, F. , Date-Added =. The. Journal of Statistical Mechanics: Theory and Experiment , Number =

  79. [79]

    and Sejnowski, T

    Hinton, G. and Sejnowski, T. , Date-Added =. Learning and relearning in. MIT Press , Number =

  80. [80]

    and Hinton, G

    Ackley, D. and Hinton, G. and Sejnowski, T. , Date-Added =. A learning algorithm for boltzmann machines* , Volume =. Cognitive science , Number =

Showing first 80 references.