Computational lower bounds for graphon estimation via low-degree polynomials

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

A nonparametric view of network models and Newman–Girvan and other modularities
Spectral clustering and the high-dimensional stochastic blockmodel
Limits of dense graph sequences
Large networks and graph limits
A survey of statistical network models
Rate-optimal graphon estimation
A proof of the block model threshold conjecture
Dynamic network models and graphon estimation
Matrix estimation by universal singular value thresholding
Consistency of spectral clustering in stochastic block models
Minimax rates of community detection in stochastic block models
Community structure in social and biological networks
Community detection and stochastic block models: recent developments
Tensor SVD: Statistical and Computational Limits
Reconstruction and estimation in the planted partition model
Community detection thresholds and the weak Ramanujan property
The method of moments and degree distributions for network models
Fast community detection by SCORE
Exact Recovery in the Stochastic Block Model
Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization
Oracle inequalities for network models and sparse graphon estimation
Community detection in sparse networks via Grothendieck's inequality
Detection of a sparse submatrix of a high-dimensional noisy matrix
Representations for partially exchangeable arrays of random variables
Graph limits and exchangeable random graphs
Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions
Computational and statistical tradeoffs via convex relaxation
Consistent nonparametric estimation for heavy-tailed sparse graphs
Statistical and computational trade-offs in estimation of sparse principal components
Co-clustering separately exchangeable network data
Computational barriers in minimax submatrix detection
Limits of local algorithms over sparse random graphs
Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
Proof of the achievability conjectures for the general stochastic block model
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Co-clustering directed graphs to discover asymmetries and directional communities
Estimating network edge probabilities by neighbourhood smoothing
Sparse CCA: adaptive estimation and computational barriers
Convex biclustering
Title not available (Why is that?)
Isotonic regression with unknown permutations: statistics, computation and adaptation
Optimal estimation and completion of matrices with biclustering structures
Computationally efficient sparse clustering
Title not available (Why is that?)
The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix
Convex relaxation methods for community detection
Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
Optimal graphon estimation in cut distance
Computational and statistical boundaries for submatrix localization in a large noisy matrix
Statistical algorithms and a lower bound for detecting planted cliques
Efficient algorithms and lower bounds for robust linear regression
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 low-degree hardness of maximum independent set
Tensor clustering with planted structures: statistical optimality and computational limits
Co-clustering of nonsmooth graphons
Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly
Computational barriers to estimation from low-degree polynomials
Nearest Neighbors for Matrix Estimation Interpreted as Blind Regression for Latent Variable Model
Optimal estimation and computational limit of low-rank Gaussian mixtures
Title not available (Why is that?)
Average-case complexity of tensor decomposition for low-degree polynomials
Subexponential-time algorithms for sparse PCA

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)