Log-free performance conjecture for the even-order Kikuchi algorithms
Log-free performance conjecture for the even-order Kikuchi algorithms
Fix an integer and let be constant independently of . Log-free performance conjecture. There exists a constant , with as for fixed , such that whenever , the detection and recovery algorithms at level , which run in time , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.