  We introduce a novel algorithm for decoding binary linear codes by linear
programming. We build on the LP decoding algorithm of Feldman et al. and
introduce a post-processing step that solves a second linear program that
reweights the objective function based on the outcome of the original LP
decoder output. Our analysis shows that for some LDPC ensembles we can improve
the provable threshold guarantees compared to standard LP decoding. We also
show significant empirical performance gains for the reweighted LP decoding
algorithm with very small additional computational complexity.
