Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials

Yuetian Luo, Chao Gao

Graphon estimation has been one of the most fundamental problems in network analysis and has received considerable attention in the past decade. From the statistical perspective, t…