We introduce a novel algorithm for decoding binary linear codes by linear programming (LP). We build on the LP decoding algorithm of Feldman and introduce a postprocessing 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.

Efficient hardware implementations of statistical inference continue to grow in importance for a wide range of computing applications. While CPU cycles are increasingly being used for statistical inference, transistors are also becoming increasingly statistical. For implementing statistical algorithms, could it be that statistical electronic substrates are a feature rather than a bug?

It has been observed that a linear-feedback shift-register (LFSR) sequence can be synchronized by feeding the modulated sequence into a "soft" (or "analog") version of the LFSR. In this correspondence, the "soft LFSR" is derived as forward-only message passing in the corresponding factor graph. A continous-time analog (suitable for realization as a clockless electronic circuit) is then given of both the LFSR and the soft LFSR. A connection is thus established between statistical state estimation and the phenomenon of entrainment of dynamical systems, which opens the prospect of deriving dynamical systems (such as electronic circuits) with strong entrainment capabilities from more powerful message passing algorithms