{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:59:23Z","timestamp":1775282363662,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,7,20]],"date-time":"2020-07-20T00:00:00Z","timestamp":1595203200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,9,30]]},"abstract":"<jats:p>\n            The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function\n            <jats:italic>f<\/jats:italic>\n            can be computed by a Boolean circuit of size at most \u03b8, for a given parameter \u03b8. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a PRG is called\n            <jats:italic>local<\/jats:italic>\n            if its output bit strings, when viewed as the truth table of a Boolean function, can be computed by a Boolean circuit of small size. We get new and improved lower bounds for MCSP that almost match the best-known lower bounds against several circuit models. Specifically, we show that computing MCSP, on functions with a truth table of length\n            <jats:italic>N<\/jats:italic>\n            , requires\n          <\/jats:p>\n          <jats:p>\n            \u2022\n            <jats:italic>N<\/jats:italic>\n            <jats:sup>\n              3\u2212\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            -size de Morgan formulas, improving the recent\n            <jats:italic>N<\/jats:italic>\n            <jats:sup>\n              2\u2212\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            lower bound by Hirahara and Santhanam (CCC, 2017),\n          <\/jats:p>\n          <jats:p>\n            \u2022\n            <jats:italic>N<\/jats:italic>\n            <jats:sup>\n              2\u2212\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            -size formulas over an arbitrary basis or general branching programs (no non-trivial lower bound was known for MCSP against these models), and\n          <\/jats:p>\n          <jats:p>\n            \u2022 2\n            <jats:sup>\n              \u03a9(\n              <jats:italic>N<\/jats:italic>\n              1\/(\n              <jats:italic>d<\/jats:italic>\n              +1.01))\n            <\/jats:sup>\n            -size depth-\n            <jats:italic>d<\/jats:italic>\n            AC\n            <jats:sup>0<\/jats:sup>\n            circuits, improving the (implicit, in their work) exponential size lower bound by Allender et\u00a0al. (SICOMP, 2006).\n          <\/jats:p>\n          <jats:p>\n            The AC\n            <jats:sup>0<\/jats:sup>\n            lower bound stated above matches the best-known AC\n            <jats:sup>0<\/jats:sup>\n            lower bound (for PARITY) up to a small\n            <jats:italic>additive<\/jats:italic>\n            constant in the depth. Also, for the special case of depth-2 circuits (i.e., CNFs or DNFs), we get an optimal lower bound of 2\n            <jats:sup>\n              \u03a9(\n              <jats:italic>N<\/jats:italic>\n              )\n            <\/jats:sup>\n            for MCSP.\n          <\/jats:p>","DOI":"10.1145\/3404860","type":"journal-article","created":{"date-parts":[[2020,7,20]],"date-time":"2020-07-20T16:05:26Z","timestamp":1595261126000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Circuit Lower Bounds for MCSP from Local Pseudorandom Generators"],"prefix":"10.1145","volume":"12","author":[{"given":"Mahdi","family":"Cheraghchi","sequence":"first","affiliation":[{"name":"EECS Department, University of Michigan, Ann Arbor, MI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valentine","family":"Kabanets","sequence":"additional","affiliation":[{"name":"School of Computing Science, Simon Fraser University, Burnaby, BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhenjian","family":"Lu","sequence":"additional","affiliation":[{"name":"School of Computing Science, Simon Fraser University, Burnaby, BC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitrios","family":"Myrisiotis","sequence":"additional","affiliation":[{"name":"Department of Computing, Imperial College London, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,7,20]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"199","article-title":"Deterministic simulation of probabilistic constant depth circuits","volume":"5","author":"Ajtai Mikl\u00f3s","year":"1989","unstructured":"Mikl\u00f3s Ajtai and Avi Wigderson . 1989 . Deterministic simulation of probabilistic constant depth circuits . Adv. Comput. Res. 5 (1989), 199 -- 222 . DOI:10.1109\/SFCS.1985.19 10.1109\/SFCS.1985.19 Mikl\u00f3s Ajtai and Avi Wigderson. 1989. Deterministic simulation of probabilistic constant depth circuits. Adv. Comput. Res. 5 (1989), 199--222. DOI:10.1109\/SFCS.1985.19","journal-title":"Adv. Comput. Res."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/050628994"},{"key":"e_1_2_1_3_1","first-page":"1","article-title":"Learning algorithms from natural proofs","volume":"10","author":"Carmosino Marco L.","year":"2016","unstructured":"Marco L. Carmosino , Russell Impagliazzo , Valentine Kabanets , and Antonina Kolokolova . 2016 . Learning algorithms from natural proofs . In Proceedings of CCC. 10 : 1 -- 10 :24. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. 2016. Learning algorithms from natural proofs. In Proceedings of CCC. 10:1--10:24.","journal-title":"Proceedings of CCC."},{"key":"e_1_2_1_4_1","first-page":"1","article-title":"Pseudorandom generators from polarizing random walks","volume":"1","author":"Chattopadhyay Eshan","year":"2018","unstructured":"Eshan Chattopadhyay , Pooya Hatami , Kaave Hosseini , and Shachar Lovett . 2018 . Pseudorandom generators from polarizing random walks . In Proceedings of CCC. 1 : 1 -- 1 :21. Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett. 2018. Pseudorandom generators from polarizing random walks. In Proceedings of CCC. 1:1--1:21.","journal-title":"Proceedings of CCC."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of MFCS. 272--284","author":"Cryan Mary","year":"2001","unstructured":"Mary Cryan and Peter Bro Miltersen . 2001 . On pseudorandom generators in . In Proceedings of MFCS. 272--284 . DOI:10.1007\/3-540-44683-4_24 10.1007\/3-540-44683-4_24 Mary Cryan and Peter Bro Miltersen. 2001. On pseudorandom generators in . In Proceedings of MFCS. 272--284. DOI:10.1007\/3-540-44683-4_24"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15369-3_38"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-017-0159-x"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10958-013-1350-5"},{"key":"e_1_2_1_9_1","first-page":"1","article-title":"AC0[p] lower bounds against MCSP via the coin problem","volume":"66","author":"Golovnev Alexander","year":"2019","unstructured":"Alexander Golovnev , Rahul Ilango , Russell Impagliazzo , Valentine Kabanets , Antonina Kolokolova , and Avishay Tal . 2019 . AC0[p] lower bounds against MCSP via the coin problem . In Proceedings of ICALP. 66 : 1 -- 66 :15. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.66 10.4230\/LIPIcs.ICALP.2019.66 Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, and Avishay Tal. 2019. AC0[p] lower bounds against MCSP via the coin problem. In Proceedings of ICALP. 66:1--66:15. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.66","journal-title":"Proceedings of ICALP."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12132"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/276234.276238"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00032"},{"key":"e_1_2_1_13_1","first-page":"1","article-title":"On the average-case complexity of MCSP and its variants","volume":"7","author":"Hirahara Shuichi","year":"2017","unstructured":"Shuichi Hirahara and Rahul Santhanam . 2017 . On the average-case complexity of MCSP and its variants . In Proceedings of CCC. 7 : 1 -- 7 :20. DOI:10.4230\/LIPIcs.CCC.2017.7 10.4230\/LIPIcs.CCC.2017.7 Shuichi Hirahara and Rahul Santhanam. 2017. On the average-case complexity of MCSP and its variants. In Proceedings of CCC. 7:1--7:20. DOI:10.4230\/LIPIcs.CCC.2017.7","journal-title":"Proceedings of CCC."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230630"},{"key":"e_1_2_1_15_1","volume-title":"Boolean Function Complexity\u2014Advances and Frontiers. Algorithms and combinatorics","author":"Jukna Stasys","unstructured":"Stasys Jukna . 2012. Boolean Function Complexity\u2014Advances and Frontiers. Algorithms and combinatorics , Vol. 27 . Springer . Stasys Jukna. 2012. Boolean Function Complexity\u2014Advances and Frontiers. Algorithms and combinatorics, Vol. 27. Springer."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335314"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of APPROX\/RANDOM. 640--651","author":"Lovett Shachar","year":"2011","unstructured":"Shachar Lovett and Srikanth Srinivasan . 2011 . Correlation bounds for poly-size AC0 circuits with n1\u2212o(1) symmetric gates . In Proceedings of APPROX\/RANDOM. 640--651 . DOI:10.1007\/978-3-642-22935-0_54 10.1007\/978-3-642-22935-0_54 Shachar Lovett and Srikanth Srinivasan. 2011. Correlation bounds for poly-size AC0 circuits with n1\u2212o(1) symmetric gates. In Proceedings of APPROX\/RANDOM. 640--651. DOI:10.1007\/978-3-642-22935-0_54"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISTCS.1993.253488"},{"key":"e_1_2_1_19_1","first-page":"765","article-title":"On a Boolean function","volume":"169","author":"Nechiporuk E. I.","year":"1966","unstructured":"E. I. Nechiporuk . 1966 . On a Boolean function . Doklady Akademii Nauk SSSR 169 , 4 (1966), 765 -- 766 . E. I. Nechiporuk. 1966. On a Boolean function. Doklady Akademii Nauk SSSR 169, 4 (1966), 765--766.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0004"},{"key":"e_1_2_1_22_1","volume-title":"Electr. Colloq. Comput. Complex. 25","author":"Oliveira Igor Carboni","year":"2018","unstructured":"Igor Carboni Oliveira , J\u00e1n Pich , and Rahul Santhanam . 2018 . Hardness magnification near state-of-the-art lower bounds . Electr. Colloq. Comput. Complex. 25 (2018), 158. Igor Carboni Oliveira, J\u00e1n Pich, and Rahul Santhanam. 2018. Hardness magnification near state-of-the-art lower bounds. Electr. Colloq. Comput. Complex. 25 (2018), 158."},{"key":"e_1_2_1_23_1","first-page":"1","article-title":"Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness","volume":"18","author":"Oliveira Igor Carboni","year":"2017","unstructured":"Igor Carboni Oliveira and Rahul Santhanam . 2017 . Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness . In Proceedings of CCC. 18 : 1 -- 18 :49. Igor Carboni Oliveira and Rahul Santhanam. 2017. Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. In Proceedings of CCC. 18:1--18:49.","journal-title":"Proceedings of CCC."},{"key":"e_1_2_1_24_1","first-page":"18","volume-title":"Proceedings of FOCS. 65--76","author":"Oliveira Igor Carboni","year":"2018","unstructured":"Igor Carboni Oliveira and Rahul Santhanam . 2018 . Hardness magnification for natural problems . In Proceedings of FOCS. 65--76 . ECCC:TR 18 - 139 . Igor Carboni Oliveira and Rahul Santhanam. 2018. Hardness magnification for natural problems. In Proceedings of FOCS. 65--76. ECCC:TR18-139."},{"key":"e_1_2_1_25_1","first-page":"1","article-title":"Luby-Velickovic-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits","volume":"56","author":"Servedio Rocco A.","year":"2018","unstructured":"Rocco A. Servedio and Li-Yang Tan . 2018 . Luby-Velickovic-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits . In Proceedings of APPROX\/RANDOM. 56 : 1 -- 56 :20. Rocco A. Servedio and Li-Yang Tan. 2018. Luby-Velickovic-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits. In Proceedings of APPROX\/RANDOM. 56:1--56:20.","journal-title":"Proceedings of APPROX\/RANDOM."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1949.tb03624.x"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.65"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055472"},{"key":"e_1_2_1_29_1","first-page":"1","article-title":"Tight bounds on the fourier spectrum of","volume":"15","author":"Tal Avishay","year":"2017","unstructured":"Avishay Tal . 2017 . Tight bounds on the fourier spectrum of . In Proceedings of CCC. 15 : 1 -- 15 :31. ECCC:TR14-174. Avishay Tal. 2017. Tight bounds on the fourier spectrum of . In Proceedings of CCC. 15:1--15:31. ECCC:TR14-174.","journal-title":"Proceedings of CCC."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.1984.10036"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.32"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.25"},{"key":"e_1_2_1_34_1","volume-title":"Modern Computer Algebra","author":"von zur Gathen Joachim","unstructured":"Joachim von zur Gathen and J\u00fcrgen Gerhard . 2013. Modern Computer Algebra . Cambridge University Press . Joachim von zur Gathen and J\u00fcrgen Gerhard. 2013. Modern Computer Algebra. Cambridge University Press."},{"key":"e_1_2_1_35_1","volume-title":"The Complexity of Boolean Functions","author":"Wegener Ingo","unstructured":"Ingo Wegener . 1987. The Complexity of Boolean Functions . Wiley-Teubner . Retrieved from http:\/\/ls2-www.cs.uni-dortmund.de\/monographs\/bluebook\/. Ingo Wegener. 1987. The Complexity of Boolean Functions. Wiley-Teubner. Retrieved from http:\/\/ls2-www.cs.uni-dortmund.de\/monographs\/bluebook\/."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3404860","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3404860","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:44Z","timestamp":1750191464000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3404860"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,20]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9,30]]}},"alternative-id":["10.1145\/3404860"],"URL":"https:\/\/doi.org\/10.1145\/3404860","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,20]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}