{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:18:44Z","timestamp":1787501924764,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":46,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["CCF-1718695"],"award-info":[{"award-number":["CCF-1718695"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384231","type":"proceedings-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T21:45:25Z","timestamp":1591479925000},"page":"510-523","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Explicit near-Ramanujan graphs of every degree"],"prefix":"10.1145","author":[{"given":"Sidhanth","family":"Mohanty","sequence":"first","affiliation":[{"name":"University of California at Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ryan","family":"O'Donnell","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pedro","family":"Paredes","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2014-06255-7"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030308"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003730200002"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a015"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129167X92000357"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90059-6"},{"key":"e_1_3_2_1_9_1","first-page":"261","article-title":"On the realization of networks in three-dimensional space","volume":"19","author":"B\u0101rzdin\u0161 J\u0101nis","year":"1967","unstructured":"J\u0101nis B\u0101rzdin\u0161 and Andrey Kolmogorov . On the realization of networks in three-dimensional space . Problemy Kibernetiki , 19 : 261 \u2013 268 , 1967 . J\u0101nis B\u0101rzdin\u0161 and Andrey Kolmogorov. On the realization of networks in three-dimensional space. Problemy Kibernetiki, 19:261\u2013268, 1967.","journal-title":"Problemy Kibernetiki"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0029-7"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"e_1_3_2_1_13_1","volume-title":"Lecture notes on random graphs and probabilistic combinatorial optimization.","author":"Bordenave Charles","year":"2016","unstructured":"Charles Bordenave . Lecture notes on random graphs and probabilistic combinatorial optimization. Retrieved from https:\/\/www.math.univ-toulouse.fr\/~bordenave\/coursRG.pdf, 2016 . Charles Bordenave. Lecture notes on random graphs and probabilistic combinatorial optimization. Retrieved from https:\/\/www.math.univ-toulouse.fr\/~bordenave\/coursRG.pdf, 2016."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/080732651"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01285816"},{"key":"e_1_3_2_1_17_1","volume-title":"Ramanujan graphs and Shimura curves.","author":"Clark Pete","year":"2006","unstructured":"Pete Clark . Ramanujan graphs and Shimura curves. Retrieved from http:\/\/alpha.math.uga.edu\/~pete\/ramanujanrevisited.pdf, 2006 . Pete Clark. Ramanujan graphs and Shimura curves. Retrieved from http:\/\/alpha.math.uga.edu\/~pete\/ramanujanrevisited.pdf, 2006."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1515\/FORUM.2008.035"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.37"},{"key":"e_1_3_2_1_20_1","volume-title":"Ramanujan graphs, and 1-factor perturbations. Bulletin of the Belgian Mathematical Society \u2014 Simon Stevin, 13(4):673\u2013680","author":"de la Harpe Pierre","year":"2006","unstructured":"Pierre de la Harpe and Antoine Musitelli . Expanding graphs , Ramanujan graphs, and 1-factor perturbations. Bulletin of the Belgian Mathematical Society \u2014 Simon Stevin, 13(4):673\u2013680 , 2006 . Pierre de la Harpe and Antoine Musitelli. Expanding graphs, Ramanujan graphs, and 1-factor perturbations. Bulletin of the Belgian Mathematical Society \u2014 Simon Stevin, 13(4):673\u2013680, 2006."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.140"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-93-06921-9"},{"key":"e_1_3_2_1_23_1","volume-title":"A proof of Alon\u2019s second eigenvalue conjecture and related problems. Memoirs of the American Mathematical Society, 195(910):viii+100","author":"Friedman Joel","year":"2008","unstructured":"Joel Friedman . A proof of Alon\u2019s second eigenvalue conjecture and related problems. Memoirs of the American Mathematical Society, 195(910):viii+100 , 2008 . Joel Friedman. A proof of Alon\u2019s second eigenvalue conjecture and related problems. Memoirs of the American Mathematical Society, 195(910):viii+100, 2008."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90040-4"},{"key":"e_1_3_2_1_25_1","volume-title":"An NP-complete problem \u2013 some aspects of its solution and some possible applications. Master\u2019s thesis","author":"H\u00e5stad Johan","year":"1984","unstructured":"Johan H\u00e5stad . An NP-complete problem \u2013 some aspects of its solution and some possible applications. Master\u2019s thesis , Uppsala University , 1984 . Johan H\u00e5stad. An NP-complete problem \u2013 some aspects of its solution and some possible applications. Master\u2019s thesis, Uppsala University, 1984."},{"key":"e_1_3_2_1_26_1","series-title":"Advanced Studies in Pure Mathematics","first-page":"280","volume-title":"Automorphic forms and geometry of arithmetic varieties","unstructured":"Ki-ichiro Hashimoto. Zeta functions of finite graphs and representations of p-adic groups . In Automorphic forms and geometry of arithmetic varieties , volume 15 of Advanced Studies in Pure Mathematics , pages 211\u2013 280 . Elsevier, 1989. Ki-ichiro Hashimoto. Zeta functions of finite graphs and representations of p-adic groups. In Automorphic forms and geometry of arithmetic varieties, volume 15 of Advanced Studies in Pure Mathematics, pages 211\u2013280. Elsevier, 1989."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2969\/jmsj\/01830219"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-007-0065-y"},{"issue":"1","key":"e_1_3_2_1_31_1","first-page":"113","article-title":"Derandomized constructions of k-wise (almost) independent permutations","volume":"55","author":"Kaplan Eyal","year":"2009","unstructured":"Eyal Kaplan , Moni Naor , and Omer Reingold . Derandomized constructions of k-wise (almost) independent permutations . Algorithmica. An International Journal in Computer Science , 55 ( 1 ): 113 \u2013 133 , 2009 . Eyal Kaplan, Moni Naor, and Omer Reingold. Derandomized constructions of k-wise (almost) independent permutations. Algorithmica. An International Journal in Computer Science, 55(1):113\u2013133, 2009.","journal-title":"Algorithmica. An International Journal in Computer Science"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1215\/00127094-2010-029"},{"issue":"1","key":"e_1_3_2_1_34_1","first-page":"84","article-title":"Complexity of an optimum nonblocking switching network without reconnections","volume":"9","author":"Margulis Grigory","year":"1973","unstructured":"Grigory Margulis . Complexity of an optimum nonblocking switching network without reconnections . Problemy Peredachi Informatsii , 9 ( 1 ): 84 \u2013 87 , 1973 . Grigory Margulis. Complexity of an optimum nonblocking switching network without reconnections. Problemy Peredachi Informatsii, 9(1):84\u201387, 1973.","journal-title":"Problemy Peredachi Informatsii"},{"issue":"4","key":"e_1_3_2_1_35_1","first-page":"71","article-title":"Explicit construction of concentrators","volume":"94","author":"Margulis Grigory","year":"1973","unstructured":"Grigory Margulis . Explicit construction of concentrators . Problemy Peredachi Informatsii , 94 ( 4 ): 71 \u2013 80 , 1973 . Grigory Margulis. Explicit construction of concentrators. Problemy Peredachi Informatsii, 94(4):71\u201380, 1973.","journal-title":"Problemy Peredachi Informatsii"},{"issue":"1","key":"e_1_3_2_1_36_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 Grigory","year":"1988","unstructured":"Grigory Margulis . Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators . Problemy Peredachi Informatsii , 24 ( 1 ): 51 \u2013 60 , 1988 . Grigory Margulis. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24(1):51\u201360, 1988.","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1054"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2015.182.1.7"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.87"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90112-F"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"e_1_3_2_1_43_1","first-page":"4","volume-title":"Proceedings of the 7th International Teletraffic Congress","author":"Pinsker Mark","year":"1973","unstructured":"Mark Pinsker . On the complexity of a concentrator . In Proceedings of the 7th International Teletraffic Congress , pages 318\/1\u2013318\/ 4 , 1973 . Mark Pinsker. On the complexity of a concentrator. In Proceedings of the 7th International Teletraffic Congress, pages 318\/1\u2013318\/4, 1973."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1990-15918-X"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.2307\/3062153"},{"key":"e_1_3_2_1_46_1","volume-title":"Paris","author":"Serre Jean-Pierre","year":"1977","unstructured":"Jean-Pierre Serre . Arbres, amalgames, SL2. Soci\u00e9t\u00e9 Math\u00e9matique de France , Paris , 1977 . Avec un sommaire anglais, R\u00e9dig\u00e9 avec la collaboration de Hyman Bass, Ast\u00e9risque, No. 46. Jean-Pierre Serre. Arbres, amalgames, SL2. Soci\u00e9t\u00e9 Math\u00e9matique de France, Paris, 1977. Avec un sommaire anglais, R\u00e9dig\u00e9 avec la collaboration de Hyman Bass, Ast\u00e9risque, No. 46."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1990-0993933-0"},{"key":"e_1_3_2_1_48_1","first-page":"2025","volume-title":"Proceedings of the 23rd Annual Conference on Neural Information Processing Systems","author":"Watanabe Yusuke","year":"2009","unstructured":"Yusuke Watanabe and Kenji Fukumizu . Graph zeta function in the Bethe free energy and loopy belief propagation . In Proceedings of the 23rd Annual Conference on Neural Information Processing Systems , pages 2017\u2013 2025 , 2009 . Yusuke Watanabe and Kenji Fukumizu. Graph zeta function in the Bethe free energy and loopy belief propagation. In Proceedings of the 23rd Annual Conference on Neural Information Processing Systems, pages 2017\u20132025, 2009."},{"key":"e_1_3_2_1_49_1","series-title":"London Mathematical Society Lecture Note Series","first-page":"298","volume-title":"Surveys in combinatorics","author":"Wormald Nicholas","year":"1999","unstructured":"Nicholas Wormald . Models of random regular graphs . In Surveys in combinatorics , 1999 ( Canterbury) , volume 267 of London Mathematical Society Lecture Note Series , pages 239\u2013 298 . Cambridge Univ. Press, Cambridge, 1999. Nicholas Wormald. Models of random regular graphs. In Surveys in combinatorics, 1999 (Canterbury), volume 267 of London Mathematical Society Lecture Note Series, pages 239\u2013298. Cambridge Univ. Press, Cambridge, 1999."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384231","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384231","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384231","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:41:12Z","timestamp":1750185672000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384231"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":46,"alternative-id":["10.1145\/3357713.3384231","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384231","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}