{"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":1778948704650,"version":"3.51.4"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T00:00:00Z","timestamp":1497916800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1007\/s00037-017-0155-1","type":"journal-article","created":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T13:54:51Z","timestamp":1497966891000},"page":"225-244","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Local Expanders"],"prefix":"10.1007","volume":"27","author":[{"given":"Emanuele","family":"Viola","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,6,20]]},"reference":[{"key":"155_CR1","doi-asserted-by":"crossref","unstructured":"Noga Alon & Michael R. Capalbo (2002). Explicit Unique-Neighbor Expanders. In IEEE Symp. on Foundations of Computer Science (FOCS), 73\u201379.","DOI":"10.1109\/SFCS.2002.1181884"},{"key":"155_CR2","doi-asserted-by":"crossref","unstructured":"Noga Alon, Alexander Lubotzky & Avi Wigderson (2001). Semi-Direct Product in Groups and Zigzag Product in Graphs: Connections and Applications. In IEEE Symp. on Foundations of Computer Science (FOCS), 630\u2013637. URL http:\/\/dx.doi.org\/10.1109\/SFCS.2001.959939 .","DOI":"10.1109\/SFCS.2001.959939"},{"issue":"4","key":"155_CR3","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1137\/S0097539705446950","volume":"36","author":"Applebaum Benny","year":"2006","unstructured":"Benny Applebaum, Yuval Ishai, Eyal Kushilevitz (2006) Cryptography in NC0. SIAM J. on Computing 36(4): 845\u2013888","journal-title":"SIAM J. on Computing"},{"key":"155_CR4","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora, David Steurer & Avi Wigderson (2009). Towards a Study of Low-Complexity Graphs. In Coll. on Automata, Languages and Programming (ICALP), 119\u2013131.","DOI":"10.1007\/978-3-642-02927-1_12"},{"key":"155_CR5","doi-asserted-by":"crossref","unstructured":"Ziv Bar-Yossef, Oded Goldreich & Avi Wigderson. (1999). Deterministic Amplification of Space Bounded Probabilistic Algorithms. In IEEE Conf. on Computational Complexity (CCC), 188\u2013198.","DOI":"10.1109\/CCC.1999.766276"},{"key":"155_CR6","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson & Emanuele Viola (2014). Short PCPs with projection queries. In Coll. on Automata, Languages and Programming (ICALP).","DOI":"10.1007\/978-3-662-43948-7_14"},{"key":"155_CR7","doi-asserted-by":"crossref","unstructured":"Michael R. Capalbo, Omer Reingold, Salil P. Vadhan & Avi Wigderson (2002). Randomness conductors and constant-degree lossless expanders. In ACM Symp. on the Theory of Computing (STOC), 659\u2013668. URL http:\/\/doi.acm.org\/10.1145\/509907.510003 .","DOI":"10.1145\/509907.510003"},{"key":"155_CR8","doi-asserted-by":"crossref","unstructured":"Aviad Cohen & Avi Wigderson (1989). Dispersers, Deterministic Amplification, and Weak Random Sources. In 30th Symposium on Foundations of Computer Science, 14\u201319. IEEE, Research Triangle Park, North Carolina.","DOI":"10.1109\/SFCS.1989.63449"},{"key":"155_CR9","unstructured":"Mary Cryan & Peter Bro Miltersen (2001). On Pseudorandom Generators in NC 0. In 26th Symposium on Mathematical Foundations of Computer Science (MFCS 01), 272\u2013284. Springer-Verlag."},{"issue":"3","key":"155_CR10","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1137\/050642228","volume":"36","author":"Diehl Scott","year":"2006","unstructured":"Scott Diehl, Dieter van Melkebeek (2006) Time-space lower bounds for the polynomial-time hierarchy on randomized machines. SIAM J. on Computing 36(3): 563\u2013594","journal-title":"SIAM J. on Computing"},{"key":"155_CR11","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"Gabber Ofer","year":"1981","unstructured":"Ofer Gabber, Zvi Galil (1981) Explicit constructions of linear size superconcentrators. J. of Computer and System Sciences 22: 407\u2013420","journal-title":"J. of Computer and System Sciences"},{"key":"155_CR12","unstructured":"Oded Goldreich (2000). Candidate One-Way Functions Based on Expander Graphs. Technical report, Electronic Colloquium on Computational Complexity."},{"key":"155_CR13","doi-asserted-by":"crossref","unstructured":"Oded Goldreich (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press, xx+372.","DOI":"10.1017\/CBO9780511546891"},{"key":"155_CR14","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan & David Zuckerman (1990). Security Preserving Amplification of Hardness. In 31st IEEE Symposium on Foundations of Computer Science (FOCS), 318\u2013326.","DOI":"10.1109\/FSCS.1990.89550"},{"key":"155_CR15","unstructured":"Dan Gutfreund & Emanuele Viola (2004). Fooling Parity Tests with Parity Gates. In 8thWorkshop on Randomization and Computation (RANDOM), 381\u2013392. Springer."},{"key":"155_CR16","doi-asserted-by":"crossref","unstructured":"Alexander Healy & Emanuele Viola (2006). Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two. In 23rd Symp. on Theoretical Aspects of Computer Science (STACS), 672\u2013683. Springer.","DOI":"10.1007\/11672142_55"},{"key":"155_CR17","doi-asserted-by":"crossref","unstructured":"Shlomo Hoory, Nathan Linial & Avi Wigderson (2006). Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.) 43(4), 439\u2013561 (electronic). ISSN 0273-0979. URL http:\/\/dx.doi.org\/10.1090\/S0273-0979-06-01126-8 .","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"155_CR18","unstructured":"Hamid Jahanjou, Eric Miles & Emanuele Viola (2015). Local reductions. In Coll. on Automata, Languages and Programming (ICALP). Available at http:\/\/www.ccs.neu.edu\/home\/viola\/ ."},{"issue":"4","key":"155_CR19","first-page":"343","volume":"7","author":"S. Jimbo","year":"1987","unstructured":"Jimbo S., Maruoka A. (1987) Expanders obtained from affine transformations. Combinatorica. An Journal of the J\u00e1nos Bolyai Mathematical Society 7(4): 343\u2013355","journal-title":"Combinatorica. An Journal of the J\u00e1nos Bolyai Mathematical Society"},{"key":"155_CR20","doi-asserted-by":"crossref","unstructured":"Martin Kassabov (2007). Symmetric groups and expander graphs. Invent. Math. 170(2), 327\u2013354. ISSN 0020-9910. URL http:\/\/dx.doi.org\/10.1007\/s00222-007-0065-y .","DOI":"10.1007\/s00222-007-0065-y"},{"key":"155_CR21","doi-asserted-by":"crossref","unstructured":"J. H. van Lint (1999). Introduction to coding theory. Springer-Verlag, Berlin, 3rd edition, xiv+227.","DOI":"10.1007\/978-3-642-58575-3"},{"issue":"3","key":"155_CR22","first-page":"261","volume":"8","author":"Alexander Lubotzky","year":"1988","unstructured":"Lubotzky Alexander, Phillips R., Sarnak P. (1988) Ramanujan graphs. Combinatorica. A Journal of the J\u00e1nos Bolyai Mathematical Society 8(3): 261\u2013277","journal-title":"Combinatorica. A Journal of the J\u00e1nos Bolyai Mathematical Society"},{"key":"155_CR23","doi-asserted-by":"crossref","unstructured":"Adam W. Marcus, Daniel A. Spielman & Nikhil Srivastava (2015). Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes. In IEEE Symp. on Foundations of Computer Science (FOCS), 1358\u20131377. URL http:\/\/dx.doi.org\/10.1109\/FOCS.2015.87 .","DOI":"10.1109\/FOCS.2015.87"},{"key":"155_CR24","first-page":"325","volume":"9","author":"G.A. Margulis","year":"1973","unstructured":"Margulis G.A. (1973) Explicit construction of concentrators. Problems Inform. Transmission 9: 325\u2013332","journal-title":"Problems Inform. Transmission"},{"key":"155_CR25","unstructured":"M. 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. ISSN 0095-8956. URL http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0095895684710549 ."},{"issue":"1","key":"155_CR26","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1002\/rsa.20112","volume":"29","author":"Mossel Elchanan","year":"2006","unstructured":"Elchanan Mossel, Amir Shpilka, Luca Trevisan (2006) On epsilon-biased generators in NC0. Random Struct. Algorithms 29(1): 56\u201381","journal-title":"Random Struct. Algorithms"},{"key":"155_CR27","doi-asserted-by":"crossref","unstructured":"Omer Reingold, Salil Vadhan & Avi Wigderson (2002). Entropy waves, the zigzag graph product, and new constant-degree expanders. Ann. of Math. (2) 155(1), 157\u2013187. ISSN 0003-486X. http:\/\/dx.doi.org\/10.2307\/3062153 .","DOI":"10.2307\/3062153"},{"key":"155_CR28","unstructured":"Nicholas Pippenger Richard Karp & Michael Sipser (1985). A time-randomness tradeoff. In AMS Conference on Probabilistic Computational Complexity."},{"key":"155_CR29","doi-asserted-by":"crossref","unstructured":"Eyal Rozenman, Aner Shalev & Avi Wigderson (2006). Iterative Construction of Cayley Expander Graphs. Theory of Computing 2(5), 91\u2013120. URL http:\/\/dx.doi.org\/10.4086\/toc.2006.v002a005 .","DOI":"10.4086\/toc.2006.v002a005"},{"key":"155_CR30","doi-asserted-by":"crossref","unstructured":"Salil P. Vadhan (2012). Pseudorandomness. Foundations and Trends in Theoretical Computer Science 7(1\u20133), 1\u2013336. URL http:\/\/dx.doi.org\/10.1561\/0400000010 .","DOI":"10.1561\/0400000010"},{"issue":"1","key":"155_CR31","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1137\/100814998","volume":"41","author":"Viola Emanuele","year":"2012","unstructured":"Emanuele Viola (2012) The complexity of distributions. SIAM J. on Computing 41(1): 191\u2013218","journal-title":"SIAM J. on Computing"},{"key":"155_CR32","unstructured":"Ryan Williams (2014). Nonuniform ACC Circuit Lower Bounds. J. of the ACM 61(1), 2:1\u20132:32. URL http:\/\/doi.acm.org\/10.1145\/2559903 ."},{"key":"155_CR33","doi-asserted-by":"crossref","unstructured":"Andrew Yao (1982). Theory and Applications of Trapdoor Functions. In 23rd IEEE Symp. on Foundations of Computer Science (FOCS), 80\u201391. IEEE.","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-017-0155-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0155-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0155-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,24]],"date-time":"2023-08-24T02:59:17Z","timestamp":1692845957000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-017-0155-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,20]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["155"],"URL":"https:\/\/doi.org\/10.1007\/s00037-017-0155-1","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,20]]}}}