{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:57:26Z","timestamp":1787497046858,"version":"build-2736575974"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030199548","type":"print"},{"value":"9783030199555","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-19955-5_2","type":"book-chapter","created":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T19:10:01Z","timestamp":1561317001000},"page":"13-24","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["The Non-hardness of Approximating Circuit Size"],"prefix":"10.1007","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rahul","family":"Ilango","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Neekon","family":"Vafa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,5,16]]},"reference":[{"issue":"2","key":"2_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":"2_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.: $$\\varSigma ^1_1$$-formulae on finite structures. Ann. Pure Appl. Log. 24, 1\u201348 (1983)","journal-title":"Ann. Pure Appl. Log."},{"issue":"6","key":"2_CR3","doi-asserted-by":"publisher","first-page":"1467","DOI":"10.1137\/050628994","volume":"35","author":"E Allender","year":"2006","unstructured":"Allender, E., Buhrman, H., Kouck\u1ef3, M., van Melkebeek, D., Ronneburger, D.: Power from random strings. SIAM J. Comput. 35(6), 1467\u20131493 (2006)","journal-title":"SIAM J. Comput."},{"key":"2_CR4","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":"2_CR5","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."},{"issue":"1","key":"2_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 $${\\sf AC}^0$$ circuits given a truth table. SIAM J. Comput. 38(1), 63\u201384 (2008)","journal-title":"SIAM J. Comput."},{"key":"2_CR7","unstructured":"Allender, E., Hirahara, S.: New insights on the (non)-hardness of circuit minimization and related problems. In: Proceedings of 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) (2017)"},{"issue":"2","key":"2_CR8","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":"1","key":"2_CR9","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., Kouck\u1ef3, 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."},{"key":"2_CR10","first-page":"23","volume-title":"Algorithms and Theory of Computation Handbook","author":"E Allender","year":"2010","unstructured":"Allender, E., Loui, M.C., Regan, K.W.: Reducibility and completeness. In: Atallah, M.J., Blanton, M. (eds.) Algorithms and Theory of Computation Handbook, pp. 23\u201323. Chapman & Hall\/CRC, New York (2010)"},{"key":"2_CR11","unstructured":"Arora, S.: AC$$^0$$-reductions cannot prove the PCP theorem (1995, unpublished Manuscript)"},{"issue":"1","key":"2_CR12","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M Furst","year":"1984","unstructured":"Furst, M., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory 17(1), 13\u201327 (1984)","journal-title":"Math. Syst. Theory"},{"key":"2_CR13","unstructured":"Golovnev, A., Ilango, R., Impagliazzo, R., Kabanets, V., Kolokolova, A., Tal, A.: AC$$^0[p]$$ lower bounds against MCSP via the coin problem. Technical report TR19-018, Electronic Colloquium on Computational Complexity (ECCC) (2019). To appear in ICALP 2019"},{"key":"2_CR14","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":"2_CR15","doi-asserted-by":"crossref","unstructured":"Hirahara, S.: Non-black-box worst-case to average-case reductions within NP. In: 59th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 247\u2013258 (2018)","DOI":"10.1109\/FOCS.2018.00032"},{"key":"2_CR16","unstructured":"Hirahara, S., Santhanam, R.: On the average-case complexity of MCSP and its variants. In: Proceedings of 32nd Conference on Computational Complexity (CCC). LIPIcs-Leibniz International Proceedings in Informatics, vol. 79. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)"},{"key":"2_CR17","unstructured":"Hirahara, S., Watanabe, O.: Limits of minimum circuit size problem as oracle. In: Proceedings of 31st Conference on Computational Complexity (CCC). LIPIcs-Leibniz International Proceedings in Informatics, vol. 50. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)"},{"key":"2_CR18","unstructured":"Hitchcock, J., Pavan, A.: On the NP-completeness of the minimum circuit size problem. In: FSTTCS (2015)"},{"key":"2_CR19","unstructured":"Ilango, R.: AC$$^0[p]$$ lower bounds and NP-hardness for variants of MCSP. Technical report TR19-021, Electronic Colloquium on Computational Complexity (ECCC) (2019)"},{"key":"2_CR20","unstructured":"Impagliazzo, R., Kabanets, V., Volkovich, I.: The power of natural properties as oracles. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 102. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Kabanets, V., Cai, J.Y.: Circuit minimization problem. In: Proceedings of 32nd ACM Symposium on Theory of Computing (STOC), New York, NY, USA, pp. 73\u201379 (2000)","DOI":"10.1145\/335305.335314"},{"issue":"1","key":"2_CR22","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, R.R.: On the (non) NP-hardness of computing circuit complexity. Theory Comput. 13(1), 1\u201322 (2017)","journal-title":"Theory Comput."},{"key":"2_CR23","unstructured":"Oliveira, I., Pich, J., Santhanam, R.: Hardness magnification near state-of-the-art lower bounds. In: Electronic Colloquium on Computational Complexity 158 (2018)"},{"key":"2_CR24","unstructured":"Oliveira, I., Santhanam, R.: Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness. In: Proceedings of 32nd Conference on Computational Complexity (CCC), vol. 79, pp. 18:1\u201318:49. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)"},{"key":"2_CR25","unstructured":"Oliveira, I.C., Santhanam, R.: Hardness magnification for natural problems. In: Symposium on Foundations of Computer Science (FOCS), pp. 65\u201376 (2018)"},{"key":"2_CR26","doi-asserted-by":"crossref","unstructured":"Razborov, A., Rudich, S.: Natural proofs. In: Proceedings of 26th ACM Symposium on Theory of Computing (STOC), New York, NY, USA, pp. 204\u2013213 (1994)","DOI":"10.1145\/195058.195134"},{"key":"2_CR27","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":"2_CR28","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":"2_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity: A Uniform Approach","author":"H Vollmer","year":"2013","unstructured":"Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-662-03927-4"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-19955-5_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T16:32:39Z","timestamp":1710347559000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-19955-5_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030199548","9783030199555"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-19955-5_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"16 May 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Novosibirsk","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"71","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"31","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"44% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.27","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}