MLS-3LIN problem is
a problem of finding a most likely solution for a given system of perturbed 3LIN-equations under a certain planted solution model.
This problem is essentially the same as MAX-3XORSAT problem.
We investigate
the average-case performance of message passing algorithms for this problem, where input instances are generated under the planted 
solution model with equation probability p and perturbation probability q.
For some variant of a typical message passing algorithm, we prove that p=Theta(1/(nln n)) is the threshold for the algorithm to work 
w.h.p.for any fixed constant q<1/2.