The stronger minimum pseudocodeword weight bound for expander codes

About 19 years old · traced to

Let GG be a (c,d,m,n,μ)(c,d,m,n,\mu) expander graph, and let NN denote the block length of the LDPC code obtained from GG. Let wmin⁡BSCw^{BSC}_{\min} denote its minimum pseudocodeword weight. Assume that

ϵ2d≥ϵ1c>2μ.\epsilon_2d\geq \epsilon_1c>2\mu.

Stronger pseudocodeword weight conjecture. The resulting LDPC code has

wmin⁡BSC≥N(ϵ1ϵ22−μ2cd(ϵ1cd+ϵ2dc)).w^{BSC}_{\min}\geq N\left(\frac{\epsilon_1\epsilon_2}{2}-\frac{\mu}{2\sqrt{cd}}\left(\epsilon_1\sqrt{\frac{c}{d}}+\epsilon_2\sqrt{\frac{d}{c}}\right)\right).

The authors present this as a strengthening of the preceding lower bound for the minimum pseudocodeword weight; the supplied text gives no evidence that it has been proved or disproved.

References

Primary source

Christine A. Kelley and Deepak Sridhara, “Eigenvalue bounds on the pseudocodeword weight of expander codes”, arXiv:0708.2462 (2007).

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.