{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:53:54Z","timestamp":1781078034241,"version":"3.54.1"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,6,1]],"date-time":"2009-06-01T00:00:00Z","timestamp":1243814400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-04-1-0478"],"award-info":[{"award-number":["N00014-04-1-0478"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0343672CCF-0835814CCF-0346991CCF-0830787CCF-0133096"],"award-info":[{"award-number":["CCF-0343672CCF-0835814CCF-0346991CCF-0830787CCF-0133096"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"name":"BSF","award":["2.00E+13"],"award-info":[{"award-number":["2.00E+13"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,6]]},"abstract":"<jats:p>We give an improved explicit construction of highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree (which is polylogarithmic in the number of vertices). Both the degree and the number of right-hand vertices are polynomially close to optimal, whereas the previous constructions of Ta-Shma et al. [2007] required at least one of these to be quasipolynomial in the optimal. Our expanders have a short and self-contained description and analysis, based on the ideas underlying the recent list-decodable error-correcting codes of Parvaresh and Vardy [2005].<\/jats:p>\n          <jats:p>Our expanders can be interpreted as near-optimal \u201crandomness condensers,\u201d that reduce the task of extracting randomness from sources of arbitrary min-entropy rate to extracting randomness from sources of min-entropy rate arbitrarily close to 1, which is a much easier task. Using this connection, we obtain a new, self-contained construction of randomness extractors that is optimal up to constant factors, while being much simpler than the previous construction of Lu et al. [2003] and improving upon it when the error parameter is small (e.g., 1\/poly(n)).<\/jats:p>","DOI":"10.1145\/1538902.1538904","type":"journal-article","created":{"date-parts":[[2009,6,30]],"date-time":"2009-06-30T13:10:17Z","timestamp":1246367417000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":188,"title":["Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes"],"prefix":"10.1145","volume":"56","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, Pennsylvania"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christopher","family":"Umans","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Salil","family":"Vadhan","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, Massachusetts, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,7,2]]},"reference":[{"key":"e_1_2_1_1_1","series-title":"Lecture Notes in Computer Science","volume-title":"On the derandomization of space-bounded computations","author":"Armoni R.","unstructured":"]] Armoni , R. 1998. On the derandomization of space-bounded computations . In RANDOM, M. Luby, J. D. P. Rolim, and M. J. Serna, Eds. Lecture Notes in Computer Science , vol. 1518 . Springer-Verlag , Berlin, Germany , 47--59. ]]Armoni, R. 1998. On the derandomization of space-bounded computations. In RANDOM, M. Luby, J. D. P. Rolim, and M. J. Serna, Eds. Lecture Notes in Computer Science, vol. 1518. Springer-Verlag, Berlin, Germany, 47--59."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702405292"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510003"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217015"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63449"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90040-4"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v28:4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268765"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199712)11:4%3C315::AID-RSA3%3E3.0.CO;2-1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.995539"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.911222"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.782097"},{"key":"e_1_2_1_13_1","volume-title":"Tech. Rep. TR06-134, Electronic Colloquium on Computational Complexity. October.","author":"Guruswami V.","year":"2006","unstructured":"]] Guruswami , V. , Umans , C. , and Vadhan , S . 2006 . Extractors and condensers from univariate polynomials. Tech. Rep. TR06-134, Electronic Colloquium on Computational Complexity. October. ]]Guruswami, V., Umans, C., and Vadhan, S. 2006. Extractors and condensers from univariate polynomials. Tech. Rep. TR06-134, Electronic Colloquium on Computational Complexity. October."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.38"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73009"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335306"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63486"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/210118.210136"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944836_12"},{"key":"e_1_2_1_21_1","unstructured":"]]Lidl R. and Niederreiter H. 1986. Introduction to Finite Fields and Their applications. Cambridge University Press Cambridge.   ]]Lidl R. and Niederreiter H. 1986. Introduction to Finite Fields and Their applications. Cambridge University Press Cambridge."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780630"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"e_1_2_1_24_1","first-page":"71","article-title":"Explicit constructions of expanders. Probl","volume":"9","author":"Margulis G. A.","year":"1973","unstructured":"]] Margulis , G. A. 1973 . Explicit constructions of expanders. Probl . Pereda\u010di Inf. 9 , 4, 71 -- 80 . ]]Margulis, G. A. 1973. Explicit constructions of expanders. Probl. Pereda\u010di Inf. 9, 4, 71--80.","journal-title":"Pereda\u010di Inf."},{"key":"e_1_2_1_25_1","first-page":"51","article-title":"Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators","volume":"24","author":"Margulis G. A.","year":"1988","unstructured":"]] Margulis , G. A. 1988 . Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators . Probl. Peredachi Inf. 24 , 1, 51 -- 60 . ]]Margulis, G. A. 1988. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Probl. Peredachi Inf. 24, 1, 51--60.","journal-title":"Probl. Peredachi Inf."},{"key":"e_1_2_1_26_1","unstructured":"]]Nelson J. and Woodruff D. P. 2008. Revisiting norm estimation in data streams. CoRR abs\/0811.3648.  ]]Nelson J. and Woodruff D. P. 2008. Revisiting norm estimation in data streams. CoRR abs\/0811.3648."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1546"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0004"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.29"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197329508"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_44"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1824"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703431032"},{"key":"e_1_2_1_34_1","first-page":"18","article-title":"Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors","volume":"8","author":"Reingold O.","year":"2001","unstructured":"]] Reingold , O. , Vadhan , S. P. , and Wigderson , A. 2001 . Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors . Electron. Colloq. Comput. Complex. (ECCC) 8 , 18 . ]]Reingold, O., Vadhan, S. P., and Wigderson, A. 2001. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. Electron. Colloq. Comput. Complex. (ECCC) 8, 18.","journal-title":"Electron. Colloq. Comput. Complex. (ECCC)"},{"key":"e_1_2_1_35_1","first-page":"67","article-title":"Recent developments in explicit constructions of extractors","volume":"77","author":"Shaltiel R.","year":"2002","unstructured":"]] Shaltiel , R. 2002 . Recent developments in explicit constructions of extractors . Bull. European Assoc. Theoret. Comput. Sci. 77 , 67 --. Columns: Computational Complexity. ]]Shaltiel, R. 2002. Recent developments in explicit constructions of extractors. Bull. European Assoc. Theoret. Comput. Sci. 77, 67--. Columns: Computational Complexity.","journal-title":"Bull. European Assoc. Theoret. Comput. Sci."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059516"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"]]Shoup V. 1990. New algorithms for finding irreducible polynomials over finite fields. Math. Comput. 54 189 435--447.  ]]Shoup V. 1990. New algorithms for finding irreducible polynomials over finite fields. Math. Comput. 54 189 435--447.","DOI":"10.1090\/S0025-5718-1990-0993933-0"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979630091X"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0439"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00206-5"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.18"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0053-2"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.838377"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.010"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502099"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00046-1"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050049"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940870"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199712)11:4%3C345::AID-RSA4%3E3.0.CO;2-Z"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132612"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1538902.1538904","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1538902.1538904","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:53Z","timestamp":1750278413000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1538902.1538904"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["10.1145\/1538902.1538904"],"URL":"https:\/\/doi.org\/10.1145\/1538902.1538904","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6]]},"assertion":[{"value":"2008-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-07-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}