LP/SDP hierarchy lower bounds for decoding random LDPC codes

Random (dv, dc)-regular LDPC codes (where each variable is involved in d, parity checks and each parity check involves d, variables) 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: -- For any values of d, and de, 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. -- For any value of d, and infinitely many values of de, 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 streching 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. Our (algebraic) construction for the Lasserre hierarchy is based on designing sets of points in Fq (for q any power of 2 and d = 2,3) with special hyperplane-incidence properties constructions that may be of independent interest. An intriguing consequence of our work is that expansion seems to be both the strength and the weakness of random regular LDPC codes. 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 - e that holds after a 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-E and due to Schoenebeck.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2015

Author dc:creator

• Ghazi, Badih

Advisor dc:contributor.advisor

• Madhu Sudan.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/97327

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/97327