Using linear programming to Decode Binary linear codes

By Jon Feldman, Martin J. Wainwright, David R Karger. IEEE Transactions on Information Theory, 2005

545 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Hinge-Loss Markov Random Fields and Probabilistic Soft Logic (2015, methodology): “ve also studied performance guarantees of other subclasses of the rst-order local consistency relaxation. Kleinberg and Tardos (2002) and Chekuri et al. (2005) considered the metric labeling problem. Feldman et al. (2005) used the local consistency relaxation to decode binary linear codes. In this p”
Graphical Models, Exponential Families, and Variational Inference (2008, background): “Since its introduction [73, 75], the performance of this LP relaxation has been extensively studied [e.”
MAP estimation via agreement on trees: message-passing and linear programming (2005, methodology): “In a parallel collaboration with Feldman and Karger [19], [18], [20], we have studied the tree-relaxed linear program (LP) and related message-passing algorithms as decoding methods for turbo-like and low-density parity check (LDPC) codes, and provided finite-length performance guarantees for partic”
Decoding by linear programming (2005, unknown): “[22]–[25], linear programming methods (based on relaxing the space of codewords to a convex polytope) were developed to establish a polynomial-time decoder which can correct a constant fraction of errors, and also achieve the information-theoretic capacity of the code.”