Log-free performance conjecture for the even-order Kikuchi algorithms

Fix an integer pp and let \ell be constant independently of nn. Log-free performance conjecture. There exists a constant cp()>0c_p(\ell)>0, with cp()0c_p(\ell)\to 0 as \ell\to\infty for fixed pp, such that whenever λcp()np/4\lambda\ge c_p(\ell)n^{-p/4}, the detection and recovery algorithms at level \ell, which run in time nO()n^{O(\ell)}, achieve strong detection and strong recovery, respectively. Removing the logarithmic factor would match the conjectured power of these polynomial-time algorithms with the guarantees suggested by the preceding results.

Sources & referencesView supporting material

Primary source

Alexander S. Wein, Ahmed El Alaoui and Cristopher Moore, “The Kikuchi Hierarchy and Tensor PCA”, arXiv:1904.03858 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.