{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T14:04:24Z","timestamp":1770818664306,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,9,12]],"date-time":"2020-09-12T00:00:00Z","timestamp":1599868800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,9,12]],"date-time":"2020-09-12T00:00:00Z","timestamp":1599868800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1559855"],"award-info":[{"award-number":["CCF-1559855"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1559855"],"award-info":[{"award-number":["CCF-1559855"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1909216"],"award-info":[{"award-number":["CCF-1909216"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1514164"],"award-info":[{"award-number":["CCF-1514164"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2021,4]]},"DOI":"10.1007\/s00224-020-10004-x","type":"journal-article","created":{"date-parts":[[2020,9,12]],"date-time":"2020-09-12T21:03:46Z","timestamp":1599944626000},"page":"559-578","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["The Non-hardness of Approximating Circuit Size"],"prefix":"10.1007","volume":"65","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0650-028X","authenticated-orcid":false,"given":"Eric","family":"Allender","sequence":"first","affiliation":[]},{"given":"Rahul","family":"Ilango","sequence":"additional","affiliation":[]},{"given":"Neekon","family":"Vafa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,9,12]]},"reference":[{"issue":"2","key":"10004_CR1","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1006\/jcss.1998.1583","volume":"57","author":"M Agrawal","year":"1998","unstructured":"Agrawal, M., Allender, E., Rudich, S.: Reductions in circuit complexity: an isomorphism theorem and a gap theorem. J. Comput. Syst. Sci. 57(2), 127\u2013143 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"10004_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M Ajtai","year":"1983","unstructured":"Ajtai, M.: ${{\\Sigma }^{1}_{1}}$-formulae on finite structures. Ann. Pure Appl. Logic 24, 1\u201348 (1983)","journal-title":"Ann. Pure Appl. Logic"},{"key":"10004_CR3","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.ic.2017.04.004","volume":"256","author":"E Allender","year":"2017","unstructured":"Allender, E., Das, B.: Zero knowledge and circuit minimization. Inf. Comput. 256, 2\u20138 (2017)","journal-title":"Inf. Comput."},{"issue":"4","key":"10004_CR4","doi-asserted-by":"publisher","first-page":"27:1","DOI":"10.1145\/3349616","volume":"11","author":"E Allender","year":"2019","unstructured":"Allender, E., Hirahara, S.: New insights on the (non)-hardness of circuit minimization and related problems. ACM Trans. Comput. Theory 11 (4), 27:1\u201327:27 (2019)","journal-title":"ACM Trans. Comput. Theory"},{"issue":"6","key":"10004_CR5","doi-asserted-by":"publisher","first-page":"1467","DOI":"10.1137\/050628994","volume":"35","author":"E Allender","year":"2006","unstructured":"Allender, E., Buhrman, H., Koucky\u0300, M., van Melkebeek, D., Ronneburger, D.: Power from random strings. SIAM J. Comput. 35(6), 1467\u20131493 (2006)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10004_CR6","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1137\/060664537","volume":"38","author":"E Allender","year":"2008","unstructured":"Allender, E., Hellerstein, L., McCabe, P., Pitassi, T., Saks, M.: Minimizing disjunctive normal form formulas and AC0 circuits given a truth table. SIAM J. Comput. 38(1), 63\u201384 (2008)","journal-title":"SIAM J. Comput."},{"key":"10004_CR7","doi-asserted-by":"crossref","unstructured":"Allender, E., Loui, M.C., Regan, K.W.: Reducibility and completeness. In: Algorithms and Theory of Computation Handbook, pp 23\u201323. Chapman & Hall\/CRC (2010)","DOI":"10.1201\/9781584888239-c23"},{"issue":"1","key":"10004_CR8","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.jcss.2010.06.004","volume":"77","author":"E Allender","year":"2011","unstructured":"Allender, E., Koucky\u0300, M., Ronneburger, D., Roy, S.: The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. J. Comput. Syst. Sci. 77(1), 14\u201340 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"10004_CR9","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/s00037-016-0124-0","volume":"26","author":"E Allender","year":"2017","unstructured":"Allender, E., Holden, D., Kabanets, V.: The minimum oracle circuit size problem. Comput. Complex. 26(2), 469\u2013496 (2017)","journal-title":"Comput. Complex."},{"issue":"4","key":"10004_CR10","doi-asserted-by":"publisher","first-page":"1339","DOI":"10.1137\/17M1157970","volume":"47","author":"E Allender","year":"2018","unstructured":"Allender, E., Grochow, J.A., van Melkebeek, D., Moore, C., Morgan, A.: Minimum circuit size, graph isomorphism, and related problems. SIAM J. Comput. 47(4), 1339\u20131372 (2018)","journal-title":"SIAM J. Comput."},{"key":"10004_CR11","doi-asserted-by":"crossref","unstructured":"Allender, E., Ilango, R., Vafa, N.: The non-hardness of approximating circuit size. In: Proceedings of the 14th International Computer Science Symposium in Russia (CSR), volume 11532 of Lecture Notes in Computer Science, pp 13\u201324. Springer (2019)","DOI":"10.1007\/978-3-030-19955-5_2"},{"key":"10004_CR12","unstructured":"Arora, S: AC0-reductions cannot prove the PCP theorem. Unpublished Manuscript (1995)"},{"issue":"1","key":"10004_CR13","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M Furst","year":"1984","unstructured":"Furst, M, Saxe, JB., Sipser, M: Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory 17(1), 13\u201327 (1984)","journal-title":"Math. Syst. Theory"},{"key":"10004_CR14","unstructured":"Golovnev, A, Ilango, R, Impagliazzo, R, Kabanets, V, Kolokolova, A, Tal, A: AC0[p] lower bounds against MCSP via the coin problem. In: Proceedings of the 46th International Colloquium on Automata Languages, and Programming, (ICALP), volume 132 of LIPIcs, pp 66:1\u201366:15 (2019)"},{"key":"10004_CR15","volume-title":"Computational Limitations for Small Depth Circuits","author":"J H\u00e5stad","year":"1987","unstructured":"H\u00e5stad, J: Computational Limitations for Small Depth Circuits. MIT Press, Cambridge (1987)"},{"issue":"4","key":"10004_CR16","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J: Some optimal inapproximability results. J. ACM 48 (4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"10004_CR17","first-page":"1","volume":"4","author":"P Hatami","year":"2011","unstructured":"Hatami, P., Kulkarni, R., Pankratov, D.: Variations on the sensitivity conjecture. Theory Comput. Grad. Surv. 4, 1\u201327 (2011)","journal-title":"Theory Comput. Grad. Surv."},{"key":"10004_CR18","doi-asserted-by":"crossref","unstructured":"Hirahara, S.: Non-black-box worst-case to average-case reductions within NP. In: Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (FOCS), pp 247\u2013258 (2018)","DOI":"10.1109\/FOCS.2018.00032"},{"key":"10004_CR19","unstructured":"Hirahara, S., Santhanam, R.: On the average-case complexity of MCSP and its variants. In: Proceedings of the 32nd Computational Complexity Conference (CCC), volume 79 of LIPIcs, pp 7:1\u20137:20. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)"},{"key":"10004_CR20","unstructured":"Hirahara, S, Watanabe, O: Limits of minimum circuit size problem as oracle. In: Proceedings of the 31st Computational Complexity Conference (CCC), volume 50 of LIPIcs, pp 18:1\u201318:20. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2016)"},{"key":"10004_CR21","unstructured":"Hitchcock, J, Pavan, A: On the NP-completeness of the minimum circuit size problem. In: Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS), volume 45 of LIPIcs, pp 236\u2013245. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015)"},{"key":"10004_CR22","unstructured":"Ilango, R: Approaching MCSP from above and below: hardness for a conditional variant and AC0[p]. In: Proceedings of the 11th Innovations in Theoretical Computer Science Conference, (ITCS), volume 151 of LIPIcs, pp 34:1\u201334:26. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"10004_CR23","unstructured":"Impagliazzo, R, Kabanets, V, Volkovich, I: The power of natural properties as oracles. In: Proceedings of the 33rd Computational Complexity Conference (CCC), volume 102 of LIPIcs, pp 7:1\u20137:20. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"},{"key":"10004_CR24","doi-asserted-by":"crossref","unstructured":"Kabanets, V, Cai, J-Y: Circuit minimization problem. In: Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), pp 73\u201379, New York (2000)","DOI":"10.1145\/335305.335314"},{"key":"10004_CR25","doi-asserted-by":"crossref","unstructured":"McKay, D.M., Murray, C.D., Williams, R.R.: Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. In: Proceedings of the 51st ACM Symposium on Theory of Computing (STOC), pp 1215\u20131225. ACM (2019)","DOI":"10.1145\/3313276.3316396"},{"issue":"1","key":"10004_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2017.v013a004","volume":"13","author":"CD Murray","year":"2017","unstructured":"Murray, C. D., Williams, RR: On the (non) NP-hardness of computing circuit complexity. Theory Comput. 13(1), 1\u201322 (2017)","journal-title":"Theory Comput."},{"key":"10004_CR27","unstructured":"Oliveira, I.C., Santhanam, R.: Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness. In: Proceedings of the 32nd Computational Complexity Conference (CCC), volume 79 of LIPIcs, pp 18:1\u201318:49. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2017)"},{"key":"10004_CR28","unstructured":"Oliveira, I. C., Santhanam, R.: Hardness magnification for natural problems. In: Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (FOCS), pp 65\u201376 (2018)"},{"key":"10004_CR29","unstructured":"Oliveira, I.C., Pich, J., Santhanam, R.: Hardness magnification near state-of-the-art lower bounds. In: Proceedings of the 34th Computational Complexity Conference (CCC), volume 137 of LIPIcs, pp 27:1\u201327:29. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2019)"},{"issue":"1","key":"10004_CR30","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"AA Razborov","year":"1997","unstructured":"Razborov, A. A., Rudich, S.: Natural proofs. J. Comput. Syst. Sci. 55(1), 24\u201335 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"10004_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ipl.2017.07.005","volume":"128","author":"M Rudow","year":"2017","unstructured":"Rudow, M.: Discrete logarithm and minimum circuit size. Inf. Process. Lett. 128, 1\u20134 (2017)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"10004_CR32","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1109\/MAHC.1984.10036","volume":"6","author":"B Trakhtenbrot","year":"1984","unstructured":"Trakhtenbrot, B.: A survey of Russian approaches to perebor (brute-force searches) algorithms. IEEE Ann. Hist. Comput. 6(4), 384\u2013400 (1984)","journal-title":"IEEE Ann. Hist. Comput."},{"key":"10004_CR33","unstructured":"Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer Science & Business Media (2013)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10004-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-10004-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10004-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,18]],"date-time":"2022-11-18T02:06:19Z","timestamp":1668737179000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-10004-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,12]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["10004"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-10004-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,12]]},"assertion":[{"value":"12 September 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}