The Kikuchi Hierarchy is Sharp for $k$XOR

Alexander Schmidhuber, Matthew B. Hastings

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 shou…