Computational lower bounds for graphon estimation via low-degree polynomials
From MaRDI portal
Publication:6656622
community detectiongraphon estimationlow-degree polynomialscomputational lower boundKesten-Stigum thresholdstatistical-computational tradeoffs
Nonparametric estimation (62G05) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Random graphs (graph-theoretic aspects) (05C80) Minimax procedures in statistical decision theory (62C20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites work
- scientific article; zbMATH DE number 5485586 (Why is no real title available?)
- scientific article; zbMATH DE number 7650426 (Why is no real title available?)
- scientific article; zbMATH DE number 7788417 (Why is no real title available?)
- A nearly tight sum-of-squares lower bound for the planted clique problem
- A nonparametric view of network models and Newman–Girvan and other modularities
- A proof of the block model threshold conjecture
- A survey of statistical network models
- Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly
- Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
- An \(L^p\) theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
- An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
- Average-case complexity of tensor decomposition for low-degree polynomials
- Co-clustering directed graphs to discover asymmetries and directional communities
- Co-clustering of nonsmooth graphons
- Co-clustering separately exchangeable network data
- Community detection and stochastic block models: recent developments
- Community detection in sparse networks via Grothendieck's inequality
- Community detection thresholds and the weak Ramanujan property
- Community structure in social and biological networks
- Computational and statistical boundaries for submatrix localization in a large noisy matrix
- Computational and statistical tradeoffs via convex relaxation
- Computational barriers in minimax submatrix detection
- Computational barriers to estimation from low-degree polynomials
- Computationally efficient sparse clustering
- Consistency of spectral clustering in stochastic block models
- Consistent nonparametric estimation for heavy-tailed sparse graphs
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
- Convex biclustering
- Convex relaxation methods for community detection
- Detection of a sparse submatrix of a high-dimensional noisy matrix
- Dynamic network models and graphon estimation
- Efficient algorithms and lower bounds for robust linear regression
- Estimating network edge probabilities by neighbourhood smoothing
- Exact Recovery in the Stochastic Block Model
- Fast community detection by SCORE
- Graph limits and exchangeable random graphs
- Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization
- Isotonic regression with unknown permutations: statistics, computation and adaptation
- Large networks and graph limits
- Limits of dense graph sequences
- Limits of local algorithms over sparse random graphs
- Matrix estimation by universal singular value thresholding
- Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
- Minimax rates of community detection in stochastic block models
- Nearest Neighbors for Matrix Estimation Interpreted as Blind Regression for Latent Variable Model
- Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
- On the complexity of random satisfiability problems with planted solutions
- Optimal estimation and completion of matrices with biclustering structures
- Optimal estimation and computational limit of low-rank Gaussian mixtures
- Optimal graphon estimation in cut distance
- Optimal low-degree hardness of maximum independent set
- Oracle inequalities for network models and sparse graphon estimation
- Proof of the achievability conjectures for the general stochastic block model
- Rate-optimal graphon estimation
- Reconstruction and estimation in the planted partition model
- Representations for partially exchangeable arrays of random variables
- Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix
- Sparse CCA: adaptive estimation and computational barriers
- Spectral clustering and the high-dimensional stochastic blockmodel
- Statistical algorithms and a lower bound for detecting planted cliques
- Statistical and computational trade-offs in estimation of sparse principal components
- Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
- Subexponential-time algorithms for sparse PCA
- Tensor SVD: Statistical and Computational Limits
- Tensor clustering with planted structures: statistical optimality and computational limits
- The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
- The method of moments and degree distributions for network models
This page was built for publication: Computational lower bounds for graphon estimation via low-degree polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6656622)
