Belief propagation for approximate real 3LIN?

Question

In a Science paper from 2002, Mezard, Parisi and Zecchina put forward the belief propagation heuristic for random 3SAT. Experiments indicate that the heuristic works well for ratios of constraints-per-variable for which a satisfying assignment is likely to exist.

My questions are:

(1) What if you consider random 3LIN instead of random 3SAT? (each constraint is a random linear equation over GF(2))

(2) What if you consider random approximate real 3LIN? Is it conceivable that the performance of (an appropriately adapted) belief propagation heuristic would be easier to analyze in this case?

The approximate version, defined in a recent work with Subhash Khot, is as follows: the variables can assume real values and not just binary values. We consider only assignments of norm 1. Each equation is of the form $c_1 x_1 + c_2 x_2 + c_3 x_3 = 0$, where $c_1,c_2,c_3$ are normally distributed, and $x_1,x_2,x_3$ are chosen uniformly from the set of variables. An equation is satisfied if $|c_1 x_1 + c_2 x_2 + c_3 x_3|\leq \epsilon$, and not just if there is an exact equality.

The intuition is that in the approximate version, changes to the belief (what should be the assignment of a variable) could happen in a continuous/incremental way.

Answer 1

In coding theory, Belief Propagation is heavily used as a good heuristic for decoding (either explicit or randomly generated) LDPC codes in various settings (e.g., for the erasure channel, you want to satisfy all constraints more quickly than Gaussian elimination. For noisy channels, you want to find the "best fit", etc). I think techniques used there are directly relevant to your question. You may want to have a look at the book "Modern Coding Theory" by Urbanke and Richardson for an extensive discussion.