{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,7,2]],"date-time":"2022-07-02T07:41:17Z","timestamp":1656747677554},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T00:00:00Z","timestamp":1647388800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T00:00:00Z","timestamp":1647388800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1007\/s00037-022-00220-x","type":"journal-article","created":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T12:03:13Z","timestamp":1647432193000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Expander-Based Cryptography Meets Natural Proofs"],"prefix":"10.1007","volume":"31","author":[{"given":"Igor C.","family":"Oliveira","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Santhanam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roei","family":"Tell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,3,16]]},"reference":[{"key":"220_CR1","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3s Ajtai (1990). Approximate Counting with Uniform Constant-Depth Circuits. In Advances in computational complexity theory, 1\u201320","DOI":"10.1090\/dimacs\/013\/01"},{"key":"220_CR2","doi-asserted-by":"crossref","unstructured":"Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath & Alon Rosen (2014). Candidate weak pseudorandom functions in $$\\sf AC\\it ^0 \\circ \\sf MOD\\it \\,2$$. In Proc. Annual Innovations in Theoretical Computer Science Conference (ITCS), 251-260.","DOI":"10.1145\/2554797.2554821"},{"issue":"4","key":"220_CR3","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1007\/s00037-011-0029-x","volume":"20","author":"Michael Alekhnovich","year":"2011","unstructured":"Alekhnovich, Michael: More on average case vs approximation complexity. Computational Complexity 20(4), 755\u2013786 (2011)","journal-title":"Computational Complexity"},{"key":"220_CR4","doi-asserted-by":"publisher","first-page":"45","DOI":"10.4086\/toc.2011.v007a004","volume":"7","author":"Kazuyuki Amano","year":"2011","unstructured":"Amano, Kazuyuki: Tight bounds on the average sensitivity of $$k$$-CNF. Theory of Computing 7, 45\u201348 (2011)","journal-title":"Theory of Computing"},{"key":"220_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17367-7","volume-title":"Cryptography in Constant Parallel Time","author":"Benny Applebaum","year":"2014","unstructured":"Applebaum, Benny: Cryptography in Constant Parallel Time. Information Security and Cryptography. Springer (2014)"},{"issue":"3","key":"220_CR6","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1007\/s00037-015-0121-8","volume":"25","author":"Benny Applebaum","year":"2016","unstructured":"Applebaum, Benny: Cryptographic Hardness of Random Local Functions. Computational Complexity 25(3), 667\u2013722 (2016)","journal-title":"Computational Complexity"},{"key":"220_CR7","doi-asserted-by":"crossref","unstructured":"Benny Applebaum, Boaz Barak & Avi Wigderson (2010). Public-key cryptography from different assumptions. In Proc. 42nd Annual ACM Symposium on Theory of Computing (STOC), 171\u2013180","DOI":"10.1145\/1806689.1806715"},{"issue":"3","key":"220_CR8","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/s00145-015-9202-8","volume":"29","author":"Benny Applebaum","year":"2016","unstructured":"Applebaum, Benny, Bogdanov, Andrej, Rosen, Alon: A dichotomy for local small-bias generators. Journal of Cryptology 29(3), 577\u2013596 (2016)","journal-title":"Journal of Cryptology"},{"key":"220_CR9","doi-asserted-by":"crossref","unstructured":"Benny Applebaum, Yuval Ishai & Eyal Kushilevitz (2006). Cryptography in $$(NC^0)$$. siam Journal of Computing 36(4), 845\u2013888","DOI":"10.1137\/S0097539705446950"},{"key":"220_CR10","doi-asserted-by":"crossref","unstructured":"Benny Applebaum & Shachar Lovett (2018). Algebraic attacks against random local functions and their countermeasures. SIAM Journal of Computing 47, 52\u201379","DOI":"10.1137\/16M1085942"},{"key":"220_CR11","doi-asserted-by":"crossref","unstructured":"Benny Applebaum & Pavel Raykov (2016). Fast pseudorandom functions based on expander graphs. In Theory of cryptography. Part I, volume 9985 of Lecture Notes in Comput. Sci., 27\u201356. Springer, Berlin","DOI":"10.1007\/978-3-662-53641-4_2"},{"issue":"1","key":"220_CR12","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s00037-011-0034-0","volume":"21","author":"Andrej Bogdanov & Youming Qiao","year":"2012","unstructured":"Andrej Bogdanov & Youming Qiao: On the security of Goldreich\u2019s one-way function. Computational Complexity 21(1), 83\u2013127 (2012)","journal-title":"Computational Complexity"},{"issue":"1","key":"220_CR13","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/s00145-011-9117-y","volume":"26","author":"Andrej Bogdanov & Alon Rosen","year":"2013","unstructured":"Andrej Bogdanov & Alon Rosen: Input locality and hardness amplification. Journal of Cryptology 26(1), 144\u2013171 (2013)","journal-title":"Journal of Cryptology"},{"key":"220_CR14","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0020-0190(97)00131-2","volume":"63","author":"Ravi B Boppana","year":"1997","unstructured":"Boppana, Ravi B.: The Average Sensitivity of Bounded-Depth Circuits. Information Processing Letters 63, 257\u2013261 (1997)","journal-title":"Information Processing Letters"},{"key":"220_CR15","doi-asserted-by":"crossref","unstructured":"Michael Capalbo, Omer Reingold, Salil Vadhan & Avi Wigderson (2002). Randomness Conductors and Constant-degree Lossless Expanders. In Proc. 34th Annual ACM Symposium on Theory of Computing (STOC), 659\u2013668","DOI":"10.1145\/509907.510003"},{"key":"220_CR16","doi-asserted-by":"crossref","unstructured":"Claude Carlet (2010). Boolean functions for cryptography and error-correcting codes. In Boolean models and methods in mathematics, computer science, and engineering, 257\u2013397. Cambridge Univerity Press","DOI":"10.1017\/CBO9780511780448.011"},{"key":"220_CR17","unstructured":"Marco\u00a0L. Carmosino, Russell Impagliazzo, Valentine Kabanets & Antonina Kolokolova (2016). Learning algorithms from natural proofs. In Proc. 31st Annual IEEE Conference on Computational Complexity (CCC), 10 (24)"},{"key":"220_CR18","unstructured":"Mahdi Cheraghchi (2005). Applications of Derandomization Theory in Coding. Ph.D. thesis, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne"},{"key":"220_CR19","doi-asserted-by":"crossref","unstructured":"Gil Cohen & Igor Shinkar (2016). The complexity of DNF of parities. In Proc. 7th Annual Innovations in Theoretical Computer Science Conference (ITCS), 47\u201358","DOI":"10.1145\/2840728.2840734"},{"key":"220_CR20","doi-asserted-by":"crossref","unstructured":"James Cook, Omid Etesami, Rachel Miller & Luca Trevisan (2014). On the one-way function candidate proposed by Goldreich. ACM Transactions of Computation Theory 6(3), Art. 14, 35","DOI":"10.1145\/2633602"},{"key":"220_CR21","doi-asserted-by":"crossref","unstructured":"Vitaly Feldman, Will Perkins & Santosh Vempala (2015). On the Complexity of Random Satisfiability Problems with Planted Solutions. In Proc. 47th Annual ACM Symposium on Theory of Computing (STOC), 77\u201386","DOI":"10.1145\/2746539.2746577"},{"key":"220_CR22","first-page":"90","volume":"7","author":"Oded Goldreich","year":"2000","unstructured":"Goldreich, Oded: Candidate One-Way Functions Based on Expander Graphs. Electronic Colloquium on Computational Complexity: ECCC 7, 90 (2000)","journal-title":"Electronic Colloquium on Computational Complexity: ECCC"},{"key":"220_CR23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804106","volume-title":"Computational Complexity: A Conceptual Perspective","author":"Oded Goldreich","year":"2008","unstructured":"Goldreich, Oded: Computational Complexity: A Conceptual Perspective. Cambridge University Press, New York, NY, USA (2008)"},{"key":"220_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/978-3-642-22670-0_10","volume-title":"Studies in complexity and cryptography","author":"Oded Goldreich","year":"2011","unstructured":"Goldreich, Oded: Candidate one-way functions based on expander graphs. In: Studies in complexity and cryptography. Lecture Notes in Computer Science, vol. 6650, pp. 76\u201387. Springer, Heidelberg (2011)"},{"issue":"4","key":"220_CR25","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"Oded Goldreich","year":"1986","unstructured":"Goldreich, Oded, Goldwasser, Shafi, Micali, Silvio: How to construct random functions. Journal of the ACM 33(4), 792\u2013807 (1986)","journal-title":"Journal of the ACM"},{"key":"220_CR26","doi-asserted-by":"crossref","unstructured":"Venkatesan Guruswami, Christopher Umans & Salil Vadhan (2009). Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. Journal of the ACM 56(4), Art. 20, 34","DOI":"10.1145\/1538902.1538904"},{"issue":"2","key":"220_CR27","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0022-0000(93)90001-D","volume":"46","author":"Andr\u00e1s Hajnal","year":"1993","unstructured":"Hajnal, Andr\u00e1s, Maass, Wolfgang, Pudl\u00e1k, Pavel, Szegedy, M\u00e1ri\u00f3., Tur\u00e1n, Gy\u00f6rgy.: Threshold circuits of bounded depth. Journal of Computer and System Sciences 46(2), 129\u2013154 (1993)","journal-title":"Journal of Computer and System Sciences"},{"key":"220_CR28","volume-title":"Computational Limitations of Small-depth Circuits","author":"Johan H\u00e5stad","year":"1987","unstructured":"H\u00e5stad, Johan: Computational Limitations of Small-depth Circuits. MIT Press (1987)"},{"issue":"5","key":"220_CR29","doi-asserted-by":"publisher","first-page":"1699","DOI":"10.1137\/120897432","volume":"43","author":"Johan H\u00e5stad","year":"2014","unstructured":"H\u00e5stad, Johan: On the correlation of parity and small-depth circuits. SIAM Journal of Computing 43(5), 1699\u20131708 (2014)","journal-title":"SIAM Journal of Computing"},{"key":"220_CR30","doi-asserted-by":"crossref","unstructured":"Stasys Jukna (2012). Boolean function complexity, volume\u00a027 of Algorithms and Combinatorics. Springer, Heidelberg. Advances and frontiers","DOI":"10.1007\/978-3-642-24508-4"},{"key":"220_CR31","unstructured":"Swastik Kopparty & Srikanth Srinivasan (2012). Certifying polynomials for $$\\rm AC^0[\\oplus ]$$ circuits, with applications. In Proc. 32nd Annual Conference on Foundations of Software Technology and Theoretical Computer Science fsttcs, 36\u201347"},{"issue":"3","key":"220_CR32","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"Nathan Linial","year":"1993","unstructured":"Linial, Nathan, Mansour, Yishay, Nisan, Noam: Constant depth circuits, Fourier transform, and learnability. Journal of the Association for Computing Machinery 40(3), 607\u2013620 (1993)","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"1","key":"220_CR33","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1002\/rsa.20112","volume":"29","author":"Elchanan Mossel","year":"2006","unstructured":"Mossel, Elchanan, Shpilka, Amir, Trevisan, Luca: On $$\\epsilon $$-biased generators in $${\\rm NC}^0$$. Random Structures & Algorithms 29(1), 56\u201381 (2006)","journal-title":"Random Structures & Algorithms"},{"issue":"1","key":"220_CR34","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/BF01375474","volume":"11","author":"Noam Nisan","year":"1991","unstructured":"Nisan, Noam: Pseudorandom bits for constant depth circuits. Combinatorica 11(1), 63\u201370 (1991)","journal-title":"Combinatorica"},{"key":"220_CR35","doi-asserted-by":"crossref","unstructured":"Noam Nisan & Avi Wigderson (1994). Hardness vs. randomness. Journal of Computer and System Sciences 49(2), 149\u2013167","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"220_CR36","doi-asserted-by":"crossref","unstructured":"Ryan O'Donnell & Rocco\u00a0A. Servedio (2008). Extremal properties of polynomial threshold functions. 74(3), 298\u2013312","DOI":"10.1016\/j.jcss.2007.06.021"},{"key":"220_CR37","doi-asserted-by":"crossref","unstructured":"Ryan O'Donnell & David Witmer (2014). Goldreich's PRG: evidence for near-optimal polynomial stretch. In 29th, 1\u201312","DOI":"10.1109\/CCC.2014.9"},{"key":"220_CR38","unstructured":"Igor\u00a0Carboni Oliveira, Rahul Santhanam & Roei Tell (2018). Expander-Based Cryptography Meets Natural Proofs. In Proc. In 10th Annual Innovations in Theoretical Computer Science Conference itcs, 18:1\u201318:14"},{"issue":"4","key":"220_CR39","first-page":"333","volume":"41","author":"Alexander A Razborov","year":"1987","unstructured":"Razborov, Alexander A.: Lower bounds on the size of constant-depth networks over a complete basis with logical addition. Mathematical Notes of the Academy of Science of the USSR 41(4), 333\u2013338 (1987)","journal-title":"Mathematical Notes of the Academy of Science of the USSR"},{"key":"220_CR40","doi-asserted-by":"crossref","unstructured":"Alexander\u00a0A. Razborov & Steven Rudich (1997). Natural proofs. Journal of Computer and System Sciences 55(1, part 1), 24\u201335","DOI":"10.1006\/jcss.1997.1494"},{"key":"220_CR41","doi-asserted-by":"crossref","unstructured":"Roman Smolensky (1987). Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In Proc. 19th Annual ACM Symposium on Theory of Computing stoc, 77\u201382","DOI":"10.1145\/28395.28404"},{"issue":"2","key":"220_CR42","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/s00493-007-0053-2","volume":"27","author":"Amnon Ta-Shma","year":"2007","unstructured":"Ta-Shma, Amnon, Umans, Christopher, Zuckerman, David: Lossless condensers, unbalanced expanders, and extractors. Combinatorica 27(2), 213\u2013240 (2007)","journal-title":"Combinatorica"},{"key":"220_CR43","unstructured":"Avishay Tal (2017). Tight Bounds on the Fourier Spectrum of AC0. In Proc. 32nd Annual IEEE Conference on Computational Complexity (CCC), 15:1\u201315:31"},{"issue":"4","key":"220_CR44","doi-asserted-by":"publisher","first-page":"860","DOI":"10.1145\/502090.502099","volume":"48","author":"Luca Trevisan","year":"2001","unstructured":"Trevisan, Luca: Extractors and Pseudorandom Generators. Journal of the acm 48(4), 860\u2013879 (2001)","journal-title":"Journal of the acm"},{"key":"220_CR45","doi-asserted-by":"crossref","unstructured":"Salil\u00a0P. Vadhan (2012). Pseudorandomness. Foundations and Trends in Theoretical Computer Science. Now Publishers","DOI":"10.1561\/9781601985958"},{"issue":"3","key":"220_CR46","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s00037-009-0267-3","volume":"18","author":"Emanuele Viola","year":"2009","unstructured":"Viola, Emanuele: On Approximate Majority and Probabilistic Time. Computational Complexity 18(3), 337\u2013375 (2009)","journal-title":"Computational Complexity"},{"key":"220_CR47","doi-asserted-by":"crossref","unstructured":"Emanuele Viola & Avi Wigderson (2017). Local Expanders. Computational Complexity","DOI":"10.1007\/s00037-017-0155-1"},{"key":"220_CR48","unstructured":"Avi Wigderson (2018). Mathematics and Computation (book draft). Accessed at https:\/\/www.math.ias.edu\/avi\/book, August 26, 2018."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-022-00220-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-022-00220-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-022-00220-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,2]],"date-time":"2022-07-02T07:13:12Z","timestamp":1656745992000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-022-00220-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,16]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["220"],"URL":"https:\/\/doi.org\/10.1007\/s00037-022-00220-x","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,16]]},"assertion":[{"value":"13 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 March 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"4"}}