Linear Programming Decoding of Spatially Coupled Codes

For a given family of spatially coupled codes, we prove that the linear programming (LP) threshold on the binary-symmetric channel (BSC) of the tail-biting graph cover ensemble is the same as the LP threshold on the BSC of the derived spatially coupled ensemble. This result is in contrast with the fact that spatial coupling significantly increases the belief propagation threshold. To prove this, we establish some properties related to the dual witness for LP decoding. More precisely, we prove that the existence of a dual witness, which was previously known to be sufficient for LP decoding success, is also necessary and is equivalent to the existence of certain acyclic hyperflows. We also derive a sublinear (in the block length) upper bound on the weight of any edge in such hyperflows, both for regular low-density parity-check (LPDC) codes and spatially coupled codes and we prove that the bound is asymptotically tight for regular LDPC codes. Moreover, we show how to trade crossover probability for LP excess on all the variable nodes, for any binary linear code.