{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:42Z","timestamp":1781078202945,"version":"3.54.1"},"reference-count":78,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF 1212372"],"award-info":[{"award-number":["CCF 1212372"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Josef Raviv Memorial Fellowship at IBM Almaden Research Center"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>\n            The class ACC consists of circuit families with constant depth over unbounded fan-in AND, OR, NOT, and MOD\n            <jats:sub>m<\/jats:sub>\n            gates, where\n            <jats:italic>m<\/jats:italic>\n            &gt; 1 is an arbitrary constant. We prove the following.\n          <\/jats:p>\n          <jats:p>---NEXP, the class of languages accepted in nondeterministic exponential time, does not have nonuniform ACC circuits of polynomial size. The size lower bound can be slightly strengthened to quasipolynomials and other less natural functions.<\/jats:p>\n          <jats:p>\n            ---E\n            <jats:sup>NP<\/jats:sup>\n            , the class of languages recognized in 2\n            <jats:sup>O(n)<\/jats:sup>\n            time with an NP oracle, doesn\u2019t have nonuniform ACC circuits of 2\n            <jats:sup>n<\/jats:sup>\n            <jats:sup>o(1)<\/jats:sup>\n            size. The lower bound gives an exponential size-depth tradeoff: for every\n            <jats:italic>d, m<\/jats:italic>\n            there is a\n            <jats:italic>\u03b4<\/jats:italic>\n            &gt; 0 such that E\n            <jats:sup>NP<\/jats:sup>\n            doesn\u2019t have depth-\n            <jats:italic>d<\/jats:italic>\n            ACC circuits of size 2\n            <jats:sup>n<\/jats:sup>\n            <jats:sup>\u03b4<\/jats:sup>\n            with MOD\n            <jats:sub>m<\/jats:sub>\n            gates.\n          <\/jats:p>\n          <jats:p>\n            Previously, it was not known whether EXP\n            <jats:sup>NP<\/jats:sup>\n            had depth-3 polynomial-size circuits made out of only MOD\n            <jats:sub>6<\/jats:sub>\n            gates. The high-level strategy is to design faster algorithms for the circuit satisfiability problem over ACC circuits, then prove that such algorithms entail these lower bounds. The algorithms combine known properties of ACC with fast rectangular matrix multiplication and dynamic programming, while the second step requires a strengthening of the author\u2019s prior work.\n          <\/jats:p>","DOI":"10.1145\/2559903","type":"journal-article","created":{"date-parts":[[2014,2,4]],"date-time":"2014-02-04T14:16:21Z","timestamp":1391523381000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":84,"title":["Nonuniform ACC Circuit Lower Bounds"],"prefix":"10.1145","volume":"61","author":[{"given":"Ryan","family":"Williams","sequence":"first","affiliation":[{"name":"Stanford University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490272"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1675"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63538"},{"key":"e_1_2_1_5_1","article-title":"The permanent requires large uniform threshold circuits. Chicago","author":"Allender Eric","year":"1999","unstructured":"Eric Allender. 1999. The permanent requires large uniform threshold circuits. Chicago J. Theoret. Comput. Sci.","journal-title":"J. Theoret. Comput. Sci."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Eric Allender and Vivek Gore. 1991. On strong separations from AC0. Fund. Computat. Theory 8.","DOI":"10.1007\/3-540-54458-5_44"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579196"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1540612"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90037-8"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1029"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.63138"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90007-5"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","unstructured":"Richard Beigel and Jun Tarui. 1994. On ACC. Computat. Complex. 350--366. 10.1007\/BF01263423","DOI":"10.1007\/BF01263423"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/184671"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683933"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/792763.793359"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.6"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_6"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/74540.74556"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00029-4"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.46"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.17"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90152-4"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211037"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0438"},{"key":"e_1_2_1_28_1","volume-title":"Hirsch","author":"Dantsin Evgeny","year":"2009","unstructured":"Evgeny Dantsin and Edward A. Hirsch. 2009. Worst-case upper bounds. In Handbook of Satisfiability, 403--424."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101822"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1036"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00093-3"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798340850"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/646798.705312"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-005-1258-7"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-010-0287-z"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12132"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202013"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1998.0476"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00024-7"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095193"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/645731.668364"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(82)90382-5"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1033"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700389652"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00019-9"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380832"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/1765751.1765781"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/2212"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80009-2"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00286494"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_2_1_55_1","first-page":"354","article-title":"Lower bounds for the monotone complexity of some Boolean functions","volume":"31","author":"Razborov Alexander A.","year":"1985","unstructured":"Alexander A. Razborov. 1985. Lower bounds for the monotone complexity of some Boolean functions. Sov. Math. Dokl. 31, 354--357.","journal-title":"Sov. Math. Dokl."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01137685"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73023"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90177-4"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.25"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.40"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322060"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210032"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.04.012"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322061"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0067-7"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263425"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220053"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1767"},{"key":"e_1_2_1_70_1","doi-asserted-by":"crossref","unstructured":"G. S. Tseitin. 1968. On the complexity of derivation in propositional calculus. In Studies in Constructive Mathematics and Mathematical Logics 115--125.","DOI":"10.1007\/978-1-4899-5327-8_25"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.5555\/22101.22108"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.5555\/2008967.2008991"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/2034575.2034591"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1137\/10080703X"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1054"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.5555\/4479.4487"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89583"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90015-4"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2559903","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2559903","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:25Z","timestamp":1750234225000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2559903"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":78,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1145\/2559903"],"URL":"https:\/\/doi.org\/10.1145\/2559903","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]},"assertion":[{"value":"2011-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-05-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}