{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:26:55Z","timestamp":1750307215237,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,1,8]],"date-time":"2012-01-08T00:00:00Z","timestamp":1325980800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["240258"],"award-info":[{"award-number":["240258"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2006104"],"award-info":[{"award-number":["2006104"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2012,1,8]]},"DOI":"10.1145\/2090236.2090251","type":"proceedings-article","created":{"date-parts":[[2012,1,10]],"date-time":"2012-01-10T17:02:17Z","timestamp":1326214937000},"page":"168-182","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Linear time decoding of regular expander codes"],"prefix":"10.1145","author":[{"given":"Michael","family":"Viderman","sequence":"first","affiliation":[{"name":"Technion -- Israel Institute of Technology, Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2012,1,8]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_1_1_1","DOI":"10.1109\/TIT.2002.1003853"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.1109\/TIT.2005.860415"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_3_1","DOI":"10.1109\/TIT.2004.824917"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.1109\/TIT.2009.2030477"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.1145\/509907.510003"},{"unstructured":"J. Feldman. Decoding error-correcting codes via linear programming. PhD thesis 2003.   J. Feldman. Decoding error-correcting codes via linear programming . PhD thesis 2003.","key":"e_1_3_2_1_6_1"},{"volume-title":"M.-Y","year":"2008","author":"Feldman J.","key":"e_1_3_2_1_7_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_8_1","DOI":"10.1016\/j.jcss.2003.11.005"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1109\/TIT.2006.887523"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_10_1","DOI":"10.7551\/mitpress\/4347.001.0001"},{"volume-title":"Wiley","year":"1968","author":"Gallager R. G.","key":"e_1_3_2_1_11_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1145\/509907.510023"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_13_1","DOI":"10.1145\/780542.780562"},{"doi-asserted-by":"crossref","unstructured":"V.\n       \n      Guruswami\n     and \n      \n      \n      P.\n       \n      Indyk\n      \n  \n  . \n  Linear-time list decoding in error-free settings. In J. D\u00edaz J. Karhum\u00e4ki A. Lepist\u00f6 and D. Sannella editors ICALP volume \n  3142\n   of \n  Lecture Notes in Computer Science pages \n  695\n  --\n  707\n  . \n  Springer 2004\n  .  V. Guruswami and P. Indyk. Linear-time list decoding in error-free settings. In J. D\u00edaz J. Karhum\u00e4ki A. Lepist\u00f6 and D. Sannella editors ICALP volume 3142 of Lecture Notes in Computer Science pages 695--707. Springer 2004.","key":"e_1_3_2_1_14_1","DOI":"10.1007\/978-3-540-27836-8_59"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1109\/TIT.2005.855587"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.1007\/BF02126799"},{"unstructured":"D. J. C.\n       \n      MacKay\n     and \n      \n      \n      R. M.\n       \n      Neal\n      \n  \n  . \n  Good codes based on very sparse matrices. In C. Boyd editor Proceedings of the 5th IMA Conference on Cryptography and Coding (Cirencester United Kingdom December 18--20 1995\n  ) volume \n  1025\n   of \n  LNCS pages \n  100\n  --\n  111\n  . \n  Springer-Verlag Berlin-Heidelberg-\n  New\n   York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest 1995.   D. J. C. MacKay and R. M. Neal. Good codes based on very sparse matrices. In C. Boyd editor Proceedings of the 5th IMA Conference on Cryptography and Coding (Cirencester United Kingdom December 18--20 1995) volume 1025 of LNCS pages 100--111. Springer-Verlag Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong-Barcelona-Budapest 1995.","key":"e_1_3_2_1_17_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.1049\/el:19961141"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1007\/BF02579283"},{"volume-title":"Networks of Plausible Inference. Morgan Kaufmann","year":"1988","author":"Pearl J.","key":"e_1_3_2_1_20_1"},{"key":"e_1_3_2_1_21_1","first-page":"155","article-title":"Entropy waves, the zig-zag graph product, and new constant-degree expanders","year":"2002","journal-title":"ANNALSMTH: Annals of Mathematics"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_22_1","DOI":"10.1109\/18.910577"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1109\/18.910579"},{"key":"e_1_3_2_1_24_1","first-page":"245","volume-title":"Information Theory Workshop","author":"Roth R. M.","year":"2003"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_25_1","DOI":"10.1109\/TIT.2006.878232"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.1109\/SFCS.1994.365734"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_27_1","DOI":"10.1109\/18.556668"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.1145\/346048.346049"},{"unstructured":"M. H. Taghavi A. Shokrollahi and P. H. Siegel. Efficient implementation of linear programming decoding. CoRR abs\/0902.0657 2009. informal publication.  M. H. Taghavi A. Shokrollahi and P. H. Siegel. Efficient implementation of linear programming decoding. CoRR abs\/0902.0657 2009. informal publication.","key":"e_1_3_2_1_29_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_30_1","DOI":"10.1109\/TIT.1981.1056404"},{"volume-title":"ECCCTR: Electronic Colloquium on Computational Complexity, technical reports","year":"2004","key":"e_1_3_2_1_31_1"},{"doi-asserted-by":"crossref","unstructured":"P. O. Vontobel. Interior-point algorithms for linear-programming decoding. CoRR abs\/0802.1369 2008. informal publication.  P. O. Vontobel. Interior-point algorithms for linear-programming decoding. CoRR abs\/0802.1369 2008. informal publication.","key":"e_1_3_2_1_32_1","DOI":"10.1109\/ITA.2008.4601085"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_33_1","DOI":"10.1109\/18.910593"},{"issue":"1","key":"e_1_3_2_1_34_1","first-page":"18","article-title":"Estimation of the error-correction complexity of gallger low-density codes","volume":"11","author":"Zyablov V. V.","year":"1976","journal-title":"Problems of Information Transmission"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"ITCS '12","name":"ITCS '12: Innovations in Theoretical Computer Science","location":"Cambridge Massachusetts"},"container-title":["Proceedings of the 3rd Innovations in Theoretical Computer Science Conference"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2090236.2090251","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2090236.2090251","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:46Z","timestamp":1750241206000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2090236.2090251"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1,8]]},"references-count":34,"alternative-id":["10.1145\/2090236.2090251","10.1145\/2090236"],"URL":"https:\/\/doi.org\/10.1145\/2090236.2090251","relation":{},"subject":[],"published":{"date-parts":[[2012,1,8]]},"assertion":[{"value":"2012-01-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}