{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:18Z","timestamp":1759638078952},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540499947"},{"type":"electronic","value":"9783540499954"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11944836_9","type":"book-chapter","created":{"date-parts":[[2006,11,28]],"date-time":"2006-11-28T04:48:02Z","timestamp":1164689282000},"page":"69-80","source":"Crossref","is-referenced-by-count":2,"title":["Hardness of Approximation Results for the Problem of Finding the Stopping Distance in Tanner Graphs"],"prefix":"10.1007","author":[{"given":"K. Murali","family":"Krishnan","sequence":"first","affiliation":[]},{"given":"L. Sunil","family":"Chandran","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"6","key":"9_CR1","doi-asserted-by":"publisher","first-page":"1570","DOI":"10.1109\/TIT.2002.1003839","volume":"48","author":"C. Di","year":"2002","unstructured":"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\u00a048(6), 1570\u20131579 (2002)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"5","key":"9_CR2","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1109\/TIT.1981.1056404","volume":"27","author":"M. Tanner","year":"1981","unstructured":"Tanner, M.: A recursive approach to low-complexity codes. IEEE Trans. Inform. Theory\u00a027(5), 533\u2013547 (1981)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"9_CR3","unstructured":"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)"},{"issue":"3","key":"9_CR4","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1109\/TIT.2004.842571","volume":"51","author":"A. Orlitsky","year":"2005","unstructured":"Orlitsky, A., Viswanathan, K., Shang, J.: Stopping set distribution of LDPC code ensembles. IEEE Trans. Inform. Theory\u00a051(3), 929\u2013953 (2005)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"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\u20133129 (2003)","DOI":"10.1109\/ICC.2003.1203996"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Ramamoorthy, A., Wesel, R.: Construction of short block length irregular LDPC codes. In: Proc. ICC 2004, Paris, June 2004, pp. 410\u2013414 (2004)","DOI":"10.1109\/ICC.2004.1312521"},{"issue":"3","key":"9_CR7","doi-asserted-by":"publisher","first-page":"922","DOI":"10.1109\/TIT.2005.864441","volume":"52","author":"M. Schwartz","year":"2006","unstructured":"Schwartz, M., Vardy, A.: On the stopping distance and the stopping redundancy of codes. IEEE Trans. Inform. Theory\u00a052(3), 922\u2013932 (2006)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"9_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman, New York (1979)"},{"issue":"3","key":"9_CR9","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1109\/TIT.2004.824918","volume":"50","author":"H. Pishro-Nik","year":"2004","unstructured":"Pishro-Nik, H., Fekri, F.: On decoding of low-density parity-check codes over the binary erasure channel. IEEE Trans. Inform. Theory\u00a050(3), 439\u2013454 (2004)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"9_CR10","unstructured":"Han, J., Siegel, P.: Improved upper bounds on stopping redundancy (preprint), available at: http:\/\/www.arXiv.orgcs.IT\/0511056"},{"key":"9_CR11","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/4347.001.0001","volume-title":"Low density parity-check codes","author":"R.G. Gallager","year":"1963","unstructured":"Gallager, R.G.: Low density parity-check codes. MIT Press, Cambridge (1963)"},{"key":"9_CR12","unstructured":"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"},{"key":"9_CR13","volume-title":"Algebra","author":"M. Artin","year":"1991","unstructured":"Artin, M.: Algebra. Prentice-Hall, Englewood Cliffs (1991)"},{"key":"9_CR14","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2004","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2004)"},{"key":"9_CR15","volume-title":"Complexity and approximation: combinatorial optimization problems and their approximability properties","author":"G. Ausiello","year":"2003","unstructured":"Ausiello, G., et al.: Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer, Heidelberg (2003)"},{"key":"9_CR16","unstructured":"Hochbaum, D. (ed.): Approximation algorithms for NP-hard problems. Course Technology (1996)"},{"issue":"1","key":"9_CR17","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1109\/TIT.2002.806118","volume":"49","author":"I. Dumer","year":"2003","unstructured":"Dumer, I., Micciancio, D., Sudan, M.: Hardness of approximating the minimum distance of a linear code. IEEE Trans. Inform. Theory\u00a049(1), 475\u2013484 (2003)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"6","key":"9_CR18","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1109\/18.641542","volume":"43","author":"A. Vardy","year":"1997","unstructured":"Vardy, A.: The intractability of computing the minimum distance of a code. IEEE Trans. Inform. Theory\u00a043(6), 1757\u20131766 (1997)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"3","key":"9_CR19","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","volume":"24","author":"E. Berlekamp","year":"1978","unstructured":"Berlekamp, E., McEliece, R., van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Trans. Inform. Theory\u00a024(3), 384\u2013386 (1978)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"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\u2013111 (1998)","DOI":"10.1109\/SFCS.1998.743433"},{"issue":"2","key":"9_CR21","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S. Arora","year":"1997","unstructured":"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.\u00a054(2), 317\u2013331 (1997)","journal-title":"J. Comput. Sys. Sci."}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11944836_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:17:54Z","timestamp":1619507874000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11944836_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540499947","9783540499954"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11944836_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}