{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T16:31:33Z","timestamp":1754152293466,"version":"3.41.2"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T00:00:00Z","timestamp":1743033600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T00:00:00Z","timestamp":1743033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>\nWe revisit known constructions of efficient learning algorithms from various notions of constructive circuit lower bounds such as distinguishers breaking pseudorandom generators or efficient witnessing algorithms which find errors of small circuits attempting to compute hard functions. As our main result, we prove that if it is possible to find efficiently, in a particular interactive way, errors of many <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$p$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>p<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-size circuits attempting to solve hard problems, then <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$p$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>p<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-size circuits can be PAC learned over the uniform distribution with membership queries by circuits of subexponential size. The opposite implication holds as well. This provides a new characterization of learning algorithms and the natural proofs barrier of Razborov and Rudich. The proof is based on a method of reconstructing Nisan-Wigderson generators introduced by Kraj\u00ed\u010dek (2010) and used to analyze complexity of circuit lower bounds in bounded arithmetic.\nAn interesting consequence of known constructions of learning algorithms from circuit lower bounds is a learning speedup of Oliveira and Santhanam (2016). We present an alternative proof of this phenomenon and discuss its potential to advance the program of hardness magnification. \n<\/jats:p>","DOI":"10.1007\/s00037-024-00261-4","type":"journal-article","created":{"date-parts":[[2025,3,29]],"date-time":"2025-03-29T23:17:11Z","timestamp":1743290231000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Learning algorithms from circuit lower bounds"],"prefix":"10.1007","volume":"34","author":[{"given":"J\u00e1n","family":"Pich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,3,27]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Alth\u00f6fer I.; On sparse approximations to randomized strategies\nand convex combinations; Linear Algebra and its Applications,\n199(1):339-355, 1994.","key":"261_CR1","DOI":"10.1016\/0024-3795(94)90357-3"},{"doi-asserted-by":"crossref","unstructured":"Amit N., Goldwasser S., Paradise O., Rothblum G.; Models\nthat prove their own correctness; preprint (available at\nECCC), 2024.","key":"261_CR2","DOI":"10.70777\/si.v1i1.10867"},{"unstructured":"Atserias A.; Distinguishing SAT from polynomial-size circuits,\nthrough black-box queries; Computational Complexity Conference\n(CCC), 2006.","key":"261_CR3"},{"unstructured":"Binnendyk E., Carmosino M., Kolokolova A., Ramyaa R..,\nSabin M.; Learning with distributional inverters; Algorithmic\nLearning Theory (ALT), 2022.","key":"261_CR4"},{"doi-asserted-by":"crossref","unstructured":"Blum A., Furst M., Kearns J., Lipton R.; Cryptographic primitives\nbased on hard learning problems; International Cryptology\nConference (CRYPTO), 1993.","key":"261_CR5","DOI":"10.1007\/3-540-48329-2_24"},{"unstructured":"Buresh-Oppenheim J., Santhanam R.; Making hard problems\nharder; Computational Complexity Conference (CCC), 2006.","key":"261_CR6"},{"unstructured":"Carmosino M., Impagliazzo R., Kabanets V., Kolokolova\nA.; Learning algorithms from natural proofs; Computational\nComplexity Conference (CCC), 2016.","key":"261_CR7"},{"unstructured":"Chen L., Hirahara S., Oliveira I.C., Pich J., Rajgopal N.,\nSanthanam R.; Beyond natural proofs: hardness magnification\nand locality; Innovations in Theoretical Computer Science\n(ITCS), 2020.","key":"261_CR8"},{"doi-asserted-by":"crossref","unstructured":"Chen L., Jin C., Williams R.; Hardness magnification for\nall sparse NP languages; Foundations of Computer Science\n(FOCS), 2019.","key":"261_CR9","DOI":"10.1109\/FOCS.2019.00077"},{"doi-asserted-by":"crossref","unstructured":"Chen L., Jin C., Williams R.; Sharp threshold results for computational\ncomplexity; Symposium on Theory of Computing\n(STOC), 2020.","key":"261_CR10","DOI":"10.1145\/3357713.3384283"},{"unstructured":"Chen L., McKay D., Murray C., Williams R.; Relations and\nequivalences between circuit lower bounds and Karp-Lipton\ntheorems; Computational Complexity Conference (CCC),\n2019.","key":"261_CR11"},{"doi-asserted-by":"crossref","unstructured":"Chen L., Tell R.; Bootstrapping results for threshold circuits\n\u201cjust beyond\u201d known lower bounds; Symposium on Theory of\nComputing (STOC), 2019.","key":"261_CR12","DOI":"10.1145\/3313276.3316333"},{"unstructured":"Cheragchi M., Hirahara S., Myrisiotis D., Yoshida Y.; Onetape\nTuring machine and read-once branching program lower\nbounds for MCSP; preprint, 2020.","key":"261_CR13"},{"unstructured":"Goldberg H., Kabanets V.; Improved learning from Kolmogorov\ncomplexity; Computational Complexity Conference\n(CCC), 2023.","key":"261_CR14"},{"unstructured":"Gutfreund D., Shaltiel R., Ta-Shma A.; If NP languages are\nhard in the worst-case then it is easy to find their hard instances;\nComputational Complexity Conference (CCC), 2005.","key":"261_CR15"},{"doi-asserted-by":"crossref","unstructured":"Hirahara S.; Non-black-box worst-case to average-case reductions\nwithin NP; Foundations of Computer Science (FOCS),\n2018.","key":"261_CR16","DOI":"10.1109\/FOCS.2018.00032"},{"unstructured":"Hirahara S.; Non-disjoint promise problems from metacomputational\nview of pseudorandom generator constructions;\nComputational Complexity Conference (CCC), 2020.","key":"261_CR17"},{"doi-asserted-by":"crossref","unstructured":"Hirahara S., Nanashima M.; Learning in Pessiland via inductive\ninference; Foundations of Computer Science (FOCS),\n2023.","key":"261_CR18","DOI":"10.1109\/FOCS57990.2023.00033"},{"unstructured":"Ilango R., Loff B., Oliveira I.C.; NP-hardness of circuit minimization\nfor multi-output functions; Computational Complexity\nConference (CCC), 2020.","key":"261_CR19"},{"unstructured":"Karchmer A.; Average-case PAC-learning from Nisan\u2019s natural\nproofs; preprint (available at ECCC), 2023.","key":"261_CR20"},{"doi-asserted-by":"crossref","unstructured":"Kraj\u00ed\u010dek J.; Bounded arithmetic, propositional logic, and complexity\ntheory; Cambridge University Press, 1995.","key":"261_CR21","DOI":"10.1017\/CBO9780511529948"},{"doi-asserted-by":"crossref","unstructured":"Kraj\u00ed\u010dek J.; Dual weak pigeonhole principle, pseudo-surjective\nfunctions and provability of circuit lower bounds; Journal of\nSymbolic Logic, 69(1):265-286, 2004.","key":"261_CR22","DOI":"10.2178\/jsl\/1080938841"},{"doi-asserted-by":"crossref","unstructured":"Kraj\u00ed\u010dek J.; On the proof complexity of the Nisan\u2013Wigderson\ngenerator based on a hard NP $$\\cap$$ coNP function; Journal of\nSymbolic Logic, 11(1):11-27, 2011.","key":"261_CR23","DOI":"10.1142\/S0219061311000979"},{"doi-asserted-by":"crossref","unstructured":"Kraj\u00ed\u010dek J.; Forcing with random variables and proof complexity;\nCambridge University Press, 2011.","key":"261_CR24","DOI":"10.1017\/CBO9781139107211"},{"doi-asserted-by":"crossref","unstructured":"Kraj\u00ed\u010dek J.; Pseudo-finite hard instances for a student-teacher\ngame with a Nisan\u2013Wigderson generator; Logical Methods in\nComputer Science, 8(3:9), 2012.","key":"261_CR25","DOI":"10.2168\/LMCS-8(3:9)2012"},{"doi-asserted-by":"crossref","unstructured":"Kraj\u00ed\u010dek J.; On the computational complexity of finding hard\ntautologies; Bulletin of the London Mathematical Society,\n46(1):111-125, 2014.","key":"261_CR26","DOI":"10.1112\/blms\/bdt071"},{"doi-asserted-by":"crossref","unstructured":"Kraj\u00ed\u010dek J.; Proof complexity; Cambridge University Press,\n2019.","key":"261_CR27","DOI":"10.1017\/9781108242066"},{"doi-asserted-by":"crossref","unstructured":"Kraj\u00ed\u010dek J., Pudl\u00e1k P., Takeuti G.; Bounded arithmetic and\nthe polynomial hierarchy; Annals of Pure and Applied Logic,\n52:143-153, 1991.","key":"261_CR28","DOI":"10.1016\/0168-0072(91)90043-L"},{"unstructured":"Kulikov A.S., Slezkin N.; SAT-based circuit local improvement;\npreprint, 2021","key":"261_CR29"},{"doi-asserted-by":"crossref","unstructured":"Li L., Littman M., Walsh T.; Knows what it knows: a framework\nfor self-aware learning; International Conference on Machine\nLearning (ICML), 2008.","key":"261_CR30","DOI":"10.1145\/1390156.1390228"},{"doi-asserted-by":"crossref","unstructured":"Linial N., Mansour Y., Nisan N.; Constant depth circuits,\nFourier transform, and learnability; Journal of the Association\nfor Computing Machinery; 40(3):607-620, 1993.","key":"261_CR31","DOI":"10.1145\/174130.174138"},{"doi-asserted-by":"crossref","unstructured":"Liu Y., Pass R.; Cryptography from sublinear-time averagecase\nhardness of time-bounded Kolmogorov complexity; Symposium\non Theory of Computing (STOC), 2021.","key":"261_CR32","DOI":"10.1145\/3406325.3451121"},{"doi-asserted-by":"crossref","unstructured":"Lipton R.J., Young N.E.; Simple strategies for large zero-sum\ngames with applications to complexity theory; Symposium on\nTheory of Computing (STOC), 1994.","key":"261_CR33","DOI":"10.1145\/195058.195447"},{"doi-asserted-by":"crossref","unstructured":"McKay D., Murray C., Williams R.; Weak lower bounds\non resource-bounded compression imply strong separations of\ncomplexity classes; Symposium on Theory of Computing\n(STOC), 2019.","key":"261_CR34","DOI":"10.1145\/3313276.3316396"},{"doi-asserted-by":"crossref","unstructured":"Modanese A.; Lower bounds and hardness magnification for\nsublinear-time shrinking cellular automata; preprint, 2020.","key":"261_CR35","DOI":"10.1007\/978-3-030-79416-3_18"},{"doi-asserted-by":"crossref","unstructured":"M\u00fcller M., Pich J.; Feasibly constructive proofs of succinct\nweak circuit lower bounds; Annals of Pure and Applied Logic,\n2019.","key":"261_CR36","DOI":"10.1016\/j.apal.2019.102735"},{"doi-asserted-by":"crossref","unstructured":"Newman I.; Private vs common random bits in communication\ncomplexity; Information Processing Letters, 39:67-71, 1991.","key":"261_CR37","DOI":"10.1016\/0020-0190(91)90157-D"},{"doi-asserted-by":"crossref","unstructured":"Nisan N., Wigderson A.; Hardness vs. randomness; J. Comp.\nSystems Sci., 49:149-167, 1994.","key":"261_CR38","DOI":"10.1016\/S0022-0000(05)80043-1"},{"unstructured":"Oliveira I.C.; Randomness and intractability in Kolmogorov\ncomplexity; International Colloquium on Automata, Languages\nand Programming (ICALP), 2019.","key":"261_CR39"},{"unstructured":"Oliveira I.C., Pich. J., Santhanam R.; Hardness magnification\nnear state-of-the-art lower bounds; Computational Complexity\nConference (CCC), 2019.","key":"261_CR40"},{"unstructured":"Oliveira I.C., Santhanam R.; Conspiracies between learning algorithms,\ncircuit lower bounds, and pseudorandomness; Computational\nComplexity Conference (CCC), 2017.","key":"261_CR41"},{"unstructured":"Oliveira I.C., Santhanam R.; Hardness magnification for natural\nproblems; Foundations of Computer Science (FOCS), 2018.","key":"261_CR42"},{"doi-asserted-by":"crossref","unstructured":"Pich J.; Nisan\u2013Wigderson generators in proof systems with\nforms of interpolation; Mathematical Logic Quarterly, 57(4),\n2011.","key":"261_CR43","DOI":"10.1002\/malq.201010012"},{"doi-asserted-by":"crossref","unstructured":"Pich J.; Circuit lower bounds in bounded arithmetics; Annals\nof Pure and Applied Logic, 166(1):29-45, 2015.","key":"261_CR44","DOI":"10.1016\/j.apal.2014.08.004"},{"unstructured":"Pich J.; Mathesis universalis; Literis, 2016.","key":"261_CR45"},{"doi-asserted-by":"crossref","unstructured":"Pich J., Santhanam R.; Strong co-nondeterministic lower\nbounds for NP cannot be proved feasibly; Symposium on Theory\nof Computing (STOC), 2021.","key":"261_CR46","DOI":"10.1145\/3406325.3451117"},{"unstructured":"Pich J., Santhanam R.; Towards P $$\\ne$$ NP from Extended Frege\nlower bounds; arXiv, 2023.","key":"261_CR47"},{"doi-asserted-by":"crossref","unstructured":"Razborov A.A; Unprovability of lower bounds on the circuit\nsize in certain fragments of bounded arithmetic, Izvestiya of\nthe Russian Academy of Science, 59:201-224, 1995.","key":"261_CR48","DOI":"10.1070\/IM1995v059n01ABEH000009"},{"doi-asserted-by":"crossref","unstructured":"Razborov A.A.; Pseudorandom generators hard for k-DNF\nResolution and Polynomial Calculus; Annals of Mathematics,\n181(2):415-472, 2015.","key":"261_CR49","DOI":"10.4007\/annals.2015.181.2.1"},{"doi-asserted-by":"crossref","unstructured":"Razborov A.A, Rudich S.; Natural Proofs; Journal of Computer\nand System Sciences, 55(1):24-35, 1997.","key":"261_CR50","DOI":"10.1006\/jcss.1997.1494"},{"unstructured":"Rivest R., Sloan R.; Learning complicated concepts reliably and\nusefully; Conference on Artificial Intelligence (AAAI), 1988.","key":"261_CR51"},{"doi-asserted-by":"crossref","unstructured":"Rudich S.; Super-bits, demi-bits, and NP\/qpoly-natural proofs;\nJournal of Computer and System Sciences, 55(1):24-35, 1997.","key":"261_CR52","DOI":"10.1006\/jcss.1997.1494"},{"unstructured":"Santhanam R.; Pseudorandomness and the Minimum Circuit\nSize Problem; Innovations in Theoretical Computer Science\n(ITCS), 2020.","key":"261_CR53"},{"unstructured":"Tal A.; Computing requires larger formulas than approximating;\nSymposium on Theory of Computing (STOC), 2017.","key":"261_CR54"},{"unstructured":"Vadhan S.; Learning versus refutation; Conference on Learning\nTheory (COLT), 2017.","key":"261_CR55"},{"doi-asserted-by":"crossref","unstructured":"Vadhan S., Zheng C.J.; A uniform Min-Max theorem with applications\nin Cryptography; International Cryptology Conference\n(CRYPTO), 2013.","key":"261_CR56","DOI":"10.1007\/978-3-642-40041-4_6"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-024-00261-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-024-00261-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-024-00261-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,21]],"date-time":"2025-07-21T23:11:16Z","timestamp":1753139476000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-024-00261-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,27]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["261"],"URL":"https:\/\/doi.org\/10.1007\/s00037-024-00261-4","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2025,3,27]]},"assertion":[{"value":"9 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 March 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"6"}}