Detection-Recovery Gap for Planted Dense Cycles
share
Planted dense cycles are a type of latent structure that appears in many applications, such as small-world networks in social sciences and sequence assembly in computational biology. We consider a model where a dense cycle with expected bandwidth n τ and edge density p is planted in an Erdős-Rényi graph G(n,q). We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree polynomial algorithms. In particular, a gap exists between the two thresholds in a certain regime of parameters. For example, if n^-3/4≪τ≪ n^-1/2 and p = C q = Θ(1) for a constant C>1, the detection problem is computationally easy while the recovery problem is hard for low-degree algorithms.
READ FULL TEXT