  Random (dv,dc)-regular LDPC codes are well-known to achieve the Shannon
capacity of the binary symmetric channel (for sufficiently large dv and dc)
under exponential time decoding. However, polynomial time algorithms are only
known to correct a much smaller fraction of errors. One of the most powerful
polynomial-time algorithms with a formal analysis is the LP decoding algorithm
of Feldman et al. which is known to correct an Omega(1/dc) fraction of errors.
In this work, we show that fairly powerful extensions of LP decoding, based on
the Sherali-Adams and Lasserre hierarchies, fail to correct much more errors
than the basic LP-decoder. In particular, we show that:
  1) For any values of dv and dc, a linear number of rounds of the
Sherali-Adams LP hierarchy cannot correct more than an O(1/dc) fraction of
errors on a random (dv,dc)-regular LDPC code.
  2) For any value of dv and infinitely many values of dc, a linear number of
rounds of the Lasserre SDP hierarchy cannot correct more than an O(1/dc)
fraction of errors on a random (dv,dc)-regular LDPC code.
  Our proofs use a new stretching and collapsing technique that allows us to
leverage recent progress in the study of the limitations of LP/SDP hierarchies
for Maximum Constraint Satisfaction Problems (Max-CSPs). The problem then
reduces to the construction of special balanced pairwise independent
distributions for Sherali-Adams and special cosets of balanced pairwise
independent subgroups for Lasserre.
  Some of our techniques are more generally applicable to a large class of
Boolean CSPs called Min-Ones. In particular, for k-Hypergraph Vertex Cover, we
obtain an improved integrality gap of $k-1-\epsilon$ that holds after a
\emph{linear} number of rounds of the Lasserre hierarchy, for any k = q+1 with
q an arbitrary prime power. The best previous gap for a linear number of rounds
was equal to $2-\epsilon$ and due to Schoenebeck.
