{"id":"arxiv/2607.29672","url":"https://arxiv.org/abs/2607.29672","tags":["cs.DS","cs.CC","quant-ph"],"score":0,"title":"The Kikuchi Hierarchy is Sharp for $k$XOR","domain":"cs.DS","source":"arxiv","authors":["Alexander Schmidhuber","Matthew B. Hastings"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-31","reactions":{}}