Asymptotic strength of random regular Tanner graphs

Let dvd_v and dcd_c be integers with dc>dv3d_c>d_v\geq 3. A Tanner graph is asymptotically strong if, for every constant β>0\beta>0, there is a constant α>0\alpha>0 such that its LP decoder succeeds on the asymmetric LLR vector γ(y,β)\gamma(y,\beta) for every y{0,1}ny\in\{0,1\}^n of weight at most αn\alpha n. Asymptotic-strength conjecture. For all dc>dv3d_c>d_v\geq 3, a random (dv,dc)(d_v,d_c)-regular Tanner graph is asymptotically strong with high probability. This would extend the known implication from expansion to asymptotic strength to all random regular ensembles, without the integrality restrictions on the expansion parameters used in the preceding theorem.

Sources & referencesView supporting material

Primary source

Louay Bazzi and Hani Audah, “Impact of redundant checks on the LP decoding thresholds of LDPC codes”, arXiv:1411.7554 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.