@article{669d4b50b2334db8bb329e785fa62628,
title = "On the hardness of approximating stopping and trapping sets",
abstract = "We prove that approximating the size of stopping and trapping sets in Tanner graphs of linear block codes, and more restrictively, the class of low-density parity-check (LDPC) codes, is NP-hard. The ramifications of our findings are that methods used for estimating the height of the error-floor of moderate- and long-length LDPC codes, based on stopping and trapping set enumeration, cannot provide accurate worst-case performance predictions for most codes.",
keywords = "Low-density parity-check (LDPC) codes, NP hardness, Stopping sets, Trapping sets",
author = "Andrew McGregor and Olgica Milenkovic",
note = "Funding Information: Manuscript received August 01, 2008; revised June 21, 2009. Current version published March 17, 2010. This work was supported in part by the NSF under Grant CCF 0644427, the NSF Career Award, and the DARPA Young Faculty Award of O. Milenkovic. The material in this paper was presented in part at the 2007 Information Theory Workshop, Lake Tahoe, NV. A. McGregor is with the Department of Computer Science, University of Massachusetts, Amherst, MA, 01003 USA (e-mail: mcgregor@cs.umass.edu.) O. Milenkovic is with the Department of Electrical and Computer Engineering, University of Illinois, Urbana-Champaign, IL, 61801 USA (e-mail: milenkov@uiuc.edu). Communicated by I. Sason, Associate Editor for Coding Theory. Digital Object Identifier 10.1109/TIT.2010.2040941",
year = "2010",
month = apr,
doi = "10.1109/TIT.2010.2040941",
language = "English (US)",
volume = "56",
pages = "1640--1650",
journal = "IRE Professional Group on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "4",
}