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.