Computational lower bounds for graphon estimation via low-degree polynomials

DOI10.1214/24-aos2437MaRDI QIDQ6656622

Chao Gao, Yuetian Luo

Publication date: 3 January 2025

Published in: The Annals of Statistics (Search for Journal in Brave)

zbMATH Keywords

community detectionlow-degree polynomialsgraphon estimationcomputational lower boundKesten-Stigum thresholdstatistical-computational tradeoffs

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Nonparametric estimation (62G05) 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)

This page was built for publication: Computational lower bounds for graphon estimation via low-degree polynomials