Message Passing Algorithms for MLS-3LIN Problem

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‐3LIN problem. We consider simple and efficient message passing algorithms for this problem, and investigate their success probability, 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=Θ(1/(nlnn)) is the threshold for the algorithm to work w.h.p. for any fixed constant q <1/2.