LP decoding of codes with expansion parameter above 2/3

A code C⊆F2n is a (c,δ,ϵ)(c,δ,ϵ)-expander code if it has a Tanner graph, where every variable node has degree c  , and every subset of variable nodes L0L0 such that |L0|⩽δn|L0|⩽δn has at least ϵc|L0|ϵc|L0| neighbors.Feldman et al. (2007) [3] proved that LP decoding corrects 3ϵ−22ϵ−1⋅(δn−1) errors of (c,δ,ϵ)(c,δ,ϵ)-expander code, where ϵ>23+13c.In this paper, we provide a slight consolidation of their work and show that this result holds for every expansion parameter ϵ>23.

► We provide some consolidation of the work of Feldman et al. (2007) [3]. ► Our proof is slightly shorter than the proof of Feldman et al. ► We show that expansion parameter above 2/3 is sufficient for LP decoding.