{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T16:25:04Z","timestamp":1778948704228,"version":"3.51.4"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,4,6]],"date-time":"2023-04-06T00:00:00Z","timestamp":1680739200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,4,6]],"date-time":"2023-04-06T00:00:00Z","timestamp":1680739200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s00037-023-00235-y","type":"journal-article","created":{"date-parts":[[2023,4,6]],"date-time":"2023-04-06T12:04:27Z","timestamp":1680782667000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Explicit construction of q+1 regular local Ramanujan graphs, for all prime-powers q"],"prefix":"10.1007","volume":"32","author":[{"given":"Rishabh","family":"Batra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nitin","family":"Saxena","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Devansh","family":"Shringi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,4,6]]},"reference":[{"key":"235_CR1","doi-asserted-by":"crossref","unstructured":"Noga Alon & Michael Capalbo (2002). Explicit unique-neighbor expanders. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, (FOCS 2002). Proceedings, 73\u201379. IEEE.","DOI":"10.1109\/SFCS.2002.1181884"},{"key":"235_CR2","doi-asserted-by":"crossref","unstructured":"Benny Applebaum, Yuval Ishai & Eyal Kushilevitz (2006).Cryptography in NC\u02c60. SIAM Journal on Computing 36(4), 845\u2013888.","DOI":"10.1137\/S0097539705446950"},{"key":"235_CR3","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora, David Steurer & Avi Wigderson (2009). Towards a study of low-complexity graphs. In International Colloquium on Automata, Languages, and Programming, 119\u2013131. Springer.","DOI":"10.1007\/978-3-642-02927-1_12"},{"key":"235_CR4","doi-asserted-by":"crossref","unstructured":"Ziv Bar-Yossef, Oded Goldreich & Avi Wigderson (1999).Deterministic amplification of space-bounded probabilistic algorithms.In Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference)(Cat. No. 99CB36317), 188\u2013198. IEEE.","DOI":"10.1109\/CCC.1999.766276"},{"key":"235_CR5","doi-asserted-by":"crossref","unstructured":"Alexander Barg & Gilles Z\u00e9mor (2002). Error exponents of expander codes. IEEE Transactions on Information Theory 48(6), 1725\u20131729.","DOI":"10.1109\/TIT.2002.1003853"},{"key":"235_CR6","doi-asserted-by":"crossref","unstructured":"Ho Yee Cheung, Lap Chi Lau & Kai Man Leung (2011). Graph Connectivities, Network Coding, and Expander Graphs. IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011) 190\u2013199.","DOI":"10.1109\/FOCS.2011.55"},{"key":"235_CR7","doi-asserted-by":"crossref","unstructured":"Scott Diehl & Dieter Van Melkebeek (2006). Time-space lower bounds for the polynomial-time hierarchy on randomized machines. SIAM Journal on Computing 36(3), 563-594.","DOI":"10.1137\/050642228"},{"key":"235_CR8","doi-asserted-by":"crossref","unstructured":"Irit Dinur (2007). The PCP theorem by gap amplification. Journal of the ACM 54(3), 12\u2013es.","DOI":"10.1145\/1236457.1236459"},{"key":"235_CR9","doi-asserted-by":"crossref","unstructured":"Ofer Gabber & Zvi Galil (1981). Explicit constructions of linear sized superconcentrators. Journal of Computer and System Sciences 22(3), 407\u2013420.","DOI":"10.1016\/0022-0000(81)90040-4"},{"key":"235_CR10","unstructured":"Oded Goldreich (2000). Candidate One-Way Functions Based on Expander Graphs. IACR Cryptol. ePrint Arch. 2000, 63."},{"key":"235_CR11","doi-asserted-by":"crossref","unstructured":"Venkatesan Guruswami (2004). Guest column: error-correcting codes and expander graphs. ACM SIGACT News 35(3), 25\u201341.","DOI":"10.1145\/1027914.1027924"},{"key":"235_CR12","doi-asserted-by":"crossref","unstructured":"Dan Gutfreund & Emanuele Viola (2004). Fooling parity tests with parity gates. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 381\u2013392. Springer.","DOI":"10.1007\/978-3-540-27821-4_34"},{"key":"235_CR13","doi-asserted-by":"crossref","unstructured":"Shlomo Hoory, Nathan Linial & Avi Wigderson (2006). Expander graphs and their applications. Bulletin of the American Mathematical Society 43(4), 439\u2013561.","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"235_CR14","doi-asserted-by":"crossref","unstructured":"Shuji Jimbo & Akira Maruoka (1985). Expanders obtained from affine transformations. In Proceedings of the 17th annual ACM Symposium on Theory of Computing (STOC), 88\u201397.","DOI":"10.1145\/22145.22155"},{"key":"235_CR15","unstructured":"Wen-Ching Winnie Li (1993). A survey of Ramanujan graphs. Arithmetic, Geometry, and Coding Theory, Luminy, France 127\u2013143."},{"key":"235_CR16","doi-asserted-by":"crossref","unstructured":"Rudolf Lidl & Harald Niederreiter (1994). Introduction to finite fields and their applications. Cambridge university press.","DOI":"10.1017\/CBO9781139172769"},{"key":"235_CR17","doi-asserted-by":"crossref","unstructured":"Alexander Lubotzky, Ralph Phillips & Peter Sarnak (1988).Ramanujan graphs. Combinatorica 8(3), 261\u2013277.","DOI":"10.1007\/BF02126799"},{"key":"235_CR18","doi-asserted-by":"crossref","unstructured":"Adam Marcus, Daniel A Spielman & Nikhil Srivastava (2013).Interlacing families I: Bipartite Ramanujan graphs of all degrees. InIEEE 54th Annual Symposium on Foundations of Computer Science,529\u2013537. IEEE.","DOI":"10.1109\/FOCS.2013.63"},{"key":"235_CR19","doi-asserted-by":"crossref","unstructured":"Adam W Marcus, Daniel A Spielman & Nikhil Srivastava (2018). Interlacing families IV: Bipartite Ramanujan graphs of all sizes.SIAM Journal on Computing 47(6), 2488\u20132509.","DOI":"10.1137\/16M106176X"},{"key":"235_CR20","unstructured":"Grigorii Aleksandrovich Margulis (1973). Explicit constructions of concentrators. Problemy Peredachi Informatsii 9(4), 71\u201380."},{"key":"235_CR21","doi-asserted-by":"crossref","unstructured":"Moshe Morgenstern (1994). Existence and explicit constructions of q + 1 regular Ramanujan graphs for every prime power q. Journal of Combinatorial Theory, Series B 62(1), 44\u201362.","DOI":"10.1006\/jctb.1994.1054"},{"key":"235_CR22","unstructured":"Elchanan Mossel, Amir Shpilka & Luca Trevisan (2003). On epsilon-Biased Generators in NC\u02c60. In Annual Symposium on Foundations of Computer Science, volume 44, 136\u2013145. Citeseer."},{"key":"235_CR23","doi-asserted-by":"crossref","unstructured":"Alon Nilli (1991). On the second eigenvalue of a graph. Discrete Mathematics 91(2), 207\u2013210.","DOI":"10.1016\/0012-365X(91)90112-F"},{"key":"235_CR24","doi-asserted-by":"crossref","unstructured":"Omer Reingold (2008). Undirected connectivity in log-space. Journal of the ACM (JACM) 55(4), 1\u201324.","DOI":"10.1145\/1391289.1391291"},{"key":"235_CR25","doi-asserted-by":"crossref","unstructured":"Michael Sipser & Daniel A Spielman (1996). Expander codes.IEEE transactions on Information Theory 42(6), 1710\u20131722.","DOI":"10.1109\/18.556667"},{"key":"235_CR26","doi-asserted-by":"crossref","unstructured":"Daniel A Spielman (1999). Constructing error-correcting codes from expander graphs. In Emerging Applications of Number Theory, 591\u2013600.Springer.","DOI":"10.1007\/978-1-4612-1544-8_25"},{"key":"235_CR27","doi-asserted-by":"crossref","unstructured":"Emanuele Viola & Avi Wigderson (2018). Local expanders. computational complexity 27(2), 225\u2013244.","DOI":"10.1007\/s00037-017-0155-1"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00235-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-023-00235-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00235-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,27]],"date-time":"2023-06-27T17:04:20Z","timestamp":1687885460000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-023-00235-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,6]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["235"],"URL":"https:\/\/doi.org\/10.1007\/s00037-023-00235-y","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,6]]},"assertion":[{"value":"30 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 April 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"2"}}