{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T16:31:29Z","timestamp":1754152289444,"version":"3.41.2"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T00:00:00Z","timestamp":1736121600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T00:00:00Z","timestamp":1736121600000},"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":[[2025,6]]},"DOI":"10.1007\/s00037-024-00260-5","type":"journal-article","created":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T10:34:46Z","timestamp":1736159686000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Structure of Learnability beyond P\/poly"],"prefix":"10.1007","volume":"34","author":[{"given":"Ninad","family":"Rajgopal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Santhanam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,6]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Adi Akavia, Oded Goldreich, Shafi Goldwasser & Dana\nMoshkovitz (2006). On basing one-way functions on NP-hardness.\nIn Proceedings of the 38th ACM Symposium on Theory of Computing,\nSeattle, 2006, 701\u2013710.","key":"260_CR1","DOI":"10.1145\/1132516.1132614"},{"doi-asserted-by":"crossref","unstructured":"Eric Allender (2001). When worlds collide: Derandomization, lower\nbounds, and Kolmogorov complexity. In International Conference on\nFoundations of Software Technology and Theoretical Computer Science,\n1\u201315.","key":"260_CR2","DOI":"10.1007\/3-540-45294-X_1"},{"doi-asserted-by":"crossref","unstructured":"Eric Allender, Harry Buhrman, Michal Kouck\u00fd, Dieter Van Melkebeek & Detlef Ronneburger (2006). Power from random\nstrings. SIAM Journal on Computing 35(6), 1467\u20131493.","key":"260_CR3","DOI":"10.1137\/050628994"},{"doi-asserted-by":"crossref","unstructured":"Dana Angluin (1988). Queries and concept learning. Machine learning\n2(4), 319\u2013342.","key":"260_CR4","DOI":"10.1023\/A:1022821128753"},{"doi-asserted-by":"crossref","unstructured":"Benny Applebaum, Boaz Barak & David Xiao (2008). On Basing\nLower-Bounds for Learning on Worst-Case Assumptions. In 49th IEEE\nSymposium on Foundations of Computer Science, FOCS 2008, 211\u2013220.","key":"260_CR5","DOI":"10.1109\/FOCS.2008.35"},{"doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai, Lance Fortnow & Carsten Lund (1991). Nondeterministic\nexponential time has two-prover interactive protocols.\nComputational complexity 1(1), 3\u201340.","key":"260_CR6","DOI":"10.1007\/BF01200056"},{"doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai, Lance Fortnow, Noam Nisan & Avi Wigderson\n(1993). BPP Has Subexponential Time Simulations Unless EXPTIME\nhas Publishable Proofs. Computational Complexity 3, 307\u2013318.","key":"260_CR7","DOI":"10.1007\/BF01275486"},{"doi-asserted-by":"crossref","unstructured":"Avrim Blum, Merrick Furst, Michael Kearns & Richard J\nLipton (1993). Cryptographic primitives based on hard learning problems.\nIn International Cryptology Conference, 278\u2013291.","key":"260_CR8","DOI":"10.1007\/3-540-48329-2_24"},{"doi-asserted-by":"crossref","unstructured":"Andrej Bogdanov & Chris Brzuska (2015). On Basing Size-\nVerifiable One-Way Functions on NP-Hardness. In 12th Theory of\nCryptography Conference, TCC 2015, volume 9014 of Lecture Notes\nin Computer Science, 1\u20136.","key":"260_CR9","DOI":"10.1007\/978-3-662-46494-6_1"},{"doi-asserted-by":"crossref","unstructured":"Andrej Bogdanov & Luca Trevisan (2006). On worst-case to\naverage-case reductions for NP problems. SIAM Journal on Computing\n36(4), 1119\u20131159.","key":"260_CR10","DOI":"10.1137\/S0097539705446974"},{"doi-asserted-by":"crossref","unstructured":"Harry Buhrman, Lance Fortnow & Thomas Thierauf (1998).\nNonrelativizing separations. In Proceedings. Thirteenth IEEE Conference\non Computational Complexity (Formerly: Structure in Complexity\nTheory Conference)(Cat. No. 98CB36247), 8\u201312.","key":"260_CR11","DOI":"10.1109\/CCC.1998.694585"},{"unstructured":"Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets\n& Antonina Kolokolova (2016). Learning Algorithms from\nNatural Proofs. In 31st Conference on Computational Complexity, CCC\n2016, 10:1\u201310:24.","key":"260_CR12"},{"doi-asserted-by":"crossref","unstructured":"Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, J\u00e1n\nPich, Ninad Rajgopal & Rahul Santhanam (2022). Beyond natural\nproofs: Hardness magnification and locality. ACM Journal of the\nACM (JACM) 69(4), 1\u201349.","key":"260_CR13","DOI":"10.1145\/3538391"},{"doi-asserted-by":"crossref","unstructured":"Joan Feigenbaum & Lance Fortnow (1993). Random-selfreducibility\nof complete sets. SIAM Journal on Computing 22(5), 994\u2013\n1005.","key":"260_CR14","DOI":"10.1137\/0222061"},{"doi-asserted-by":"crossref","unstructured":"Lance Fortnow & Adam R Klivans (2009). Efficient learning algorithms\nyield circuit lower bounds. Journal of Computer and System\nSciences 75(1), 27\u201336.","key":"260_CR15","DOI":"10.1016\/j.jcss.2008.07.006"},{"doi-asserted-by":"crossref","unstructured":"Lance Fortnow, John Rompel & Michael Sipser (1994). On\nthe power of multi-prover interactive protocols. Theoretical Computer\nScience 134(2), 545\u2013557.","key":"260_CR16","DOI":"10.1016\/0304-3975(94)90251-8"},{"doi-asserted-by":"crossref","unstructured":"Yoav Freund & Robert E Schapire (1997). A decision-theoretic\ngeneralization of on-line learning and an application to boosting. Journal\nof computer and system sciences 55(1), 119\u2013139.","key":"260_CR17","DOI":"10.1006\/jcss.1997.1504"},{"doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Shafi Goldwasser & Silvio Micali (1984). How\nto construct Randolli functions. In 25th Symposium onFoundations of\nComputer Science, 1984., 464\u2013479.","key":"260_CR18","DOI":"10.1109\/SFCS.1984.715949"},{"doi-asserted-by":"crossref","unstructured":"Dan Gutfreund, Ronen Shaltiel & Amnon Ta-Shma (2007). If\nNP Languages are Hard on the Worst-Case, Then it is Easy to Find\nTheir Hard Instances. Comput. Complex. 16(4), 412\u2013441.","key":"260_CR19","DOI":"10.1007\/s00037-007-0235-8"},{"doi-asserted-by":"crossref","unstructured":"Dan Gutfreund & Salil P. Vadhan (2008). Limitations of Hardness\nvs. Randomness under Uniform Reductions. In Approximation,\nRandomization and Combinatorial Optimization. Algorithms and Techniques,\n11th International Workshop, APPROX 2008, and 12th International\nWorkshop, RANDOM 2008, volume 5171, 469\u2013482.","key":"260_CR20","DOI":"10.1007\/978-3-540-85363-3_37"},{"doi-asserted-by":"crossref","unstructured":"Shuichi Hirahara (2018). Non-Black-Box Worst-Case to Average-\nCase Reductions within NP. In 59th Symposium on Foundations of\nComputer Science, FOCS 2018, Mikkel Thorup, editor, 247\u2013258.","key":"260_CR21","DOI":"10.1109\/FOCS.2018.00032"},{"unstructured":"Shuichi Hirahara & Osamu Watanabe (2020). On Nonadaptive\nSecurity Reductions of Hitting Set Generators. In Approximation,\nRandomization, and Combinatorial Optimization. Algorithms and Techniques,\nAPPROX\/RANDOM 2020, volume 176 of LIPIcs, 15:1\u201315:14.","key":"260_CR22"},{"doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo (2011). Relativized Separations of Worst-Case\nand Average-Case Complexities for NP. In 26th IEEE Conference on\nComputational Complexity, CCC 2011, 104\u2013114.","key":"260_CR23","DOI":"10.1109\/CCC.2011.34"},{"doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo, Valentine Kabanets & Avi Wigderson\n(2002). In search of an easy witness: Exponential time vs. probabilistic\npolynomial time. Journal of Computer and System Sciences 65(4),\n672\u2013694.","key":"260_CR24","DOI":"10.1016\/S0022-0000(02)00024-7"},{"doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo & Leonid A Levin (1990). No better ways to\ngenerate hard NP instances than picking uniformly at random. In 31st\nSymposium on Foundations of Computer Science, 812\u2013821.","key":"260_CR25","DOI":"10.1109\/FSCS.1990.89604"},{"doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo & Avi Wigderson (2001). Randomness vs\nTime: Derandomization under a Uniform Assumption. J. Comput.\nSyst. Sci. 63(4), 672\u2013688.","key":"260_CR26","DOI":"10.1006\/jcss.2001.1780"},{"doi-asserted-by":"crossref","unstructured":"Jeffrey C Jackson (1997). An efficient membership-query algorithm\nfor learning DNF with respect to the uniform distribution. Journal of\nComputer and System Sciences 55(3), 414\u2013440.","key":"260_CR27","DOI":"10.1006\/jcss.1997.1533"},{"doi-asserted-by":"crossref","unstructured":"Richard M Karp & Richard J Lipton (1980). Some connections\nbetween nonuniform and uniform complexity classes. In 12th ACM\nsymposium on Theory of computing, 302\u2013309.","key":"260_CR28","DOI":"10.1145\/800141.804678"},{"doi-asserted-by":"crossref","unstructured":"Michael Kearns & Leslie Valiant (1994). Cryptographic limitations\non learning Boolean formulae and finite automata. Journal of the\nACM (JACM) 41(1), 67\u201395.","key":"260_CR29","DOI":"10.1145\/174644.174647"},{"doi-asserted-by":"crossref","unstructured":"Michael J Kearns & Umesh Vazirani (1994). An introduction to\ncomputational learning theory. MIT press.","key":"260_CR30","DOI":"10.7551\/mitpress\/3897.001.0001"},{"doi-asserted-by":"crossref","unstructured":"Adam R. Klivans, Pravesh Kothari & Igor Carboni Oliveira\n(2013). Constructing Hard Functions Using Learning Algorithms. In\n28th Conference on Computational Complexity, CCC 2013, 86\u201397.","key":"260_CR31","DOI":"10.1109\/CCC.2013.18"},{"doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz & Yishay Mansour (1993). Learning decision\ntrees using the Fourier spectrum. SIAM Journal on Computing 22(6),\n1331\u20131348.","key":"260_CR32","DOI":"10.1137\/0222080"},{"doi-asserted-by":"crossref","unstructured":"Leonid A Levin (1984). Randomness conservation inequalities; information\nand independence in mathematical theories. Information and\nControl 61(1), 15\u201337.","key":"260_CR33","DOI":"10.1016\/S0019-9958(84)80060-1"},{"doi-asserted-by":"crossref","unstructured":"Nathan Linial, Yishay Mansour & Noam Nisan (1993). Constant\ndepth circuits, Fourier transform, and learnability. Journal of the ACM\n(JACM) 40(3), 607\u2013620.","key":"260_CR34","DOI":"10.1145\/174130.174138"},{"doi-asserted-by":"crossref","unstructured":"Carsten Lund, Lance Fortnow, Howard Karloff & Noam\nNisan (1990). Algebraic methods for interactive proof systems. In\n31st Symposium on Foundations of Computer Science, 2\u201310.","key":"260_CR35","DOI":"10.1109\/FSCS.1990.89518"},{"unstructured":"Igor Carboni Oliveira & Rahul Santhanam (2017). Conspiracies\nBetween Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness.\nIn 32nd Computational Complexity Conference, CCC 2017,\n18:1\u201318:49.","key":"260_CR36"},{"unstructured":"Ninad Rajgopal & Rahul Santhanam (2021). On the Structure\nof Learnability Beyond P\/Poly. In Approximation, Randomization,\nand Combinatorial Optimization. Algorithms and Techniques, APPROX\/\nRANDOM 2021, volume 207, 46:1\u201346:23.","key":"260_CR37"},{"doi-asserted-by":"crossref","unstructured":"Robert E Schapire (1990). The strength of weak learnability. Machine\nlearning 5(2), 197\u2013227.","key":"260_CR38","DOI":"10.1023\/A:1022648800760"},{"doi-asserted-by":"crossref","unstructured":"Luca Trevisan & Salil Vadhan (2007). Pseudorandomness and\naverage-case complexity via uniform reductions. Computational Complexity\n16(4), 331\u2013364.","key":"260_CR39","DOI":"10.1007\/s00037-007-0233-x"},{"doi-asserted-by":"crossref","unstructured":"Chee K Yap (1983). Some consequences of non-uniform conditions on\nuniform classes. Theoretical computer science 26(3), 287\u2013300.","key":"260_CR40","DOI":"10.1016\/0304-3975(83)90020-8"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-024-00260-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-024-00260-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-024-00260-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,21]],"date-time":"2025-07-21T23:09:29Z","timestamp":1753139369000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-024-00260-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,6]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["260"],"URL":"https:\/\/doi.org\/10.1007\/s00037-024-00260-5","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2025,1,6]]},"assertion":[{"value":"6 January 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"1"}}