Computational lower bounds for graphon estimation via low-degree polynomials (Q6656622)

scientific article; zbMATH DE number 7961558

Language	Label	Description	Also known as
default for all languages	No label defined
English	Computational lower bounds for graphon estimation via low-degree polynomials	scientific article; zbMATH DE number 7961558

Statements

instance of

scholarly article

0 references

title

Computational lower bounds for graphon estimation via low-degree polynomials (English)

0 references

0 references

0 references

The Annals of Statistics

0 references

publication date

3 January 2025

0 references

zbMATH Keywords

community detection

0 references

computational lower bound

0 references

graphon estimation

0 references

Kesten-Stigum threshold

0 references

low-degree polynomials

0 references

statistical-computational tradeoffs

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Community detection and stochastic block models: recent developments

0 references

Exact Recovery in the Stochastic Block Model

0 references

Proof of the achievability conjectures for the general stochastic block model

0 references

Representations for partially exchangeable arrays of random variables

0 references

Q5875785

0 references

Q6147331

0 references

Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization

0 references

A nearly tight sum-of-squares lower bound for the planted clique problem

0 references

A nonparametric view of network models and Newman–Girvan and other modularities

0 references

The method of moments and degree distributions for network models

0 references

Consistent nonparametric estimation for heavy-tailed sparse graphs

0 references

An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence

0 references

An \(L^p\) theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions

0 references

Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing

0 references

Convergent sequences of dense graphs. II. Multiway cuts and statistical physics

0 references

Detection of a sparse submatrix of a high-dimensional noisy matrix

0 references

Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix

0 references

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

0 references

Computational and statistical tradeoffs via convex relaxation

0 references

Matrix estimation by universal singular value thresholding

0 references

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

0 references

Convex biclustering

0 references

Co-clustering of nonsmooth graphons

0 references

Co-clustering separately exchangeable network data

0 references

Graph limits and exchangeable random graphs

0 references

Efficient algorithms and lower bounds for robust linear regression

0 references

Subexponential-time algorithms for sparse PCA

0 references

Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly

0 references

Statistical algorithms and a lower bound for detecting planted cliques

0 references

On the complexity of random satisfiability problems with planted solutions

0 references

Limits of local algorithms over sparse random graphs

0 references

Optimal estimation and completion of matrices with biclustering structures

0 references

Rate-optimal graphon estimation

0 references

Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing

0 references

Sparse CCA: adaptive estimation and computational barriers

0 references

Community structure in social and biological networks

0 references

A survey of statistical network models

0 references

Community detection in sparse networks via Grothendieck's inequality

0 references

Fast community detection by SCORE

0 references

Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes

0 references

Oracle inequalities for network models and sparse graphon estimation

0 references

Optimal graphon estimation in cut distance

0 references

Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio

0 references

Consistency of spectral clustering in stochastic block models

0 references

Convex relaxation methods for community detection

0 references

Nearest Neighbors for Matrix Estimation Interpreted as Blind Regression for Latent Variable Model

0 references

Computationally efficient sparse clustering

0 references

Large networks and graph limits

0 references

Limits of dense graph sequences

0 references

Tensor clustering with planted structures: statistical optimality and computational limits

0 references

Optimal estimation and computational limit of low-rank Gaussian mixtures

0 references

Computational barriers in minimax submatrix detection

0 references

Community detection thresholds and the weak Ramanujan property

0 references

The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness

0 references

Reconstruction and estimation in the planted partition model

0 references

A proof of the block model threshold conjecture

0 references

Isotonic regression with unknown permutations: statistics, computation and adaptation

0 references

Dynamic network models and graphon estimation

0 references

Spectral clustering and the high-dimensional stochastic blockmodel

0 references

Co-clustering directed graphs to discover asymmetries and directional communities

0 references

Q5302097

0 references

Computational barriers to estimation from low-degree polynomials

0 references

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

0 references

Optimal low-degree hardness of maximum independent set

0 references

Average-case complexity of tensor decomposition for low-degree polynomials

0 references

Tensor SVD: Statistical and Computational Limits

0 references

Minimax rates of community detection in stochastic block models

0 references

Estimating network edge probabilities by neighbourhood smoothing

0 references

Identifiers

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6656622