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.