{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:42:10Z","timestamp":1787017330093,"version":"build-2736575974"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,8,23]],"date-time":"2022-08-23T00:00:00Z","timestamp":1661212800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1741615, and CCF-2127597"],"award-info":[{"award-number":["CCF-1741615, and CCF-2127597"]}]},{"name":"Google Faculty Research Award"},{"name":"IBM Fellowship"},{"name":"Royal Society University Research Fellowship","award":["URF\\R1\\191059, URF\\R1\\211106, 19-05497S"],"award-info":[{"award-number":["URF\\R1\\191059, URF\\R1\\211106, 19-05497S"]}]},{"name":"EPSRC New Horizons","award":["EP\/V048201\/1"],"award-info":[{"award-number":["EP\/V048201\/1"]}]},{"name":"Structure versus Randomness in Algorithms and Computation"},{"name":"European Research Council under the European Union\u2019s Seventh Framework Programme","award":["FP7\/2007-2014)\/ERC, and 615075"],"award-info":[{"award-number":["FP7\/2007-2014)\/ERC, and 615075"]}]},{"name":"European Union\u2019s Horizon 2020","award":["890220"],"award-info":[{"award-number":["890220"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,8,31]]},"abstract":"<jats:p>\n                    Hardness magnification reduces major complexity separations (such as\n                    <jats:monospace>EXP<\/jats:monospace>\n                    \u2288\n                    <jats:monospace>NC<\/jats:monospace>\n                    <jats:sup>1<\/jats:sup>\n                    ) to proving lower bounds for some natural problem\n                    <jats:italic>Q<\/jats:italic>\n                    against weak circuit models. Several recent works\u00a0[\n                    <jats:xref ref-type=\"bibr\">11<\/jats:xref>\n                    ,\n                    <jats:xref ref-type=\"bibr\">13<\/jats:xref>\n                    ,\n                    <jats:xref ref-type=\"bibr\">14<\/jats:xref>\n                    ,\n                    <jats:xref ref-type=\"bibr\">40<\/jats:xref>\n                    ,\n                    <jats:xref ref-type=\"bibr\">42<\/jats:xref>\n                    ,\n                    <jats:xref ref-type=\"bibr\">43<\/jats:xref>\n                    ,\n                    <jats:xref ref-type=\"bibr\">46<\/jats:xref>\n                    ] have established results of this form. In the most intriguing cases, the required lower bound is known for problems that appear to be significantly easier than\n                    <jats:italic>Q<\/jats:italic>\n                    , while\n                    <jats:italic>Q<\/jats:italic>\n                    itself is susceptible to lower bounds, but these are not yet sufficient for magnification.\n                  <\/jats:p>\n                  <jats:p>\n                    In this work, we provide more examples of this phenomenon and investigate the prospects of proving new lower bounds using this approach. In particular, we consider the following essential questions associated with the hardness magnification program:\n                    <jats:list list-type=\"simple\">\n                      <jats:list-item>\n                        <jats:label>\u2013<\/jats:label>\n                        <jats:p>\n                          <jats:italic>Does hardness magnification avoid the natural proofs barrier of Razborov and Rudich<\/jats:italic>\n                          [\n                          <jats:xref ref-type=\"bibr\">51<\/jats:xref>\n                          ]\n                          <jats:italic>?<\/jats:italic>\n                        <\/jats:p>\n                        <jats:p\/>\n                      <\/jats:list-item>\n                      <jats:list-item>\n                        <jats:label>\u2013<\/jats:label>\n                        <jats:p>\n                          <jats:italic>\n                            Can we adapt known lower-bound techniques to establish the desired lower bound for\n                            <jats:italic>Q<\/jats:italic>\n                            ?\n                          <\/jats:italic>\n                        <\/jats:p>\n                      <\/jats:list-item>\n                    <\/jats:list>\n                  <\/jats:p>\n                  <jats:p>We establish that some instantiations of hardness magnification overcome the natural proofs barrier in the following sense: slightly superlinear-size circuit lower bounds for certain versions of the minimum circuit-size problem imply the non-existence of natural proofs. As the non-existence of natural proofs implies the non-existence of efficient learning algorithms, we show that certain magnification theorems not only imply strong worst-case circuit lower bounds but also rule out the existence of efficient learning algorithms.<\/jats:p>\n                  <jats:p>\n                    Hardness magnification might sidestep natural proofs, but we identify a source of difficulty when trying to adapt existing lower-bound techniques to prove strong lower bounds via magnification. This is captured by a\n                    <jats:italic>locality barrier<\/jats:italic>\n                    : existing magnification theorems\n                    <jats:italic>unconditionally<\/jats:italic>\n                    show that the problems\n                    <jats:italic>Q<\/jats:italic>\n                    considered above admit highly efficient circuits extended with small fan-in oracle gates, while lower-bound techniques against weak circuit models quite often easily extend to circuits containing such oracles. This explains why direct adaptations of certain lower bounds are unlikely to yield strong complexity separations via hardness magnification.\n                  <\/jats:p>","DOI":"10.1145\/3538391","type":"journal-article","created":{"date-parts":[[2022,8,12]],"date-time":"2022-08-12T07:31:22Z","timestamp":1660289482000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Beyond Natural Proofs: Hardness Magnification and Locality"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6084-4729","authenticated-orcid":false,"given":"Lijie","family":"Chen","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3101-446X","authenticated-orcid":false,"given":"Shuichi","family":"Hirahara","sequence":"additional","affiliation":[{"name":"National Institute of Informatics, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4048-2385","authenticated-orcid":false,"given":"Igor Carboni","family":"Oliveira","sequence":"additional","affiliation":[{"name":"University of Warwick, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2731-1330","authenticated-orcid":false,"given":"J\u00e1n","family":"Pich","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6945-2345","authenticated-orcid":false,"given":"Ninad","family":"Rajgopal","sequence":"additional","affiliation":[{"name":"University of Warwick, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8716-6091","authenticated-orcid":false,"given":"Rahul","family":"Santhanam","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,8,23]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/060664537"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706594"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.07.036"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.35"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/070691954"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2016.10"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2018.12"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.74"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00077"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384283"},{"key":"e_1_3_3_14_2","volume-title":"Proceedings of the Computational Complexity Conference (CCC\u201919)","author":"Chen Lijie","year":"2019","unstructured":"Lijie Chen, Dylan M. McKay, Cody D. Murray, and R. Ryan Williams. 2019. Relations and equivalences between circuit lower bounds and Karp-Lipton theorems. In Proceedings of the Computational Complexity Conference (CCC\u201919)."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316333"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055425"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2018.04.006"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2021.23"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.39"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00019-3"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_3_3_23_2","first-page":"38:1\u201338:19","volume-title":"Proceedings of the Innovations in Theoretical Computer Science Conference (ITCS\u201919)","author":"G\u00f6\u00f6s Mika","year":"2019","unstructured":"Mika G\u00f6\u00f6s, Pritish Kamath, Robert Robere, and Dmitry Sokolov. 2019. Adventures in monotone complexity and TFNP. In Proceedings of the Innovations in Theoretical Computer Science Conference (ITCS\u201919). 38:1\u201338:19."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261556"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00032"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2020.20"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2017.7"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3230630"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792282965"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1780"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1245158087"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/2190632"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1972.1054893"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3470861"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1137\/0403021"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488630"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993702"},{"key":"e_1_3_3_39_2","volume-title":"Forcing with Random Variables and Proof Complexity","author":"Kraj\u00ed\u010dek Jan","year":"2011","unstructured":"Jan Kraj\u00ed\u010dek. 2011. Forcing with Random Variables and Proof Complexity. Cambridge University Press."},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0069-5"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316396"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2019.102735"},{"key":"e_1_3_3_43_2","first-page":"32:1\u201332:14","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP\u201919)","author":"Oliveira Igor Carboni","year":"2019","unstructured":"Igor Carboni Oliveira. 2019. Randomness and intractability in Kolmogorov complexity. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP\u201919). 32:1\u201332:14."},{"key":"e_1_3_3_44_2","volume-title":"Proceedings of the Computational Complexity Conference (CCC\u201919)","author":"Oliveira Igor Carboni","year":"2019","unstructured":"Igor Carboni Oliveira, J\u00e1n Pich, and Rahul Santhanam. 2019. Hardness magnification near state-of-the-art lower bounds. In Proceedings of the Computational Complexity Conference (CCC\u201919)."},{"key":"e_1_3_3_45_2","first-page":"124","volume-title":"Proceedings of the Conference on Computational Complexity (CCC\u201915)","author":"Oliveira Igor Carboni","year":"2015","unstructured":"Igor Carboni Oliveira and Rahul Santhanam. 2015. Majority is incompressible by AC \\( ^0[p] \\) circuits. In Proceedings of the Conference on Computational Complexity (CCC\u201915). 124\u2013157."},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2017.18"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00016"},{"key":"e_1_3_3_48_2","volume-title":"The Complexity of Meta-Computational Problems","author":"Rajgopal Ninad","year":"2021","unstructured":"Ninad Rajgopal. 2021. The Complexity of Meta-Computational Problems. University of Oxford, UK."},{"key":"e_1_3_3_49_2","first-page":"798","article-title":"Lower bounds on the monotone complexity of some Boolean functions","volume":"281","author":"Razborov Alexander A.","year":"1985","unstructured":"Alexander A. Razborov. 1985. Lower bounds on the monotone complexity of some Boolean functions. Doklady Akademii Nauk SSSR 281 (1985), 798\u2013801. English translation in: Soviet Mathematics Doklady 31:354\u2013357, 1985.","journal-title":"Doklady Akademii Nauk SSSR"},{"issue":"4","key":"e_1_3_3_50_2","first-page":"598","article-title":"Lower bounds on the size of constant-depth networks over a complete basis with logical addition","volume":"41","author":"Razborov Alexander A.","year":"1987","unstructured":"Alexander A. Razborov. 1987. Lower bounds on the size of constant-depth networks over a complete basis with logical addition. Mathematicheskie Zametki 41, 4 (1987), 598\u2013607.","journal-title":"Mathematicheskie Zametki"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2015.181.2.1"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.44"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.556667"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00110-7"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.65"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055472"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2017.15"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.32"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73025"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3538391","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3538391","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3538391","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T15:00:13Z","timestamp":1750172413000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3538391"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,23]]},"references-count":61,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8,31]]}},"alternative-id":["10.1145\/3538391"],"URL":"https:\/\/doi.org\/10.1145\/3538391","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,23]]},"assertion":[{"value":"2021-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}