A $k$-LIN instance is a system of $m$ equations over $n$ variables of the form $s_{i[1]} + \dots + s_{i[k]} =$ 0 or 1 modulo 2 (each involving $k$ variables). We consider two distributions on instances in which the variables are chosen independently and uniformly but the right-hand sides are different. In a noisy planted instance, the right-hand side is obtained by evaluating the system on a random planted solution and adding independent noise with some constant bias to each equation; whereas in a random instance, the right-hand side is uniformly random. Alekhnovich (FOCS 2003) conjectured that the two are hard to distinguish when $k = 3$ and $m = O(n)$.

We give a sample-efficient reduction from solving noisy planted $k$-LIN instances to distinguishing them from random instances. Suppose that $m$-equation, $n$-variable instances of the two types are efficiently distinguishable with advantage $\epsilon$. We show that $O(m \cdot (m/\epsilon)^{2/k})$- equation, $n$-variable noisy planted $k$-LIN instances are efficiently solvable with probability $\exp -\tilde{O}((m/\epsilon)^{6/k})$. Our solver has worse success probability but better sample complexity than Applebaum's (SICOMP 2013).

The solver is based on a new approximate local list-decoding algorithm for the $k$-XOR code at large distances. The $k$-XOR encoding of a function $F\colon \Sigma \to \{-1, 1\}$ is its $k$-th tensor power $F^k(x_1, \dots, x_k) = F(x_1)\cdots F(x_k)$. Given oracle access to a function $G$ that $\mu$-correlates with $F^k$, our algorithm outputs the description of a message that $(\mu^{1/k} - \epsilon)$-correlates with $F$ with probability $\exp -\tilde{O}(k^2\mu^{-2/k}\epsilon^{-2})$. Previous decoders have a worse dependence on $\mu$ (Levin, Combinatorica 1987) or do not apply to subconstant $\mu^{1/k}$. We also prove a new XOR lemma for this parameter regime.

The decoder and its analysis rely on a new structure-versus-randomness dichotomy for Boolean-valued functions over product sets.