  Feldman et al.(2005) asked whether the performance of the LP decoder can be
improved by adding redundant parity checks to tighten the LP relaxation. We
prove that for LDPC codes, even if we include all redundant checks,
asymptotically there is no gain in the LP decoder threshold on the BSC under
certain conditions on the base Tanner graph. First, we show that if the graph
has bounded check-degree and satisfies a condition which we call asymptotic
strength, then including high degree redundant checks in the LP does not
significantly improve the threshold in the following sense: for each constant
delta>0, there is a constant k>0 such that the threshold of the LP decoder
containing all redundant checks of degree at most k improves by at most delta
upon adding to the LP all redundant checks of degree larger than k. We conclude
that if the graph satisfies a rigidity condition, then including all redundant
checks does not improve the threshold of the base LP. We call the graph
asymptotically strong if the LP decoder corrects a constant fraction of errors
even if the LLRs of the correct variables are arbitrarily small. By building on
the work of Feldman et al.(2007) and Viderman(2013), we show that asymptotic
strength follows from sufficiently large expansion. We also give a geometric
interpretation of asymptotic strength in terms pseudocodewords. We call the
graph rigid if the minimum weight of a sum of check nodes involving a cycle
tends to infinity as the block length tends to infinity. Under the assumptions
that the graph girth is logarithmic and the minimum check degree is at least 3,
rigidity is equivalent to the nondegeneracy property that adding at least
logarithmically many checks does not give a constant weight check. We argue
that nondegeneracy is a typical property of random check-regular graphs.
