  `Tree pruning' (TP) is an algorithm for probabilistic inference on binary
Markov random fields. It has been recently derived by Dror Weitz and used to
construct the first fully polynomial approximation scheme for counting
independent sets up to the `tree uniqueness threshold.' It can be regarded as a
clever method for pruning the belief propagation computation tree, in such a
way to exactly account for the effect of loops.
  In this paper we generalize the original algorithm to make it suitable for
decoding linear codes, and discuss various schemes for pruning the computation
tree. Further, we present the outcomes of numerical simulations on several
linear codes, showing that tree pruning allows to interpolate continuously
between belief propagation and maximum a posteriori decoding. Finally, we
discuss theoretical implications of the new method.
