Abstract
Tanner Graph representation of linear block codes is widely used by iterative decoding algorithms for recovering data transmitted across a noisy communication channel from errors and erasures introduced by the channel. The stopping distance of a Tanner graph T for a binary linear block code C determines the number of erasures correctable using iterative decoding on the Tanner graph T when data is transmitted across a binary erasure channel using the code C. We show that the problem of finding the stopping distance of a Tanner graph is hard to approximate within any positive constant approximation ratio in polynomial time unless P=NP. It is also shown as a consequence that there can be no approximation algorithm for the problem achieving an approximation ratio of \(2^{(\log n)^{1-\epsilon}}\) for any ε> 0 unless NP ⊆ DTIME(n poly(logn)).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Di, C., Proietti, D., Telatar, I.E., Richardson, T.J., Urbanke, R.: Finite length analysis of low-density parity-check codes on the binary erasure channel. IEEE Trans. Inform. Theory 48(6), 1570–1579 (2002)
Tanner, M.: A recursive approach to low-complexity codes. IEEE Trans. Inform. Theory 27(5), 533–547 (1981)
Di, C., Montanari, A., Urbanke, R.: Weight distribution of LDPC code ensembles: Combinatorics meets statistical physics. In: Proc. IEEE Int. Symp. Inform. Theory, Chicago, IL, July 2004, p. 102 (2004)
Orlitsky, A., Viswanathan, K., Shang, J.: Stopping set distribution of LDPC code ensembles. IEEE Trans. Inform. Theory 51(3), 929–953 (2005)
Tian, T., Jones, C., Villasenor, J.D., Wesel, R.D.: Construction of irregular LDPC codes with low error floors. In: Proc. ICC 2003, Seattle, Washington, May 2003, pp. 3125–3129 (2003)
Ramamoorthy, A., Wesel, R.: Construction of short block length irregular LDPC codes. In: Proc. ICC 2004, Paris, June 2004, pp. 410–414 (2004)
Schwartz, M., Vardy, A.: On the stopping distance and the stopping redundancy of codes. IEEE Trans. Inform. Theory 52(3), 922–932 (2006)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman, New York (1979)
Pishro-Nik, H., Fekri, F.: On decoding of low-density parity-check codes over the binary erasure channel. IEEE Trans. Inform. Theory 50(3), 439–454 (2004)
Han, J., Siegel, P.: Improved upper bounds on stopping redundancy (preprint), available at: http://www.arXiv.orgcs.IT/0511056
Gallager, R.G.: Low density parity-check codes. MIT Press, Cambridge (1963)
Murali Krishnan, K., Shankar, P.: On the complexity of finding stopping distance in Tanner graphs (preprint), available at: http://www.arXiv.org , cs.IT/0512101
Artin, M.: Algebra. Prentice-Hall, Englewood Cliffs (1991)
Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2004)
Ausiello, G., et al.: Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer, Heidelberg (2003)
Hochbaum, D. (ed.): Approximation algorithms for NP-hard problems. Course Technology (1996)
Dumer, I., Micciancio, D., Sudan, M.: Hardness of approximating the minimum distance of a linear code. IEEE Trans. Inform. Theory 49(1), 475–484 (2003)
Vardy, A.: The intractability of computing the minimum distance of a code. IEEE Trans. Inform. Theory 43(6), 1757–1766 (1997)
Berlekamp, E., McEliece, R., van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Trans. Inform. Theory 24(3), 384–386 (1978)
Dinur, I., Kindler, G., Safra, S.: Approximating CVP to within almost polynomial factors in NP-hard. In: Proc. FOCS 1998, Palo Alto, California, November 1998, pp. 99–111 (1998)
Arora, S., Babai, L., Stern, J., Sweedyk, E.Z.: The hardness of approximate optima in lattices, codes and systems of linear equations. J. Comput. Sys. Sci. 54(2), 317–331 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Krishnan, K.M., Chandran, L.S. (2006). Hardness of Approximation Results for the Problem of Finding the Stopping Distance in Tanner Graphs. In: Arun-Kumar, S., Garg, N. (eds) FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science. FSTTCS 2006. Lecture Notes in Computer Science, vol 4337. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11944836_9
Download citation
DOI: https://doi.org/10.1007/11944836_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49994-7
Online ISBN: 978-3-540-49995-4
eBook Packages: Computer ScienceComputer Science (R0)