{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:29:27Z","timestamp":1787322567084,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>This paper presents a unified analysis framework that captures recent advances in the study of local-optimality characterizations for codes on graphs. These local-optimality characterizations are based on combinatorial structures embedded in the Tanner graph of the code. Local optimality implies both unique maximum likelihood optimality and unique linear programming (LP) decoding optimality. Also, an iterative message-passing decoding algorithm is guaranteed to find the unique locally optimal codeword if one exists. We demonstrate an instance of this proof technique by considering a definition of local optimality that is based on the simplest combinatorial structures in Tanner graphs, namely, paths of length $h$. We apply the technique of local optimality to binary Tanner codes (including any low-density parity-check code, and in particular any irregular repeat-accumulate code with both even and odd repetition factors). Inverse polynomial bounds in the code length are proved on the word error probability of LP decoding for binary Tanner codes. When the local codes are restricted to single parity-check codes, these bounds also hold for decoding by a certain iterative message-passing decoding algorithm.<\/jats:p>","DOI":"10.1137\/120886674","type":"journal-article","created":{"date-parts":[[2013,12,5]],"date-time":"2013-12-05T11:32:44Z","timestamp":1386243164000},"page":"2049-2063","source":"Crossref","is-referenced-by-count":0,"title":["Local-Optimality Guarantees Based on Paths for Optimal Decoding"],"prefix":"10.1137","volume":"27","author":[{"given":"Guy","family":"Even","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nissim","family":"Halabi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,12,5]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Daskalakis, and D. Steurer,<i>Message passing algorithms and improved LP decoding<\/i> in Proceedings of the 41st ACM Symposium on Theory of Computing, 2009.","DOI":"10.1145\/1536414.1536418"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2208584"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055873"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.926452"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"S. Even,<i>Graph Algorithms<\/i> 2nd ed., Cambridge University Press, New York, 2011.","DOI":"10.1017\/CBO9781139015165"},{"key":"atypb6","unstructured":"W. Feller,<i>An Introduction to Probability Theory and Its Applications<\/i> Vol. 1, 3rd ed., Wiley, New York, 1968."},{"key":"atypb7","unstructured":"J. Feldman,<i>Decoding Error-Correcting Codes via Linear Programming<\/i> Ph.D. dissertation, MIT, Cambridge, MA, 2003."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.005"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.887523"},{"key":"atypb10","unstructured":"J. Feldman and C. Stein,<i>LP decoding achieves capacity<\/i> in Proceedings of the ACM Symposium on Discrete Algorithms, 2005."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.842696"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"R. G. Gallager,<i>Low-Density Parity-Check Codes<\/i> MIT Press, Cambridge, MA, 1963.","DOI":"10.7551\/mitpress\/4347.001.0001"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.3934\/amc.2011.5.555"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"N. Halabi,<i>On Decoding Tanner Codes With Local-Optimality Guarantees<\/i> Ph.D. dissertation, Tel Aviv University, Israel, 2012.","DOI":"10.1109\/ISIT.2012.6284007"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.839509"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2094830"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"N. Halabi and G. Even,<i>On decoding irregular Tanner codes with local-optimality guarantees<\/i> IEEE Trans. Inform. Theory, (2013), in press.","DOI":"10.1109\/TIT.2013.2284912"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2006.12.010"},{"key":"atypb19","unstructured":"R. Koetter and P. O. Vontobel,<i>On the block error probability of LP decoding of LDPC codes<\/i> in Proceedings of the Inaugural Workshop of the Center for Information Theory and its Applications, 2006."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2137030"},{"key":"atypb21","unstructured":"P. O. Vontobel and R. Koetter,<i>Graph-Cover Decoding and Finite-Length Analysis of Message-Passing Iterative Decoding of LDPC Codes<\/i> arXiv:cs\/0512078, 2005."},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"P. O. Vontobel,<i>A factor-graph-based random walk, and its relevance for LP decoding analysis and Bethe entropy characterization<\/i> in Proceedings of the Information Theory and Applications Workshop, 2010.","DOI":"10.1109\/ITA.2010.5454077"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2264715"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1049\/el:20010755"},{"key":"atypb25","unstructured":"N. Wiberg,<i>Codes And Decoding on General Graphs<\/i> Ph.D. dissertation, Link\u00f6ping University, Link\u00f6ping, Sweden, 1996."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120886674","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:23:10Z","timestamp":1787318590000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120886674"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/120886674"],"URL":"https:\/\/doi.org\/10.1137\/120886674","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}