{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:18:43Z","timestamp":1759335523385},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,7,23]],"date-time":"2015-07-23T00:00:00Z","timestamp":1437609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2016,2]]},"DOI":"10.1007\/s00493-014-2715-1","type":"journal-article","created":{"date-parts":[[2015,7,22]],"date-time":"2015-07-22T22:43:18Z","timestamp":1437604998000},"page":"91-120","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Symmetric LDPC codes and local testing"],"prefix":"10.1007","volume":"36","author":[{"given":"Tali","family":"Kaufman","sequence":"first","affiliation":[]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,7,23]]},"reference":[{"key":"2715_CR1","first-page":"4032","volume":"51","author":"N. Alon","year":"2005","unstructured":"N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn and D. Ron: Testing Low Degree Polynomials Over GF(2), in: Proceedings of 7th International Workshop on Randomization and Computation, (RANDOM), Lecture Notes in Computer Science 2764 (2003), 188-199. Also, IEEE Transactions on Information Theory, 51 (2005), 4032\u20134039.","journal-title":"Proceedings of 7th International Workshop on Randomization and Computation, (RANDOM)"},{"key":"2715_CR2","first-page":"630","volume-title":"Proceedings of the 42nd Annual Symposium on the Foundations of Computer Science (FOCS)","author":"N. Alon","year":"2001","unstructured":"N. Alon, A. Lubotzky and A. Wigderson: Semi Direct product in groups and zig-zag product in graphs: connections and applications, in: Proceedings of the 42nd Annual Symposium on the Foundations of Computer Science (FOCS), 630\u2013637, 2001."},{"key":"2715_CR3","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s00493-003-0025-0","volume":"23","author":"S. Arora","year":"2003","unstructured":"S. Arora and M. Sudan: Improved low degree testing and its applications. Combinatorica 23 (2003), 365\u2013426.","journal-title":"Combinatorica"},{"key":"2715_CR4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"L. Babai, L. Fortnow and C. Lund: Non-Deterministic Exponential Time has Two-Prover Interactive Protocols, Computational Complexity 1 (1991), 3\u201340.","journal-title":"Computational Complexity"},{"key":"2715_CR5","doi-asserted-by":"crossref","first-page":"2849","DOI":"10.1109\/TIT.2005.851735","volume":"51","author":"L. Babai","year":"2005","unstructured":"L. Babai, A. Shpilka and D. Stefankovic: Locally testable cyclic codes, IEEE Transactions on Information Theory 51 (2005), 2849\u20132858.","journal-title":"IEEE Transactions on Information Theory"},{"key":"2715_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539704445445","volume":"35","author":"E. Ben-Sasson","year":"2005","unstructured":"E. Ben-Sasson, P. Harsha and S. Raskhodnikova: Some 3CNF Properties are Hard to Test, SIAM Journal on Computing 35 (2005), 1\u201321.","journal-title":"SIAM Journal on Computing"},{"key":"2715_CR7","first-page":"266","volume-title":"STOC 2005","author":"E. Ben-Sasson","year":"2005","unstructured":"E. Ben-Sasson and M. Sudan: Simple PCPs with poly-log rate and query complexity, STOC 2005 266\u2013275, 2005."},{"key":"2715_CR8","first-page":"612","volume-title":"STOC 2003","author":"E. Ben-Sasson","year":"2003","unstructured":"E. Ben-Sasson, M. Sudan, S. Vadhan and A. Wigderson: Randomnessefficient Low Degree Tests and Short PCPs via Epsilon-Biased Sets 35th Annual ACM Symposium, STOC 2003 612\u2013621, 2003."},{"key":"2715_CR9","first-page":"21","volume":"3","author":"S. D. Berman","year":"1967","unstructured":"S. D. Berman: Semisimple Cyclic and Abelian Codes, Cybernetics 3 (1967), 21\u201330.","journal-title":"Cybernetics"},{"key":"2715_CR10","doi-asserted-by":"crossref","unstructured":"M. Blum, M. Luby and R. Rubinfeld: Self-Testing\/Correcting with Applications to Numerical Problems, in: J. Comp. Sys. Sci. 47, 1993.","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"2715_CR11","first-page":"659","volume-title":"Proceedings of the 34th STOC","author":"M. Capalbo","year":"2002","unstructured":"M. Capalbo, O. Reingold, S. Vadhan and A. Wigderson: Randomness Conductors and Constant-Degree Expansion Beyond the Degree \/2 Barrier, Proceedings of the 34th STOC, 659\u2013668, 2002."},{"key":"2715_CR12","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1215\/S0012-7094-57-02406-7","volume":"24","author":"L. Carlitz","year":"1957","unstructured":"L. Carlitz and S. Uchiyama: Bounds for exponential sums, Duke Math. J. 24 (1957), 37\u201341.","journal-title":"Duke Math. J."},{"key":"2715_CR13","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1145\/1236457.1236459","volume":"54","author":"I. Dinur","year":"2007","unstructured":"I. Dinur: The PCP theorem by gap amplification, J. ACM 54 (2007), 12.","journal-title":"J. ACM"},{"key":"2715_CR14","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":"R. G. Gallager: Low density parity check codes, MIT Press, Cambridge, MA, 1963."},{"key":"2715_CR15","doi-asserted-by":"crossref","first-page":"534","DOI":"10.1007\/978-3-642-03685-9_40","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"E. Grigorescu","year":"2009","unstructured":"E. Grigorescu, T. Kaufman and M. Sudan: Succinct Representation of Codes with Applications to Testing, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer Berlin Heidelberg, 2009. 534\u2013547."},{"key":"2715_CR16","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1145\/1162349.1162351","volume":"53","author":"O. Goldreich","year":"2006","unstructured":"O. Goldreich and M. Sudan: Locally testable codes and PCPs of almostlinear length, J. ACM 53 (2006), 558\u2013655.","journal-title":"J. ACM"},{"key":"2715_CR17","volume-title":"Proceedings of the 40th ACM Symposium on Theory of Computing (STOC)","author":"T. Kaufman","year":"2008","unstructured":"T. Kaufman and M. Sudan: Algebraic Property Testing: The Role of Invariance, Proceedings of the 40th ACM Symposium on Theory of Computing (STOC) 2008."},{"key":"2715_CR18","first-page":"317","volume":"2005","author":"T. Kaufman","year":"2005","unstructured":"T. Kaufman and S. Litsyn: Almost Orthogonal Linear Codes are Locally Testable, FOCS 2005 (2005), 317\u2013326.","journal-title":"FOCS"},{"key":"2715_CR19","first-page":"359","volume-title":"STOC 2012","author":"T. Kaufman","year":"2012","unstructured":"T. Kaufman and A. Lubotzky: Edge transitive ramanujan graphs and symmetric LDPC good codes, STOC 2012 359\u2013366, 2012."},{"key":"2715_CR20","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1017\/S0305004108002089","volume":"146","author":"M. Lackenby","year":"2009","unstructured":"M. Lackenby: Large groups, property (T) and the homology growth of subgroups, Math. Proc. Cambridge Philos. Soc. 146 (2009), 625\u2013648.","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"key":"2715_CR21","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1215\/S0012-7094-07-13616-0","volume":"136","author":"M. Lackenby","year":"2007","unstructured":"M. Lackenby: Covering spaces of 3-orbifolds, Duke Math. J. 136 (2007), 181\u2013203.","journal-title":"Duke Math. J."},{"key":"2715_CR22","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/BF02772543","volume":"149","author":"A. Lubotzky","year":"2005","unstructured":"A. Lubotzky, B. Samuels and U. Vishne: Ramanujan complexes of type \u00c3d, Israel Journal of Mathematics 149 (2005), 267\u2013299.","journal-title":"Israel Journal of Mathematics"},{"key":"2715_CR23","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1016\/j.ejc.2004.06.007","volume":"26","author":"A. Lubotzky","year":"2005","unstructured":"A. Lubotzky, B. Samuels and U. Vishne: Explicit constructions of ramanujan complexes of type \u00c3d, Eur. J. Comb. 26 (2005), 965\u2013993.","journal-title":"Eur. J. Comb."},{"key":"2715_CR24","first-page":"95","volume-title":"DIMACS Ser. Discrete Math. Theoret. Compt. Sci.","author":"A. Lubotzky","year":"1993","unstructured":"A. Lubotzky and B. Weiss: Groups and expanders, in: Expanding Graphs (e. J. Friedman), DIMACS Ser. Discrete Math. Theoret. Compt. Sci. 95\u2013109, Amer. Math. Soc., Prividence, RI 1993."},{"key":"2715_CR25","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1109\/18.910576","volume":"47","author":"M. G. Luby","year":"2001","unstructured":"M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman: Improved Low-Density Parity-Check Codes Using Irregular Graphs, IEEE Transactions on Information Theory 47 (2001), 585\u2013598.","journal-title":"IEEE Transactions on Information Theory"},{"key":"2715_CR26","volume-title":"The Theory of Error Correcting Codes","author":"F. J. MacWilliams","year":"1977","unstructured":"F. J. MacWilliams and N. J. A. Sloan: The Theory of Error Correcting Codes, North Holland, Amsterdam, 1977."},{"key":"2715_CR27","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1109\/TIT.1970.1054508","volume":"16","author":"R. J. McElice","year":"1970","unstructured":"R. J. McElice: On the Symmetry of Good Nonlinear Codes, IEEE Trans. Inform. Theory IT 16 (1970), 609\u2013611.","journal-title":"IEEE Trans. Inform. Theory IT"},{"key":"2715_CR28","first-page":"285","volume-title":"Proceedings of STOC 2008","author":"O. Meir","year":"2008","unstructured":"O. Meir: Combinatorial Construction of Locally Testable Codes, Proceedings of STOC 2008 285\u2013294, 2008."},{"key":"2715_CR29","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1007\/s00493-004-0040-9","volume":"24","author":"R. Meshulam","year":"2004","unstructured":"R. Meshulam and A. Wigderson: Expanders in Group Algebras, Combinatorica 24 (2004), 659\u2013680.","journal-title":"Combinatorica"},{"key":"2715_CR30","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"J. Naor and M. Naor: Small-Bias Probability Spaces: Efficient Constructions and Applications, SIAM J. Comput. 22 (1993), 838\u2013856.","journal-title":"SIAM J. Comput."},{"key":"2715_CR31","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"R. Rubinfeld and M. Sudan: Robust characterizations of polynomials with applications to program testing, SIAM Journal on Computing 25 (1996), 252\u2013271.","journal-title":"SIAM Journal on Computing"},{"key":"2715_CR32","first-page":"445","volume-title":"36th Annual ACM Symposium, STOC 2004","author":"E. Rozenman","year":"2004","unstructured":"E. Rozenman, A. Shalev and A. Wigderson: A new family of Cayley expanders (?), 36th Annual ACM Symposium, STOC 2004 445\u2013454, 2004."},{"key":"2715_CR33","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1109\/18.910577","volume":"47","author":"T. Richardson","year":"2001","unstructured":"T. Richardson and R. Urbanke: The Capacity of Low-Density Parity Check Codes under Message-Passing Decoding, IEEE Transactions on Information Theory 47 (2001), 599\u2013618.","journal-title":"IEEE Transactions on Information Theory"},{"key":"2715_CR34","doi-asserted-by":"crossref","first-page":"157","DOI":"10.2307\/3062153","volume":"155","author":"O. Reingold","year":"2002","unstructured":"O. Reingold, S. Vadhan and A. Wigderson: Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders, Annals of Mathematics 155 (2002), 157\u2013187.","journal-title":"Annals of Mathematics"},{"key":"2715_CR35","doi-asserted-by":"crossref","first-page":"1710","DOI":"10.1109\/18.556667","volume":"42","author":"M. Sipser","year":"1996","unstructured":"M. Sipser and D. A. Spielman: Expander codes, IEEE Transactions on Information Theory, 42 (1996), 1710\u20131722.","journal-title":"IEEE Transactions on Information Theory"},{"key":"2715_CR36","unstructured":"M. Sudan: Lecture notes, http:\/\/people.csail.mit.edu\/madhu\/FT01\/scribe\/ bch.ps."},{"key":"2715_CR37","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1006\/jcss.2000.1730","volume":"62","author":"M. Sudan","year":"2001","unstructured":"M. Sudan, L. Trevisan and S. Vadhan: Pseudorandom generators without the XOR Lemma, Journal of Computer and System Sciences 62 (2001), 236\u2013266.","journal-title":"Journal of Computer and System Sciences"},{"key":"2715_CR38","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1109\/TIT.1981.1056404","volume":"27","author":"R. M. Tanner","year":"1981","unstructured":"R. M. Tanner: A recursive approach to low complexity codes, IEEE Transactions on Information Theory 27 (1981), 533\u2013547.","journal-title":"IEEE Transactions on Information Theory"},{"key":"2715_CR39","unstructured":"A. Weil: Sur les courbes algebriques et les varietes qui s'en deduisent Actualities Sci. et Ind. 1041, Hermann, Paris, 1948."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-014-2715-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-014-2715-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-014-2715-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,28]],"date-time":"2019-08-28T16:23:53Z","timestamp":1567009433000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-014-2715-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,23]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["2715"],"URL":"https:\/\/doi.org\/10.1007\/s00493-014-2715-1","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,23]]}}}