A k -LIN instance is a system of m equations over n variables of the form s i [1] + + 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 . We show that O ( m ( m ) 2 k ) - equation, n -variable noisy planted k -LIN instances are efficiently solvable with probability exp − O (( m ) 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 : − 1 1 is its k -th tensor power F k ( x 1 x k ) = F ( x 1 ) F ( x k ) . Given oracle access to a function G that -correlates with F k , our algorithm outputs the description of a message that ( 1 k − ) -correlates with F with probability exp − O ( k 2 − 2 k − 2 ) . Previous decoders have a worse dependence on (Levin, Combinatorica 1987) or do not apply to subconstant 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.