{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:20:56Z","timestamp":1771485656226,"version":"3.50.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T00:00:00Z","timestamp":1267401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001823","name":"Ministry of Education, Youth and Sports","doi-asserted-by":"publisher","award":["GA\u010cR 201\/07\/P276P202\/10\/0854"],"award-info":[{"award-number":["GA\u010cR 201\/07\/P276P202\/10\/0854"]}],"id":[{"id":"10.13039\/501100001823","id-type":"DOI","asserted-by":"publisher"}]},{"name":"GAAV\u010cR","award":["IAA100190902"],"award-info":[{"award-number":["IAA100190902"]}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-05147093"],"award-info":[{"award-number":["CCF-05147093"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0514155DMS-0652582CCF-0830133CCF-0832787"],"award-info":[{"award-number":["CCF-0514155DMS-0652582CCF-0830133CCF-0832787"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>\n            We observe that many important computational problems in NC\n            <jats:sup>1<\/jats:sup>\n            share a simple self-reducibility property. We then show that, for any problem\n            <jats:italic>A<\/jats:italic>\n            having this self-reducibility property,\n            <jats:italic>A<\/jats:italic>\n            has polynomial-size TC\n            <jats:sup>0<\/jats:sup>\n            circuits if and only if it has TC\n            <jats:sup>0<\/jats:sup>\n            circuits of size\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1+\u03f5<\/jats:sup>\n            for every \u03f5&gt; 0 (counting the number of wires in a circuit as the size of the circuit). As an example of what this observation yields, consider the Boolean Formula Evaluation problem (BFE), which is complete for NC\n            <jats:sup>1<\/jats:sup>\n            and has the self-reducibility property. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth\n            <jats:italic>d<\/jats:italic>\n            TC\n            <jats:sup>0<\/jats:sup>\n            circuits of size\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              1+\u03f5\n              <jats:sub>\n                <jats:italic>d<\/jats:italic>\n              <\/jats:sub>\n            <\/jats:sup>\n            . If one were able to improve this lower bound to show that there is some constant \u03f5&gt; 0 (independent of the depth\n            <jats:italic>d<\/jats:italic>\n            ) such that every TC\n            <jats:sup>0<\/jats:sup>\n            circuit family recognizing BFE has size at least\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1+\u03f5<\/jats:sup>\n            , then it would follow that TC\n            <jats:sup>0<\/jats:sup>\n            \u2260 NC\n            <jats:sup>1<\/jats:sup>\n            . We show that proving lower bounds of the form\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1+\u03f5<\/jats:sup>\n            is not ruled out by the Natural Proof framework of Razborov and Rudich and hence there is currently no known barrier for separating classes such as ACC\n            <jats:sup>0<\/jats:sup>\n            , TC\n            <jats:sup>0<\/jats:sup>\n            and NC\n            <jats:sup>1<\/jats:sup>\n            via existing \u201cnatural\u201d approaches to proving circuit lower bounds.\n          <\/jats:p>\n          <jats:p>\n            We also show that problems with small uniform constant-depth circuits have algorithms that simultaneously have small space and time bounds. We then make use of known time-space tradeoff lower bounds to show that SAT requires uniform depth\n            <jats:italic>d<\/jats:italic>\n            TC\n            <jats:sup>0<\/jats:sup>\n            and AC\n            <jats:sup>0<\/jats:sup>\n            [6] circuits of size\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              1+\n              <jats:italic>c<\/jats:italic>\n            <\/jats:sup>\n            for some constant\n            <jats:italic>c<\/jats:italic>\n            depending on\n            <jats:italic>d<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/1706591.1706594","type":"journal-article","created":{"date-parts":[[2010,3,25]],"date-time":"2010-03-25T12:17:18Z","timestamp":1269519438000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":43,"title":["Amplifying lower bounds by means of self-reducibility"],"prefix":"10.1145","volume":"57","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[{"name":"Rutgers University, Rutgers, New Jersey, New Brunswick, NJ"}]},{"given":"Michal","family":"Kouck\u00fd","sequence":"additional","affiliation":[{"name":"Academy of Sciences of the Czech Republic, Prague, Czech Republic"}]}],"member":"320","published-online":{"date-parts":[[2010,3,29]]},"reference":[{"key":"e_1_2_1_1_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS)","author":"Agrawal M.","unstructured":"Agrawal , M. 2001. The first-order isomorphism theorem . In Proceedings of the Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS) . Lecture Notes in Computer Science , vol. 2245 . Springer-Verlag , Berlin, Germany , 70--82. Agrawal, M. 2001. The first-order isomorphism theorem. In Proceedings of the Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS). Lecture Notes in Computer Science, vol. 2245. Springer-Verlag, Berlin, Germany, 70--82."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1583"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796490"},{"key":"e_1_2_1_4_1","volume-title":"Complexity of Computations and Proofs, Quaderni di Matematica","author":"Allender E.","unstructured":"Allender , E. 2004. Arithmetic circuits and counting complexity classes . In Complexity of Computations and Proofs, Quaderni di Matematica , vol. 13 . Seconda Universit\u00e0 di Napoli, Napoli, Italy , 33--72. Allender, E. 2004. Arithmetic circuits and counting complexity classes. In Complexity of Computations and Proofs, Quaderni di Matematica, vol. 13. Seconda Universit\u00e0 di Napoli, Napoli, Italy, 33--72."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1813695.1813699"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792233907"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/060664537"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 16th Annual IEEE Conference on Computational Complexity (CCC). IEEE Computer Society Press","author":"Allender E.","unstructured":"Allender , E. , Kouck\u00fd , M. , Ronneburger , D. , Roy , S. , and Vinay , V . 2001. Time-space tradeoffs in the counting hierarchy . In Proceedings of the 16th Annual IEEE Conference on Computational Complexity (CCC). IEEE Computer Society Press , Los Alamitos, CA, 295--302. Allender, E., Kouck\u00fd, M., Ronneburger, D., Roy, S., and Vinay, V. 2001. Time-space tradeoffs in the counting hierarchy. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity (CCC). IEEE Computer Society Press, Los Alamitos, CA, 295--302."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1996300100011"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446950"},{"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.1016\/0890-5401(90)90007-5"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/636865.636867"},{"key":"e_1_2_1_15_1","volume-title":"Oxford Logic Guides","volume":"23","author":"Buss S.","year":"1993","unstructured":"Buss , S. 1993 . Algorithms for Boolean formula evaluation and for tree contraction. In Arithmetic, Proof Theory, and Computational Complexity , Oxford Logic Guides , vol. 23 . Oxford Science Publications, 96--115. Buss, S. 1993. Algorithms for Boolean formula evaluation and for tree contraction. In Arithmetic, Proof Theory, and Computational Complexity, Oxford Logic Guides, vol. 23. Oxford Science Publications, 96--115."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221046"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28409"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1588"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90015-7"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90152-4"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1485"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1587"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1671"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250855"},{"key":"e_1_2_1_27_1","volume-title":"Computational Limitations of Small Depth Circuits","author":"H\u00e5stad J.","unstructured":"H\u00e5stad , J. 1988. Computational Limitations of Small Depth Circuits . MIT Press , Cambridge, MA . H\u00e5stad, J. 1988. Computational Limitations of Small Depth Circuits. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261556"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-010-0287-z"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00025-9"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792282965"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875607"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_21"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9180-z"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/972639.972643"},{"key":"e_1_2_1_38_1","first-page":"765","article-title":"On a Boolean function","volume":"169","author":"Neciporuk E. I.","year":"1966","unstructured":"Neciporuk , E. I. 1966 . On a Boolean function . Doklady of the Academy of Sciences of the USSR 169 , 4, 765 -- 766 . (English translation in Soviet Mathematics Doklady 7:4, pages 999-1000.) Neciporuk, E. I. 1966. On a Boolean function. Doklady of the Academy of Sciences of the USSR 169, 4, 765--766. (English translation in Soviet Mathematics Doklady 7:4, pages 999-1000.)","journal-title":"Doklady of the Academy of Sciences of the USSR"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"e_1_2_1_40_1","first-page":"598","article-title":"Lower bounds on the size of bounded depth networks over a complete basis with logical addition","volume":"41","author":"Razborov A. A.","year":"1987","unstructured":"Razborov , A. A. 1987 . Lower bounds on the size of bounded depth networks over a complete basis with logical addition . Mathematicheskie Zametki 41 , 598 -- 607 . (English translation in Mathematical Notes of the Academy of Sciences of the USSR 41:333-338, 1987.) Razborov, A. A. 1987. Lower bounds on the size of bounded depth networks over a complete basis with logical addition. Mathematicheskie Zametki 41, 598--607. (English translation in Mathematical Notes of the Academy of Sciences of the USSR 41:333-338, 1987.)","journal-title":"Mathematicheskie Zametki"},{"key":"e_1_2_1_41_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the Symposium on Foundations of Computation Theory","author":"Razborov A. A.","unstructured":"Razborov , A. A. 1991. Lower bounds for deterministic and nondeterministic branching programs . In Proceedings of the Symposium on Foundations of Computation Theory . Lecture Notes in Computer Science , vol. 529 . Springer-Verlag , Berlin, Germany , 47--60. Razborov, A. A. 1991. Lower bounds for deterministic and nondeterministic branching programs. In Proceedings of the Symposium on Foundations of Computation Theory. Lecture Notes in Computer Science, vol. 529. Springer-Verlag, Berlin, Germany, 47--60."},{"key":"e_1_2_1_42_1","volume-title":"Feasible Mathematics II. Progress in Computer Science and Applied Logic","author":"Razborov A. A.","unstructured":"Razborov , A. A. 1995a. Bounded arithmetic and lower bounds . In Feasible Mathematics II. Progress in Computer Science and Applied Logic , vol. 13 . Birkh\u00e4user , 344--386. Razborov, A. A. 1995a. Bounded arithmetic and lower bounds. In Feasible Mathematics II. Progress in Computer Science and Applied Logic, vol. 13. Birkh\u00e4user, 344--386."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1070\/IM1995v059n01ABEH000009"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374480"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90038-6"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00110-7"},{"key":"e_1_2_1_48_1","volume-title":"Current Trends Theoret. Computer Science","author":"van Melkebeek D.","unstructured":"van Melkebeek , D. 2004. Time-space lower bounds for NP-complete problems . In Current Trends Theoret. Computer Science , World Scientific Press , 265--291. van Melkebeek, D. 2004. Time-space lower bounds for NP-complete problems. In Current Trends Theoret. Computer Science, World Scientific Press, 265--291."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000012"},{"key":"e_1_2_1_50_1","volume-title":"Introduction to Circuit Complexity","author":"Vollmer H.","unstructured":"Vollmer , H. 1999. Introduction to Circuit Complexity . Springer-Verlag , Berlin, Germany . Vollmer, H. 1999. Introduction to Circuit Complexity. Springer-Verlag, Berlin, Germany."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219024"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.49"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1706591.1706594","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1706591.1706594","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:20Z","timestamp":1750278380000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1706591.1706594"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["10.1145\/1706591.1706594"],"URL":"https:\/\/doi.org\/10.1145\/1706591.1706594","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3]]},"assertion":[{"value":"2008-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-03-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}