AI summaryⓘ
The authors study a problem called planted noisy kXOR and its strong refutation, which involves balancing signal strength against computational time using a mathematical method called the Kikuchi hierarchy. They improve on previous approaches by introducing a normalized version of this hierarchy that matches a long-standing conjectured trade-off perfectly, eliminating previous small losses that made algorithms slower. Their improved algorithms can detect signals, recover solutions, and strongly refute random instances, with additional steps for exact recovery and formal proof certificates. The authors also extend their results to more general cases and provide a quantum algorithm that runs faster than classical ones. Key to their approach are clever normalizations and counting techniques related to matrix traces, which also help prove a related hypergraph conjecture.
kXOR problemKikuchi hierarchysignal-to-time trade-offspectral algorithmsstrong refutationsum-of-squares proofsquantum algorithmstrace momentsplanted modelshypergraph Moore bound
Authors
Alexander Schmidhuber, Matthew B. Hastings
Abstract
Planted noisy $k$XOR and the strong refutation of random $k$XOR are governed by a conjectured trade-off between signal strength and time: Level $\ell$ of the Kikuchi hierarchy should achieve the smooth curve \begin{equation*} m\ \gtrsim\ ρ^{-2}n^{k/2}/\ell^{k/2-1}\ \text{clauses} \quad\Longleftrightarrow\quad \text{solvable in time }n^{O(\ell)}, \end{equation*} where $ρ$ is the bias of the planted signal or, for refutation, the target advantage. However, every spectral analysis of sparse $k$XOR to date loses polylogarithmic factors against this curve, a loss that enters the exponent of the running time. We show that a normalized variant of the Kikuchi hierarchy achieves the sharp conjectured trade-off, with no logarithmic loss, at every arity $k\ge3$. At the scale above, our algorithms achieve strong detection, weak recovery, and strong refutation; an additional cleanup step boosts weak recovery to exact recovery, and the refutation certificates yield sum-of-squares proofs of degree $O_k(\ell)$. We also prove matching lower bounds in the same model. The inference and refutation upper bounds transfer to more general planting laws and predicates. Finally, we give a quantum algorithm that achieves a quartic speedup over the classical spectral algorithms for detection and weak recovery. The proofs rest on two key ingredients: a normalization of the sparse Kikuchi matrix, and a sharp count of the closed walks in its trace expansion. We use a closely related trace-walk count to prove Feige's 2008 hypergraph Moore bound conjecture in a companion paper.