{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T16:52:13Z","timestamp":1754153533211,"version":"3.41.2"},"reference-count":88,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"name":"Fog Research Institute","award":["FRI-454"],"award-info":[{"award-number":["FRI-454"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2025,8,31]]},"DOI":"10.1137\/23m1608483","type":"journal-article","created":{"date-parts":[[2025,7,23]],"date-time":"2025-07-23T07:53:38Z","timestamp":1753257218000},"page":"819-886","source":"Crossref","is-referenced-by-count":0,"title":["NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach"],"prefix":"10.1137","volume":"54","author":[{"given":"Yizhi","family":"Huang","sequence":"first","affiliation":[{"name":"Columbia University, New York, USA."}]},{"given":"Rahul","family":"Ilango","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA."}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7632-7574","authenticated-orcid":true,"given":"Hanlin","family":"Ren","sequence":"additional","affiliation":[{"name":"Oxford University, Oxford, UK."}]}],"member":"351","published-online":{"date-parts":[[2025,7,23]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.2307\/2694916"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-50062-1_6"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.53733\/148"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/050628994"},{"key":"ref7","series-title":"LIPIcs. Leibniz Int. Proc. Inform.","first-page":"7","volume-title":"FSTTCS","volume":"213","author":"Allender E.","year":"2021"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.04.004"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1137\/17M1157970"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/060664537"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1145\/3349616"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0124-0"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.11.033"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1145\/2160158.2160159"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90037-8"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20901-7_2"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46497-7_16"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446974"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398521"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/324\/05731"},{"key":"ref26","series-title":"LIPIcs. Leibniz Int. Proc. Inform.","first-page":"44","volume-title":"ICALP","volume":"198","author":"Carmosino M.","year":"2021"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78381-9_9"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055638"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.11.007"},{"key":"ref30","first-page":"624","author":"Dinur I.","year":"2014","journal-title":"STOC"},{"key":"ref31","series-title":"LIPIcs. Leibniz Int. Proc. Inform.","first-page":"65","volume-title":"ITCS","volume":"215","author":"Elrazik R. A.","year":"2022"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54365-8_6"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1137\/0222061"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.07.007"},{"key":"ref36","series-title":"Lecture Notes in Compu.r Sci. 263","first-page":"186","volume-title":"CRYPTO","author":"Fiat A.","year":"1986"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.03.009"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38348-9_1"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1137\/14095772X"},{"key":"ref41","first-page":"467","author":"Garg S.","year":"2013","journal-title":"STOC"},{"key":"ref42","series-title":"LIPIcs. Leibniz Int. Proc. Inform.","first-page":"16","volume-title":"CCC","volume":"234","author":"Goldberg H.","year":"2022"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1145\/6490.6503"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12132"},{"key":"ref48","first-page":"627","volume-title":"FOCS","author":"H\u00e5stad J.","year":"1996"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"ref50","first-page":"247","author":"Hirahara S.","year":"2018","journal-title":"FOCS"},{"key":"ref52","first-page":"968","volume-title":"FOCS","author":"Hirahara S.","year":"2022"},{"key":"ref53","series-title":"LIPIcs. Leibniz Int. Proc. Inform.","first-page":"26","volume-title":"CCC","volume":"234","author":"Hirahara S.","year":"2022"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585130"},{"key":"ref55","series-title":"LIPIcs. Leibniz Int. Proc. Inform.","first-page":"5","volume-title":"CCC","volume":"102","author":"Hirahara S.","year":"2018"},{"key":"ref56","series-title":"LIPIcs. Leibniz Int. Proc. Inform.","first-page":"7","volume-title":"CCC","volume":"79","author":"Hirahara S.","year":"2017"},{"key":"ref61","series-title":"LIPIcs. Leibniz Int. Proc. Inform.","first-page":"22","volume-title":"CCC","volume":"169","author":"Ilango R.","year":"2020"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520051"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451093"},{"volume-title":"Private communication","year":"2022","author":"Jain A.","key":"ref66"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-06944-4_23"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.37"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129782"},{"key":"ref72","series-title":"LIPIcs. Leibniz Int. Proc. Inform.","first-page":"44","volume-title":"ITCS","volume":"185","author":"Kleinberg R.","year":"2021"},{"key":"ref73","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90081-2"},{"key":"ref74","doi-asserted-by":"publisher","DOI":"10.1137\/0220059"},{"key":"ref75","doi-asserted-by":"publisher","DOI":"10.1080\/00207166808803030"},{"key":"ref76","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.47"},{"key":"ref77","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-015-9226-0"},{"key":"ref79","first-page":"115","volume":"9","author":"Levin L. A.","year":"1973","journal-title":"Problemy Peredachi Informatsii"},{"key":"ref80","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-49820-1"},{"key":"ref82","first-page":"722","author":"Liu Y.","year":"2021","journal-title":"STOC"},{"key":"ref84","series-title":"LIPIcs. Leibniz Int. Proc. Inform.","first-page":"36","volume-title":"CCC","volume":"234","author":"Liu Y.","year":"2022"},{"key":"ref85","first-page":"23","volume":"119","author":"Lupanov O. B.","year":"1958","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"ref86","series-title":"Lecture Notes in Comput. Sci.","first-page":"218","volume-title":"CRYPTO","author":"Merkle R. C.","year":"1989"},{"key":"ref87","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795284959"},{"key":"ref88","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2017.v013a004"},{"key":"ref89","doi-asserted-by":"publisher","DOI":"10.1007\/BF01137685"},{"key":"ref90","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"ref92","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.07.005"},{"key":"ref93","doi-asserted-by":"publisher","DOI":"10.1007\/11426639_27"},{"key":"ref95","series-title":"Lecture Notes in Comput. Sci. 196","first-page":"47","volume-title":"CRYPTO","author":"Shamir A.","year":"1984"},{"key":"ref96","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-69053-0_18"},{"key":"ref97","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808762"},{"key":"ref98","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"ref99","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366874"},{"key":"ref100","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.1984.10036"},{"key":"ref101","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0233-x"},{"key":"ref102","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22963-3_7"},{"key":"ref103","first-page":"1","volume-title":"FOCS","author":"Yao A. C.","year":"1985"},{"key":"ref104","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,7,23]],"date-time":"2025-07-23T07:53:44Z","timestamp":1753257224000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1608483"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,23]]},"references-count":88,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8,31]]}},"alternative-id":["10.1137\/23M1608483"],"URL":"https:\/\/doi.org\/10.1137\/23m1608483","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"type":"print","value":"0097-5397"},{"type":"electronic","value":"1095-7111"}],"subject":[],"published":{"date-parts":[[2025,7,23]]}}}