Pith. sign in

REVIEW 2 major objections 3 minor 300 references

Fundamental Limits of Query-Based Subgraph Detection

T0 review · 2 major / 3 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

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

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

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

Wasim Huleihel This is my paper
classification math.STcs.ITmath.ITstat.TH MSC 62C2062F0305C80
keywords plantedsubgraphdetectionnon-adaptiveedgequeriesquerycomplexityrandomgraphvertexcoverscantestdegree-on-a-cuthypothesistesting
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 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.

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

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

Extended reading notes

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

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.

Editorial extensions

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.

Reading between the lines

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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 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 · score 2.0 of 10

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.

Assumptions & free parameters 0 free parameters · 4 assumptions · 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.

assumptions (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.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fundamental Limits of Query-Based Subgraph Detection." pith.science (2026). https://pith.science/paper/MO6DOIEK

@misc{pith2026260717118,
  author       = {Pith},
  title        = {Pith review of: Fundamental Limits of Query-Based Subgraph Detection},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MO6DOIEK}},
  note         = {Machine review of arXiv:2607.17118}
}
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 the authors.

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 present our main… view at source ↗

Discussion (0). Sign in to comment.

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 =

Show all 300 references
  1. [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

  2. [10]

    Sparse pca via covariance thresholding , Year =

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

  3. [11]

    Large cliques elude the Metropolis process , Volume =

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

  4. [12]

    Finite exchangeable sequences , Year =

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

  5. [13]

    Finding hidden cliques of size

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

  6. [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 =

  7. [15]

    Bulletin of the American Mathematical Society , number =

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

  8. [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 =

  9. [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 =

  10. [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 =

  11. [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 =

  12. [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 =

  13. [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 =

  14. [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 =

  15. [23]

    Unpublished manuscript , Title =

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

  16. [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 =

  17. [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 =

  18. [26]

    Detection of correlations , Volume =

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

  19. [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 =

  20. [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 =

  21. [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 =

  22. [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 =

  23. [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 =

  24. [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 =

  25. [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 =

  26. [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 =

  27. [35]

    arXiv preprint arXiv:1604.07449 , Title =

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

    arXiv

  28. [36]

    Wein , Journal =

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

  29. [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 =

  30. [38]

    arXiv preprint arXiv:1607.02435 , Title =

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

    arXiv

  31. [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 =

  32. [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 =

  33. [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 =

  34. [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 =

  35. [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 =

    arXiv

  36. [44]

    arXiv preprint arXiv:1509.07269 , Title =

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

    arXiv

  37. [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 =

  38. [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 =

  39. [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 =

  40. [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 =

  41. [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 =

  42. [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 =

  43. [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 =

  44. [52]

    Computational Limits for Matrix Completion

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

  45. [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 =

  46. [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

  47. [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 =

  48. [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 =

  49. [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 =

  50. [58]

    Average-case hardness of RIP certification , Year =

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

  51. [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 =

  52. [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 =

  53. [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

  54. [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 =

  55. [63]

    Fourier pca , Year =

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

  56. [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 =

  57. [65]

    , Date-Added =

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

  58. [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 =

  59. [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 =

  60. [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 =

  61. [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 =

  62. [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 =

  63. [71]

    Greedy approximation , Year =

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

  64. [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 =

  65. [73]

    High dimensional variable selection , Volume =

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

  66. [74]

    , Date-Added =

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

  67. [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 =

  68. [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 =

  69. [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 =

  70. [78]

    , Date-Added =

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

  71. [79]

    and Sejnowski, T

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

  72. [80]

    and Hinton, G

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

  73. [81]

    Evolutionary information for specifying a protein fold , Volume =

    Socolich, Michael and Lockless, Steve W and Russ, William P and Lee, Heather and Gardner, Kevin H and Ranganathan, Rama , Date-Added =. Evolutionary information for specifying a protein fold , Volume =. Nature , Number =

  74. [82]

    and Monasson, R

    Sessak, V. and Monasson, R. , Date-Added =. Small-correlation expansions for the inverse. Journal of Physics A: Mathematical and Theoretical , Number =

  75. [83]

    and Walczak, A

    Mora, T. and Walczak, A. and Bialek, W. and Callan, C. , Date-Added =. Maximum entropy models for antibody diversity , Volume =. Proceedings of the National Academy of Sciences , Number =

  76. [84]

    and Aurell, E

    Roudi, Y. and Aurell, E. and Hertz, J. , Date-Added =. Statistical physics of pairwise probability models , Volume =. Frontiers in computational neuroscience , Publisher =

  77. [85]

    and Ricci-Tersenghi, F

    Decelle, A. and Ricci-Tersenghi, F. , Date-Added =. Pseudolikelihood Decimation Algorithm Improving the Inference of the Interaction Network in a General Class of Ising Models , Volume =. Physical review letters , Number =

  78. [86]

    Advanced mean field methods: Theory and practice , Year =

    Opper, Manfred and Saad, David , Date-Added =. Advanced mean field methods: Theory and practice , Year =

  79. [87]

    and White, R

    Weigt, M. and White, R. and Szurmant, H. and Hoch, J. and Hwa, T. , Date-Added =. Identification of direct residue contacts in protein--protein interaction by message passing , Volume =. Proceedings of the National Academy of Sciences , Number =

  80. [88]

    and Leibler, S

    Cocco, S. and Leibler, S. and Monasson, R. , Date-Added =. Neuronal couplings between retinal ganglion cells inferred by efficient inverse statistical physics methods , Volume =. Proceedings of the National Academy of Sciences , Number =

  81. [89]

    and Berry, M

    Schneidman, E. and Berry, M. and Segev, R. and Bialek, W. , Date-Added =. Weak pairwise correlations imply strongly correlated network states in a neural population , Volume =. Nature , Number =

  82. [90]

    and Samorodnitsky, A

    Kalai, A. and Samorodnitsky, A. and Teng, S.H. , Booktitle =. Learning and smoothed analysis , Year =

  83. [91]

    , Date-Added =

    Brush, S. , Date-Added =. Rev. Mod. Phys. , Month =

  84. [92]

    , Date-Added =

    Ising, E. , Date-Added =. Beitrag zur theorie des ferromagnetismus , Volume =. Zeitschrift f

  85. [93]

    , Date-Added =

    Talagrand, M. , Date-Added =. Mean field models for spin glasses , Year =

  86. [94]

    , Booktitle =

    Valiant, G. , Booktitle =. Finding correlations in subquadratic time, with applications to learning parities and juntas , Year =

  87. [95]

    and Srikant, R

    Wu, R. and Srikant, R. and Ni, J. , Date-Added =. Learning loosely connected Markov random fields , Volume =. Stochastic Systems , Number =

  88. [96]

    and Wainwright, M

    Ravikumar, P. and Wainwright, M. and Raskutti, G. and Yu, B. , Date-Added =. High-dimensional covariance estimation by minimizing _1 -penalized log-determinant divergence , Volume =. Electronic Journal of Statistics , Pages =

  89. [97]

    and Ravikumar, P

    Negahban, S. and Ravikumar, P. and Wainwright, M. and Yu, B. , Date-Added =. A Unified Framework for High-Dimensional Analysis of. Statistical Science , Number =

  90. [98]

    and B\"uhlmann, P

    Meinshausen, N. and B\"uhlmann, P. , Date-Added =. High-dimensional graphs and variable selection with the lasso , Year =. The Annals of Statistics , Pages =

  91. [99]

    , Date-Added =

    O'Donnell, R. , Date-Added =. Analysis of boolean functions , Year =

  92. [100]

    and Jerrum, M

    Goldberg, L. and Jerrum, M. and Paterson, M. , Date-Added =. The computational complexity of two-state spin systems , Volume =. Random Structures & Algorithms , Number =

  93. [101]

    and Srivastava, P

    Sinclair, A. and Srivastava, P. and Yin, Y. , Booktitle =. Spatial mixing and approximation algorithms for graphs with bounded connective constant , Year =

  94. [102]

    and Srivastava, P

    Sinclair, A. and Srivastava, P. and Thurley, M. , Date-Added =. Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs , Volume =. Journal of Statistical Physics , Number =

  95. [103]

    , Date-Added =

    Lauritzen, S. , Date-Added =. Graphical models , Year =

  96. [104]

    and Thomas, J

    Cover, T. and Thomas, J. , Date-Added =. Elements of information theory , Year =

  97. [105]

    and Meka, R

    Klivans, A. and Meka, R. , Date-Added =. arXiv preprint arXiv:1301.0820 , Title =

    arXiv

  98. [106]

    and Klivans, A

    Kane, D. and Klivans, A. and Meka, R. , Booktitle =. Learning halfspaces under log-concave densities: Polynomial approximations and moment matching , Year =

  99. [107]

    and Tan, V

    Anandkumar, A. and Tan, V. and Huang, F. and Willsky, A. , Date-Added =. High-dimensional. JMLR , Number =

  100. [108]

    and Hastie, T

    Friedman, J. and Hastie, T. and Tibshirani, R. , Date-Added =. Sparse inverse covariance estimation with the graphical lasso , Volume =. Biostatistics , Number =

  101. [109]

    and Hsu, D

    Anandkumar, A. and Hsu, D. and Kakade, S. , Date-Added =. arXiv preprint arXiv:1203.0683 , Title =

    arXiv

  102. [110]

    and Sinha, K

    Belkin, M. and Sinha, K. , Booktitle =. Polynomial learning of distribution families , Year =

  103. [111]

    and Valiant, G

    Moitra, A. and Valiant, G. , Booktitle =. Settling the polynomial learnability of mixtures of

  104. [112]

    arXiv , Author =:1409.3821 , Journal =

    arXiv

  105. [113]

    and Gamarnik, D

    Bresler, G. and Gamarnik, D. and Shah, D. , Booktitle =. Hardness of parameter estimation in graphical models , Year =

  106. [114]

    and Van Roy, B

    Russo, D. and Van Roy, B. , Date-Added =. Learning to Optimize Via Information Directed Sampling , Year =

  107. [115]

    and Olivieri, E

    Martinelli, F. and Olivieri, E. , Date-Added =. Approach to equilibrium of. Comm. in Mathematical Physics , Number =

  108. [116]

    and Sinclair, A

    Dyer, M. and Sinclair, A. and Vigoda, E. and Weitz, D. , Date-Added =. Mixing in time and space for lattice spin systems: A combinatorial view , Volume =. Random Structures & Algorithms , Number =

  109. [117]

    and Zegarlinski, B

    Stroock, D. and Zegarlinski, B. , Date-Added =. The logarithmic. Comm. in Mathematical Physics , Number =

  110. [118]

    and Ganapathi, V

    Lee, S. and Ganapathi, V. and Koller, D. , Booktitle =. Efficient Structure Learning of. 2006 , Bdsk-File-1 =

    2006

  111. [119]

    and Sokal, A

    Salas, S. and Sokal, A. , Date-Added =. Absence of phase transition for antiferromagnetic. Journal of Statistical Physics , Number =

  112. [120]

    and Shlosman, S

    Dobrushin, R. and Shlosman, S. , Booktitle =. Constructive criterion for the uniqueness of

  113. [121]

    , Date-Added =

    Dobrushin, R. , Date-Added =. Prescribing a system of random variables by conditional distributions , Volume =. Theory of Probability & Its Applications , Number =

  114. [122]

    , Date-Added =

    Gamarnik, D. , Date-Added =. Tutorials in Operations Research, INFORMS , Title =

  115. [123]

    and Gamarnik, D

    Bresler, G. and Gamarnik, D. and Shah, D. , Booktitle =. Structure learning of antiferromagnetic

  116. [124]

    and Huang, F

    Anandkumar, A. and Huang, F. and Hsu, D. and Kakade, S. , Booktitle =. Learning mixtures of tree graphical models , Year =

  117. [125]

    , Booktitle =

    Srebro, N. , Booktitle =. Maximum likelihood bounded tree-width

  118. [126]

    , Booktitle =

    Dasgupta, S. , Booktitle =. Learning polytrees , Year =

  119. [127]

    and Liu, C

    Chow, C. and Liu, C. , Date-Added =. Approximating discrete probability distributions with dependence trees , Volume =. IEEE Trans. on Info. Theory , Number =

  120. [128]

    Consistent estimation of the basic neighborhood of

    Csisz. Consistent estimation of the basic neighborhood of. Annals of Stat. , Pages =

  121. [129]

    and Koller, D

    Abbeel, P. and Koller, D. and Ng, A. , Date-Added =. Learning factor graphs in polynomial time and sample complexity , Year =. JMLR , Publisher =

  122. [130]

    On a lemma of

    Erd. On a lemma of. Bulletin of the American Mathematical Society , Number =

  123. [131]

    and Vu, V

    Tao, T. and Vu, V. , Date-Added =. Additive combinatorics , Volume =

  124. [132]

    Tao , Date-Added =

    T. Tao , Date-Added =

  125. [133]

    , Booktitle =

    Moser, R. , Booktitle =. A constructive proof of the

  126. [134]

    Lectures on 0/1-polytopes , Year =

    Ziegler, G. Lectures on 0/1-polytopes , Year =. Polytopes---combinatorics and computation , Date-Added =

  127. [135]

    Marginals-to-Models Reducibility , Year =

    Roughgarden, Tim and Kearns, Michael , Booktitle =. Marginals-to-Models Reducibility , Year =

  128. [136]

    On the Use of Variational Inference for Learning Discrete Graphical Model , Year =

    Yang, Eunho and Ravikumar, Pradeep K , Booktitle =. On the Use of Variational Inference for Learning Discrete Graphical Model , Year =

  129. [137]

    Hardness of low delay network scheduling , Volume =

    Shah, Devavrat and Tse, David NC and Tsitsiklis, John N , Date-Added =. Hardness of low delay network scheduling , Volume =. Information Theory, IEEE Transactions on , Number =

  130. [138]

    Convex functions: constructions, characterizations and counterexamples , Year =

    Borwein, Jonathan M and Vanderwerff, Jon D , Date-Added =. Convex functions: constructions, characterizations and counterexamples , Year =

  131. [139]

    and Shalev-Shwartz, Shai and Tewari, Ambuj , Date-Added =

    Kakade, Sham M. and Shalev-Shwartz, Shai and Tewari, Ambuj , Date-Added =. Regularization Techniques for Learning with Matrices , Url =. J. Mach. Learn. Res. , Keywords =. 2012 , Bdsk-Url-1 =

    2012

  132. [140]

    Convex analysis , Volume =

    Rockafellar, R Tyrrell , Date-Added =. Convex analysis , Volume =

  133. [141]

    Distributed random access algorithm: scheduling and congestion control , Volume =

    Jiang, Libin and Shah, Devavrat and Shin, Jinwoo and Walrand, Jean , Date-Modified =. Distributed random access algorithm: scheduling and congestion control , Volume =. IEEE Trans. on Info. Theory , Number =

  134. [142]

    Approximate inference using planar graph decomposition , Volume =

    Jaakkola, Amir Globerson Tommi , Booktitle =. Approximate inference using planar graph decomposition , Volume =

  135. [143]

    Local rules for global MAP: When do they work , Volume =

    Jung, Kyomin and Kohli, Pushmeet and Shah, Devavrat , Journal =. Local rules for global MAP: When do they work , Volume =

  136. [144]

    Georgii, H. O. , Publisher =. Gibbs measures and phase transitions , Year =

  137. [145]

    , Publisher =

    Simon, B. , Publisher =. The statistical mechanics of lattice gases,

  138. [146]

    Local algorithms for approximate inference in minor-excluded graphs , Year =

    Jung, Kyomin and Shah, Devavrat , Booktitle =. Local algorithms for approximate inference in minor-excluded graphs , Year =

  139. [147]

    Excluded minors, network decomposition, and multicommodity flow , Year =

    Klein, Philip and Plotkin, Serge A and Rao, Satish , Booktitle =. Excluded minors, network decomposition, and multicommodity flow , Year =

  140. [148]

    , Booktitle =

    Weitz, D. , Booktitle =. Counting independent sets up to the tree threshold , Year =

  141. [149]

    and Katz, D

    Gamarnik, D. and Katz, D. , Booktitle =. Correlation decay and deterministic FPTAS for counting list-colorings of a graph , Year =

  142. [150]

    Probabilistic Reasoning in Intelligent Systems: Networks of Plausble Inference , Year =

    Pearl, Judea , Publisher =. Probabilistic Reasoning in Intelligent Systems: Networks of Plausble Inference , Year =

  143. [151]

    Computational complexity , Year =

    Papadimitriou, Christos H , Date-Added =. Computational complexity , Year =

  144. [152]

    and Laurent, M

    Deza, M. and Laurent, M. , Date-Added =. Geometry of cuts and metrics , Year =

  145. [153]

    and Stefankovic, D

    Galanis, A. and Stefankovic, D. and Vigoda, E. , Date-Added =. arXiv preprint arXiv:1203.2226 , Title =. 2012 , Bdsk-File-1 =

    2012 arXiv

  146. [154]

    , Booktitle =

    Sly, A. , Booktitle =. Computational transition at the uniqueness threshold , Year =

  147. [155]

    and Frieze, A

    Dyer, M. and Frieze, A. and Jerrum, M. , Date-Added =. On counting independent sets in sparse graphs , Volume =. SIAM Journal on Computing , Number =. 2002 , Bdsk-File-1 =

    2002

  148. [156]

    and Vigoda, E

    Luby, M. and Vigoda, E. , Date-Added =. Fast convergence of the Glauber dynamics for sampling independent sets , Volume =. Random Structures and Algorithms , Number =. 1999 , Bdsk-File-1 =

    1999

  149. [157]

    and Sinclair, A

    Jerrum, M. and Sinclair, A. , Date-Added =. Polynomial-time approximation algorithms for the. SIAM Journal on computing , Number =. 1993 , Bdsk-File-1 =

    1993

  150. [158]

    and Vertigan, D

    Jaeger, F. and Vertigan, D. and Welsh, D. , Date-Added =. On the computational complexity of the Jones and Tutte polynomials , Volume =. Math. Proc. Cambridge Philos. Soc , Number =

  151. [159]

    On the computational complexity of Ising spin glass models , Volume =

    Barahona, Francisco , Date-Added =. On the computational complexity of Ising spin glass models , Volume =. Journal of Physics A: Mathematical and General , Number =. 1982 , Bdsk-File-1 =

    1982

  152. [160]

    Solving convex programs by random walks , Volume =

    Bertsimas, Dimitris and Vempala, Santosh , Date-Added =. Solving convex programs by random walks , Volume =. Journal of the ACM , Number =. 2004 , Bdsk-File-1 =

    2004

  153. [161]

    , Booktitle =

    Istrail, S. , Booktitle =. Statistical mechanics, three-dimensionality and. 2000 , Bdsk-File-1 =

    2000

  154. [162]

    More data means less inference: A pseudo-max approach to structured learning , Year =

    Sontag, David and Meshi, Ofer and Jaakkola, Tommi and Globerson, Amir , Date-Added =. More data means less inference: A pseudo-max approach to structured learning , Year =

  155. [163]

    Approximate inference using planar graph decomposition , Volume =

    Jaakkola, Tommi and Globerson, Amir , Booktitle =. Approximate inference using planar graph decomposition , Volume =. 2007 , Bdsk-File-1 =

    2007

  156. [164]

    Nonlinear programming , Year =

    Bertsekas, Dimitri P , Date-Added =. Nonlinear programming , Year =

  157. [165]

    On Learning Discrete Graphical Models Using Greedy Methods , Bdsk-File-1 =

    Jalali, Ali and Johnson, Christopher C and Ravikumar, Pradeep , Date-Added =. On Learning Discrete Graphical Models Using Greedy Methods , Bdsk-File-1 =

  158. [166]

    and Ravikumar, P

    Jalali, A. and Ravikumar, P. and Vasuki, V. and Sanghavi, S. , Booktitle =. On learning discrete graphical models using group-sparse regularization , Volume =

  159. [167]

    Graph model selection using maximum likelihood , Year =

    Bez. Graph model selection using maximum likelihood , Year =. Proceedings of the 23rd international conference on Machine learning , Date-Added =

  160. [168]

    Random gradient-free minimization of convex functions , Year =

    Nesterov, Yurii , Date-Added =. Random gradient-free minimization of convex functions , Year =

  161. [169]

    A new class of upper bounds on the log partition function , Volume =

    Wainwright, Martin J and Jaakkola, Tommi S and Willsky, Alan S , Date-Added =. A new class of upper bounds on the log partition function , Volume =. Information Theory, IEEE Transactions on , Number =. 2005 , Bdsk-File-1 =

    2005

  162. [170]

    and Wainwright, Martin J." , Date-Added =

    Wainwright, Martin J. and Wainwright, Martin J." , Date-Added =. Tree-reweighted belief propagation algorithms and approximate ML estimation via pseudo-moment matching , Year =. doi:10.1.1.68.45 , Journal =

  163. [171]

    Necessary conditions for consistent set-based graphical model selection , Year =

    Vats, Divyanshu and Moura, Jos. Necessary conditions for consistent set-based graphical model selection , Year =. Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on , Date-Added =

    2011

  164. [172]

    Santhanam, N. P. and Wainwright, M. J. , Date-Added =. Information-theoretic limits of selecting binary graphical models in high dimensions , Volume =. IEEE Trans. on Info. Theory , Number =

  165. [173]

    and Sun, N

    Sly, A. and Sun, N. , Booktitle =. The computational hardness of counting in two-spin models on d-regular graphs , Year =

  166. [174]

    and Srebro, N

    Karger, D. and Srebro, N. , Booktitle =. Learning

  167. [175]

    and Netrapalli, P

    Johnson, J.K. and Netrapalli, P. and Chertkov, M. , Date-Added =. arXiv preprint arXiv:1011.3494 , Title =

    arXiv

  168. [176]

    and Jordan, M.I

    Wainwright, M.J. and Jordan, M.I. , Date-Added =. Graphical models, exponential families, and variational inference , Volume =. Foundations and Trends in Machine Learning , Number =. 2008 , Bdsk-File-1 =

    2008

  169. [177]

    and Sanghavi, S

    Ray, A. and Sanghavi, S. and Shakkottai, S. , Booktitle =. Greedy Learning of Graphical Models with Small Girth , Year =

  170. [178]

    , Date-Added =

    Bento, J. , Date-Added =. LEARNING GRAPHICAL MODELS FUNDAMENTAL LIMITS AND EFFICIENT ALGORITHMS , Year =

  171. [179]

    and Mossel, E

    Anandkumar, A. and Mossel, E. , Date-Added =. Learning High-Dimensional Latent Graphical Models: Girth-Constrained Graph Families , Year =

  172. [180]

    and Monasson, R

    Cocco, S. and Monasson, R. , Date-Added =. Adaptive cluster expansion for the inverse. Journal of Statistical Physics , Pages =. 2012 , Bdsk-File-1 =

    2012

  173. [181]

    and Banerjee, S

    Netrapalli, P. and Banerjee, S. and Sanghavi, S. and Shakkottai, S. , Booktitle =. Greedy learning of. 2010 , Bdsk-File-1 =

    2010

  174. [182]

    and Montanari, A

    Bento, J. and Montanari, A. , Booktitle =. Which graphical models are difficult to learn? , Year =

  175. [183]

    and Roch, S

    Mossel, E. and Roch, S. and Sly, A. , Date-Added =. arXiv preprint arXiv:1109.4668 , Title =

    arXiv

  176. [184]

    and Wainwright, M.J

    Ravikumar, P. and Wainwright, M.J. and Lafferty, J.D. , Date-Added =. High-dimensional. Annals of Statistics , Number =. 2010 , Bdsk-File-1 =

    2010

  177. [185]

    and Srikant, R

    Wu, R. and Srikant, R. and Ni, J. , Booktitle =. Learning graph structures in discrete. 2012 , Bdsk-File-1 =

    2012

  178. [186]

    and Mossel, E

    Bresler, G. and Mossel, E. and Sly, A. , Booktitle =. SIAM Journal on Computing, 2013 , Title =. 2008 , Bdsk-File-1 =

    2013

  179. [187]

    and Koller, D

    Abbeel, P. and Koller, D. and Ng, A.Y. , Date-Added =. arXiv preprint arXiv:1207.1366 , Title =. 2005 , Bdsk-File-1 =

    2005 arXiv

  180. [188]

    and Valluvan, R

    Anandkumar, A. and Valluvan, R. , Date-Added =. arXiv preprint arXiv:1203.3887 , Title =. 2012 , Bdsk-File-1 =

    2012 arXiv

  181. [189]

    and Tan, V

    Choi, M. and Tan, V. and Anandkumar, A. and Willsky, A. , Date-Added =. arXiv preprint arXiv:1009.2722 , Title =. 2010 , Bdsk-File-1 =

    2010 arXiv

  182. [190]

    and Johnson, C

    Jalali, A. and Johnson, C. and Ravikumar, P. , Date-Added =. arXiv preprint arXiv:1107.3258 , Title =. 2011 , Bdsk-File-1 =

    2011 arXiv

  183. [191]

    and Tan, V

    Anandkumar, A. and Tan, V. and Huang, F. and Willsky, A. , Date-Added =. High-dimensional structure estimation in. Annals of Stat. , Number =. 2012 , Bdsk-File-1 =

    2012

  184. [192]

    and Mossel, E

    Bogdanov, A. and Mossel, E. and Vadhan, S. , Date-Added =. The complexity of distinguishing. Approximation, Randomization and Combinatorial Optimization , Pages =. 2008 , Bdsk-File-1 =

    2008

  185. [193]

    and Wainwright, M.J

    Loh, P.L. and Wainwright, M.J. , Booktitle =. arXiv preprint arXiv:1212.0478 , Title =. 2012 , Bdsk-File-1 =

    2012 arXiv

  186. [194]

    and Gamarnik, D

    Bandyopadhyay, A. and Gamarnik, D. , Date-Modified =. Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models , Volume =. Random Structures & Algorithms , Number =

  187. [195]

    and Nowicki, T

    Gamarnik, D. and Nowicki, T. and Swirszcz, G. , Date-Modified =. Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method , Volume =. Random Structures & Algorithms , Number =

  188. [196]

    and Goldberg, D

    Gamarnik, D. and Goldberg, D. and Weber, T. , Date-Modified =. arXiv preprint arXiv:0912.0338 , Title =

    arXiv

  189. [197]

    Detecting high log-densities: an O(n^

    Bhaskara, Aditya and Charikar, Moses and Chlamtac, Eden and Feige, Uriel and Vijayaraghavan, Aravindan , Journal=. Detecting high log-densities: an O(n^. 2010 , Organization=

    2010

  190. [198]

    Gao, Chao and Ma, Zongming and Zhou, Harrison H , journal=. Sparse. 2017 , publisher=

    2017

  191. [199]

    Proceedings of the fifty-eighth IEEE Foundations of Computer Science (FOCS) , year=

    The power of sum-of-squares for detecting hidden structures , author=. Proceedings of the fifty-eighth IEEE Foundations of Computer Science (FOCS) , year=

  192. [200]

    The American mathematical monthly , volume=

    Some probabilistic aspects of set partitions , author=. The American mathematical monthly , volume=. 1997 , publisher=

    1997

  193. [201]

    Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages=

    On the complexity of random satisfiability problems with planted solutions , author=. Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages=. 2015 , organization=

    2015

  194. [202]

    2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) , title=

    B. 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) , title=. 2016 , volume=

    2016

  195. [203]

    Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages=

    Sum-of-squares lower bounds for planted clique , author=. Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages=. 2015 , organization=

    2015

  196. [204]

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

    Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems , author =. Proceedings of The 28th Conference on Learning Theory , pages =. 2015 , volume =

    2015

  197. [205]

    and Kothari, Pravesh and Potechin, Aaron Henry and Raghavendra, Prasad and Schramm, Tselil , title =

    Hopkins, Samuel B. and Kothari, Pravesh and Potechin, Aaron Henry and Raghavendra, Prasad and Schramm, Tselil , title =. 2018 , issue_date =

    2018

  198. [206]

    arXiv preprint arXiv:1507.05136 , year=

    Tight lower bounds for planted clique in the degree-4 SOS program , author=. arXiv preprint arXiv:1507.05136 , year=

    arXiv

  199. [207]

    arXiv preprint 2402.00305 , year=

    Information-Theoretic Thresholds for Planted Dense Cycles , author=. arXiv preprint 2402.00305 , year=

    arXiv

  200. [208]

    Proceedings of Thirty Sixth Conference on Learning Theory , pages =

    Detection-Recovery Gap for Planted Dense Cycles , author =. Proceedings of Thirty Sixth Conference on Learning Theory , pages =. 2023 , volume =

    2023

  201. [209]

    Statistical and Computational Limits of Detecting and Recovering Hidden Submatrices , year=

    Dadon, Marom and Huleihel, Wasim and Bendory, Tamir , booktitle=. Statistical and Computational Limits of Detecting and Recovering Hidden Submatrices , year=

  202. [210]

    Detection and Recovery of Hidden Submatrices , year=

    Dadon, Marom and Huleihel, Wasim and Bendory, Tamir , journal=. Detection and Recovery of Hidden Submatrices , year=

  203. [211]

    S. B. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , title=. 2017 , volume=

    2017

  204. [212]

    Foundations and Trends

    Average-case complexity , author=. Foundations and Trends. 2006 , publisher=

    2006

  205. [213]

    SIAM Journal on Computing , volume=

    On worst-case to average-case reductions for NP problems , author=. SIAM Journal on Computing , volume=. 2006 , publisher=

    2006

  206. [214]

    Conference on Learning Theory , pages=

    Computationally efficient robust sparse estimation in high dimensions , author=. Conference on Learning Theory , pages=

  207. [215]

    arXiv preprint arXiv:1702.05860 , year=

    Robust sparse estimation tasks in high dimensions , author=. arXiv preprint arXiv:1702.05860 , year=

    arXiv

  208. [216]

    The Annals of Statistics , volume=

    Sparse PCA: Optimal rates and adaptive estimation , author=. The Annals of Statistics , volume=. 2013 , publisher=

    2013

  209. [217]

    Annales de l'IHP Probabilit

    A dozen de Finetti-style results in search of a theory , author=. Annales de l'IHP Probabilit. 1987 , organization=

    1987

  210. [218]

    Unpublished manuscript , volume=

    Inapproximability of densest -subgraph from average case hardness , author=. Unpublished manuscript , volume=

  211. [219]

    Communications of the ACM , volume=

    Computational complexity and information asymmetry in financial products , author=. Communications of the ACM , volume=. 2011 , publisher=

    2011

  212. [220]

    , author=

    Inapproximability of NP-Complete Variants of Nash Equilibrium. , author=. Theory of Computing , volume=

  213. [221]

    and Amelia Perry and Wein, Alexander S

    Bandeira, Afonso S. and Amelia Perry and Wein, Alexander S. Notes on computational-to-statistical gaps: Predictions using statistical physics. Portugaliae Mathematica. 2018

    2018

  214. [222]

    The Complexity of Public-Key Cryptography

    Barak, Boaz. The Complexity of Public-Key Cryptography. Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich. 2017. doi:10.1007/978-3-319-57048-8_2

    2017 doi

  215. [223]

    Proceedings of the forty-second ACM symposium on Theory of computing , pages=

    Public-key cryptography from different assumptions , author=. Proceedings of the forty-second ACM symposium on Theory of computing , pages=. 2010 , organization=

    2010

  216. [224]

    Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Finding endogenously formed communities , author=. Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2013 , organization=

    2013

  217. [225]

    arXiv preprint arXiv:1801.00518 , year=

    Statistical and computational limits for sparse matrix detection , author=. arXiv preprint arXiv:1801.00518 , year=

    arXiv

  218. [226]

    arXiv preprint arXiv:1803.07054 , year=

    Optimal link prediction with matrix logistic regression , author=. arXiv preprint arXiv:1803.07054 , year=

    arXiv

  219. [227]

    arXiv preprint arXiv:1802.06361 , year=

    On Finding Dense Common Subgraphs , author=. arXiv preprint arXiv:1802.06361 , year=

    arXiv

  220. [228]

    IEEE Transactions on Information Theory , volume=

    Incoherence-optimal matrix completion , author=. IEEE Transactions on Information Theory , volume=. 2015 , publisher=

    2015

  221. [229]

    SIAM Journal on Computing , volume=

    How hard is it to approximate the best Nash equilibrium? , author=. SIAM Journal on Computing , volume=. 2011 , publisher=

    2011

  222. [230]

    LIPIcs-Leibniz International Proceedings in Informatics , volume=

    On the average-case complexity of MCSP and its variants , author=. LIPIcs-Leibniz International Proceedings in Informatics , volume=. 2017 , organization=

    2017

  223. [231]

    Designs, Codes and Cryptography , volume=

    Hiding cliques for cryptographic security , author=. Designs, Codes and Cryptography , volume=. 2000 , publisher=

    2000

  224. [232]

    Proceedings of the 2016 ACM Conference on Economics and Computation , pages=

    Hardness results for signaling in bayesian zero-sum and network routing games , author=. Proceedings of the 2016 ACM Conference on Economics and Computation , pages=. 2016 , organization=

    2016

  225. [233]

    Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on , pages=

    On the hardness of signaling , author=. Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on , pages=. 2014 , organization=

    2014

  226. [234]

    IEEE Transactions on Information Theory , volume=

    Hidden cliques and the certification of the restricted isometry property , author=. IEEE Transactions on Information Theory , volume=. 2014 , publisher=

    2014

  227. [235]

    Approximation, Randomization, and Combinatorial Optimization

    Small clique detection and approximate Nash equilibria , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , pages=. 2009 , publisher=

    2009

  228. [236]

    Symposium on the Theory of Computing (STOC) , year=

    Clique is hard on average for regular resolution , author=. Symposium on the Theory of Computing (STOC) , year=

  229. [237]

    Conference on Learning Theory , pages=

    Label optimal regret bounds for online local learning , author=. Conference on Learning Theory , pages=

  230. [238]

    arXiv preprint arXiv:1703.02724 , year=

    Tensor SVD: Statistical and Computational Limits , author=. arXiv preprint arXiv:1703.02724 , year=

    arXiv

  231. [239]

    Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

    From average case complexity to improper learning complexity , author=. Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=. 2014 , organization=

    2014

  232. [240]

    Conference on Learning Theory , pages=

    Complexity theoretic limitations on learning dnf’s , author=. Conference on Learning Theory , pages=

  233. [241]

    Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages=

    Complexity theoretic limitations on learning halfspaces , author=. Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages=. 2016 , organization=

    2016

  234. [242]

    LIPIcs-Leibniz International Proceedings in Informatics , volume=

    Embedding hard learning problems into gaussian space , author=. LIPIcs-Leibniz International Proceedings in Informatics , volume=. 2014 , organization=

    2014

  235. [243]

    21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) , pages=

    Finding hidden cliques in linear time , author=. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) , pages=. 2010 , organization=

    2010

  236. [244]

    Combinatorics, Probability and Computing , volume=

    Finding hidden cliques in linear time with high probability , author=. Combinatorics, Probability and Computing , volume=. 2014 , publisher=

    2014

  237. [245]

    Random Structures and Algorithms , volume=

    Finding and certifying a large hidden clique in a semirandom graph , author=. Random Structures and Algorithms , volume=

  238. [246]

    Mathematical programming , volume=

    Nuclear norm minimization for the planted clique and biclique problems , author=. Mathematical programming , volume=. 2011 , publisher=

    2011

  239. [247]

    Conference on Learning Theory , pages=

    On the approximability of sparse PCA , author=. Conference on Learning Theory , pages=

  240. [248]

    Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    ETH hardness for densest-k-subgraph with perfect completeness , author=. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2017 , organization=

    2017

  241. [249]

    Conference on Learning Theory , pages=

    Computational limits for matrix completion , author=. Conference on Learning Theory , pages=

  242. [250]

    Conference on Learning Theory , pages=

    Lower bounds on the performance of polynomial-time algorithms for sparse linear regression , author=. Conference on Learning Theory , pages=

  243. [251]

    Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph , author=. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages=. 2017 , organization=

    2017

  244. [252]

    LIPIcs-Leibniz International Proceedings in Informatics , volume=

    Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere , author=. LIPIcs-Leibniz International Proceedings in Informatics , volume=. 2017 , organization=

    2017

  245. [253]

    and Mori, Ryuhei and O'Donnell, Ryan and Witmer, David , title =

    Kothari, Pravesh K. and Mori, Ryuhei and O'Donnell, Ryan and Witmer, David , title =. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2017 , publisher =

    2017

  246. [254]

    arXiv preprint arXiv:1611.03473 , year=

    Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures , author=. arXiv preprint arXiv:1611.03473 , year=

    arXiv

  247. [255]

    arXiv preprint arXiv: 1511.05254 , year=

    The hidden subgraph problem , author=. arXiv preprint arXiv: 1511.05254 , year=

    arXiv

  248. [256]

    Journal of Statistical Physics , volume=

    Finding one community in a sparse graph , author=. Journal of Statistical Physics , volume=. 2015 , publisher=

    2015

  249. [257]

    The Annals of Applied Probability , volume=

    Community detection in sparse random networks , author=. The Annals of Applied Probability , volume=. 2015 , publisher=

    2015

  250. [258]

    The Annals of Statistics , volume=

    Community detection in dense random networks , author=. The Annals of Statistics , volume=. 2014 , publisher=

    2014

  251. [259]

    Information Limits for Recovering a Hidden Community , year=

    Hajek, Bruce and Wu, Yihong and Xu, Jiaming , journal=. Information Limits for Recovering a Hidden Community , year=

  252. [260]

    The probable value of the Lov

    Feige, Uriel and Krauthgamer, Robert , journal=. The probable value of the Lov. 2003 , publisher=

    2003

  253. [261]

    SIAM Journal on Optimization , volume=

    Finding Planted Subgraphs with Few Eigenvalues using the Schur--Horn Relaxation , author=. SIAM Journal on Optimization , volume=. 2018 , publisher=

    2018

  254. [262]

    Communications in mathematical physics , volume=

    The largest eigenvalue of rank one deformation of large Wigner matrices , author=. Communications in mathematical physics , volume=. 2007 , publisher=

    2007

  255. [263]

    The Annals of Statistics , volume=

    Asymptotic power of sphericity tests for high-dimensional data , author=. The Annals of Statistics , volume=. 2013 , publisher=

    2013

  256. [264]

    IEEE Transactions on Information Theory , year=

    Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization , author=. IEEE Transactions on Information Theory , year=

  257. [265]

    Wein and Afonso S

    Amelia Perry and Alexander S. Wein and Afonso S. Bandeira , title =. Annales de l'Institut Henri Poincar

  258. [266]

    Wein and Afonso S

    Amelia Perry and Alexander S. Wein and Afonso S. Bandeira and Ankur Moitra , title =. The Annals of Statistics , volume =

  259. [267]

    Proceedings of Thirty Fourth Conference on Learning Theory , pages =

    Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent , author =. Proceedings of Thirty Fourth Conference on Learning Theory , pages =. 2021 , editor =

    2021

  260. [268]

    arXiv preprint arXiv:1702.00473 , year=

    Fundamental limits of low-rank matrix estimation , author=. arXiv preprint arXiv:1702.00473 , year=

    arXiv

  261. [269]

    Probability Theory and Related Fields , volume=

    The largest eigenvalue of small rank perturbations of Hermitian random matrices , author=. Probability Theory and Related Fields , volume=. 2006 , publisher=

    2006

  262. [270]

    The Annals of Probability , volume=

    The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations , author=. The Annals of Probability , volume=. 2009 , publisher=

    2009

  263. [271]

    Advances in Mathematics , volume=

    The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices , author=. Advances in Mathematics , volume=. 2011 , publisher=

    2011

  264. [272]

    Random Structures & Algorithms , volume=

    On independent sets in random graphs , author=. Random Structures & Algorithms , volume=. 2015 , publisher=

    2015

  265. [273]

    Approximation, Randomization and Combinatorial Optimization

    Finding a maximum independent set in a sparse random graph , author=. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques , pages=. 2005 , publisher=

    2005

  266. [274]

    Proceedings of the 5th conference on Innovations in theoretical computer science , pages=

    Limits of local algorithms over sparse random graphs , author=. Proceedings of the 5th conference on Innovations in theoretical computer science , pages=. 2014 , organization=

    2014

  267. [275]

    The Annals of Probability , volume=

    Local algorithms for independent sets are half-optimal , author=. The Annals of Probability , volume=. 2017 , publisher=

    2017

  268. [276]

    arXiv preprint arXiv:1602.08529 , year=

    Finding a large submatrix of a Gaussian random matrix , author=. arXiv preprint arXiv:1602.08529 , year=

    arXiv

  269. [277]

    Artificial Intelligence and Statistics , pages=

    Minimax rates of estimation for sparse PCA in high dimensions , author=. Artificial Intelligence and Statistics , pages=

  270. [278]

    Journal of Multivariate Analysis , volume=

    Consistency of sparse PCA in high dimension, low sample size contexts , author=. Journal of Multivariate Analysis , volume=. 2013 , publisher=

    2013

  271. [279]

    Annals of statistics , volume=

    Minimax bounds for sparse PCA with noisy high-dimensional data , author=. Annals of statistics , volume=. 2013 , publisher=

    2013

  272. [280]

    arXiv preprint arXiv:1804.07842 , year=

    Sherali-Adams Integrality Gaps Matching the Log-Density Threshold , author=. arXiv preprint arXiv:1804.07842 , year=

    arXiv

  273. [281]

    Proceedings 42nd IEEE Symposium on Foundations of Computer Science , title=

    Frank. Proceedings 42nd IEEE Symposium on Foundations of Computer Science , title=. 2001 , volume=

    2001

  274. [282]

    NIPS 2011 workshop on computational trade-offs in statistical learning , volume=

    Statistical and computational tradeoffs in biclustering , author=. NIPS 2011 workshop on computational trade-offs in statistical learning , volume=

    2011

  275. [283]

    Advances in Neural Information Processing Systems , pages=

    Minimax localization of structural information in large noisy matrices , author=. Advances in Neural Information Processing Systems , pages=

  276. [284]

    The Annals of Applied Statistics , volume=

    Finding large average submatrices in high dimensional data , author=. The Annals of Applied Statistics , volume=. 2009 , publisher=

    2009

  277. [285]

    Annual Symposium on Theoretical Aspects of Computer Science , pages=

    Finding large independent sets in polynomial expected time , author=. Annual Symposium on Theoretical Aspects of Computer Science , pages=. 2003 , organization=

    2003

  278. [286]

    Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on , pages=

    Everywhere-sparse spanners via dense subgraphs , author=. Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on , pages=. 2012 , organization=

    2012

  279. [287]

    Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Minimizing the union: Tight approximations for small set bipartite vertex expansion , author=. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2017 , organization=

    2017

  280. [288]

    arXiv preprint arXiv:1703.10146 , year=

    Community detection and stochastic block models: recent developments , author=. arXiv preprint arXiv:1703.10146 , year=

    arXiv

  281. [289]

    arXiv preprint arXiv:1202.1499 , year=

    Stochastic block models and reconstruction , author=. arXiv preprint arXiv:1202.1499 , year=

    arXiv

  282. [290]

    Combinatorica , pages=

    A proof of the block model threshold conjecture , author=. Combinatorica , pages=. 2013 , publisher=

    2013

  283. [291]

    arXiv preprint arXiv:1407.1591 , year=

    Consistency thresholds for binary symmetric block models , author=. arXiv preprint arXiv:1407.1591 , year=

    arXiv

  284. [292]

    Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

    Community detection thresholds and the weak Ramanujan property , author=. Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=. 2014 , organization=

    2014

  285. [293]

    IEEE Transactions on Information Theory , volume=

    Achieving exact cluster recovery threshold via semidefinite programming , author=. IEEE Transactions on Information Theory , volume=. 2016 , publisher=

    2016

  286. [294]

    IEEE Transactions on Information Theory , volume=

    Exact recovery in the stochastic block model , author=. IEEE Transactions on Information Theory , volume=. 2016 , publisher=

    2016

  287. [295]

    arXiv preprint arXiv:1512.09080 , year=

    Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic BP, and the information-computation gap , author=. arXiv preprint arXiv:1512.09080 , year=

    arXiv

  288. [296]

    SIAM Journal on Computing , volume=

    Average case complete problems , author=. SIAM Journal on Computing , volume=. 1986 , publisher=

    1986

  289. [297]

    ECCC, TR06-122 , volume=

    All natural NPC problems have average-case complete versions , author=. ECCC, TR06-122 , volume=

  290. [298]

    2009 , publisher=

    Computational complexity: a modern approach , author=. 2009 , publisher=

    2009

  291. [299]

    , author=

    Approximating the minmax value of 3-player games within a constant is as hard as detecting planted cliques. , author=. Electronic Colloquium on Computational Complexity (ECCC) , volume=

  292. [300]

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

    Feeling the Bern: Adaptive estimators for Bernoulli probabilities of pairwise comparisons , author=. Information Theory (ISIT), 2016 IEEE International Symposium on , pages=. 2016 , organization=

    2016

Pith tools

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