Researchers have demonstrated that a normalized variant of the Kikuchi hierarchy achieves the conjectured theoretical trade-off between signal strength and solution time for the kXOR problem. This breakthrough eliminates the logarithmic losses that plagued previous spectral analyses, which resulted in an exponential increase in runtime. The study validates the conjecture that level $\ell$ of the Kikuchi hierarchy can solve problems with $m \gtrsim \rho^{-2}n^{k/2}/\ell^{k/2-1}$ clauses in $n^{O(\ell)}$ time, where $\rho$ is the bias of the planted signal or the target advantage for refutation.

The algorithms developed in this research enable strong detection, weak recovery, and strong refutation at the specified scale. An additional cleanup step boosts weak recovery to exact recovery, and the refutation certificates yield sum-of-squares proofs of degree $O_k(\ell)$. Furthermore, the study establishes matching lower bounds in the same model, confirming the optimality of the results. The inference and refutation upper bounds are applicable to more general planting laws and predicates.

The proofs rely on two key ingredients: a normalization of the sparse Kikuchi matrix and a sharp count of closed walks in its trace expansion. This approach has also been used in a companion paper to prove Feige's 2008 hypergraph Moore bound conjecture. Additionally, the authors present a quantum algorithm that offers a quartic speedup over classical spectral algorithms for detection and weak recovery tasks.