{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:12Z","timestamp":1750308732556,"version":"3.41.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"5-6","license":[{"start":{"date-parts":[[2017,5,26]],"date-time":"2017-05-26T00:00:00Z","timestamp":1495756800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,5,26]],"date-time":"2017-05-26T00:00:00Z","timestamp":1495756800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["DMS-1101228"],"award-info":[{"award-number":["DMS-1101228"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCR-1213151"],"award-info":[{"award-number":["CCR-1213151"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["306202"],"award-info":[{"award-number":["306202"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Arch. Math. Logic"],"published-print":{"date-parts":[[2017,8]]},"DOI":"10.1007\/s00153-017-0560-9","type":"journal-article","created":{"date-parts":[[2017,5,26]],"date-time":"2017-05-26T04:20:57Z","timestamp":1495772457000},"page":"639-669","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Uniform proofs of ACC representations"],"prefix":"10.1007","volume":"56","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3837-334X","authenticated-orcid":false,"given":"Sam","family":"Buss","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,26]]},"reference":[{"key":"560_CR1","doi-asserted-by":"crossref","unstructured":"Allender, E.: A note on the power of threshold circuits. In: Proceedings 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 580\u2013584 (1989)","DOI":"10.1109\/SFCS.1989.63538"},{"key":"560_CR2","unstructured":"Allender, E.: The permanent requires large uniform threshold circuits. Chic. J. Theor. Comput. Sci. (article 7) (1999)"},{"issue":"5","key":"560_CR3","doi-asserted-by":"publisher","first-page":"1026","DOI":"10.1137\/S0097539792233907","volume":"23","author":"E Allender","year":"1994","unstructured":"Allender, E., Gore, V.: A uniform circuit lower bound for the permanent. SIAM J. Comput. 23(5), 1026\u20131049 (1994)","journal-title":"SIAM J. Comput."},{"key":"560_CR4","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1006\/inco.1994.1057","volume":"112","author":"E Allender","year":"1994","unstructured":"Allender, E., Hertrampf, U.: Depth reduction for circuits of unbounded fan-in. Inf. Comput. 112, 217\u2013238 (1994)","journal-title":"Inf. Comput."},{"key":"560_CR5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"key":"560_CR6","doi-asserted-by":"crossref","unstructured":"Barrington, D.A.M.: Quasipolynomial size circuit classes. In: Proc. 7th Structure in Complexity Conference, pp. 86\u201393 (1992)","DOI":"10.1109\/SCT.1992.215383"},{"key":"560_CR7","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/BF01263423","volume":"4","author":"R Beigel","year":"1994","unstructured":"Beigel, R., Tarui, J.: On ACC. Comput. Complex. 4, 350\u2013366 (1994)","journal-title":"Comput. Complex."},{"key":"560_CR8","doi-asserted-by":"crossref","unstructured":"Beigel, R., Tarui, J., Toda, S.: On probabilistic ACC circuits with an exact-threshold output gate. In: Algorithms and Computation: Third International Symposium, ISAAC\u201992, Lecture Notes in Computer Science 650, pp. 420\u2013429 (1992)","DOI":"10.1007\/3-540-56279-6_94"},{"key":"560_CR9","unstructured":"Buss, S.R.: Bounded Arithmetic. Bibliopolis, Naples, Italy (1986). Revision of 1985 Princeton University. Ph.D. thesis"},{"key":"560_CR10","doi-asserted-by":"publisher","first-page":"7517","DOI":"10.1090\/S0002-9947-2015-06233-3","volume":"367","author":"SR Buss","year":"2015","unstructured":"Buss, S.R., Ko\u0142odziejczyk, L.A., Zdanowski, K.: Collapsing modular counting in bounded arithmetic and constant depth propositional proofs. Trans. AMS 367, 7517\u20137563 (2015)","journal-title":"Trans. AMS"},{"key":"560_CR11","doi-asserted-by":"crossref","unstructured":"Chen, S., Papakonstantinou, P.A.: Depth-reduction for composites. In: Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201916), pp. 99\u2013108. IEEE Computer Society (2016)","DOI":"10.1109\/FOCS.2016.20"},{"key":"560_CR12","doi-asserted-by":"publisher","first-page":"135","DOI":"10.4086\/toc.2009.v005a007","volume":"5","author":"L Fortnow","year":"2009","unstructured":"Fortnow, L.: A simple proof of Toda\u2019s theorem. Theory Comput. 5, 135\u2013140 (2009)","journal-title":"Theory Comput."},{"key":"560_CR13","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, 13\u201327 (1984)","journal-title":"Math. Syst. Theory"},{"key":"560_CR14","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1006\/jcss.1995.1036","volume":"50","author":"F Green","year":"1995","unstructured":"Green, F., K\u00f6bler, J., Regan, K.W., Schwentick, T., Tor\u00e1n, J.: The power of the middle bit of a #P function. J. Comput. Syst. Sci. 50, 456\u2013467 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"560_CR15","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s00037-010-0287-z","volume":"19","author":"KA Hansen","year":"2010","unstructured":"Hansen, K.A., Kouck\u00fd, M.: A new characterization of $$ACC^0$$ and probabilistic $$CC^0$$. Conput. Complex. 19, 211\u2013234 (2010)","journal-title":"Conput. Complex."},{"issue":"3","key":"560_CR16","doi-asserted-by":"publisher","first-page":"959","DOI":"10.2178\/jsl\/1191333850","volume":"72","author":"E Je\u0159\u00e1bek","year":"2007","unstructured":"Je\u0159\u00e1bek, E.: Approximate counting in bounded arithmetic. J. Symb. Log. 72(3), 959\u2013993 (2007)","journal-title":"J. Symb. Log."},{"issue":"3","key":"560_CR17","doi-asserted-by":"publisher","first-page":"829","DOI":"10.2178\/jsl\/1245158087","volume":"74","author":"E Je\u0159\u00e1bek","year":"2009","unstructured":"Je\u0159\u00e1bek, E.: Approximate counting by hashing in bounded arithmetic. J. Symb. Log. 74(3), 829\u2013860 (2009)","journal-title":"J. Symb. Log."},{"issue":"2","key":"560_CR18","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1006\/inco.1993.1033","volume":"104","author":"R Kannan","year":"1993","unstructured":"Kannan, R., Venkateswaran, H., Vinay, V., Yao, A.C.: A circuit-based proof of Toda\u2019s theorem. Inf. Comput. 104(2), 271\u2013276 (1993)","journal-title":"Inf. Comput."},{"key":"560_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511529948","volume-title":"Bounded Arithmetic. Propositional Calculus and Complexity Theory","author":"J Kraj\u00ed\u010dek","year":"1995","unstructured":"Kraj\u00ed\u010dek, J.: Bounded Arithmetic. Propositional Calculus and Complexity Theory. Cambridge University Press, Heidelberg (1995)"},{"issue":"4","key":"560_CR20","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","volume":"17","author":"C Lautemann","year":"1983","unstructured":"Lautemann, C.: BPP and the polynomial hierarchy. Inf. Process. Lett. 17(4), 215\u2013217 (1983)","journal-title":"Inf. Process. Lett."},{"key":"560_CR21","first-page":"195","volume-title":"Proof complexity and feasible arithmetics","author":"A Maciel","year":"1998","unstructured":"Maciel, A., Pitassi, T.: Towards Lower Bounds for Bounded-Depth Frege Proofs with Modular Connectives. In: Beame, P.W., Buss, S.R. (eds.) Proof complexity and feasible arithmetics, pp. 195\u2013227. American Mathematical Society, Providence (1998)"},{"key":"560_CR22","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Zachos, S.K.: Two remarks on the power of counting. In: Proc. 6th Gesellschaft f\u00fcr Informatik Conference on Theoretical Computer Science, Lecture Notes in Computer Science 145, pp. 269\u2013276. Springer, Berlin (1983)","DOI":"10.1007\/BFb0036487"},{"key":"560_CR23","unstructured":"Paris, J.B., Wilkie, A.J.: $$\\varDelta _{0}$$ sets and induction. In: W.\u00a0Guzicki, W.\u00a0Marek, A.\u00a0Pelc, C.\u00a0Rauszer (eds.) Open Days in Model Theory and Set Theory, pp. 237\u2013248. Warsaw University, Warsaw (1981)"},{"key":"560_CR24","unstructured":"Razborov, A.A.: Lower bounds on the size of bounded depth networks over a complete basis with logical addition. Matematicheskie Zametki 41, 598\u2013607 (1987). English translation in Mathematical Notes of the Academy of Sciences of the USSR 41, 333-338 (1987)"},{"key":"560_CR25","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"WL Ruzzo","year":"1981","unstructured":"Ruzzo, W.L.: On uniform circuit complexity. J. Comput. Syst. Sci. 22, 365\u2013383 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"560_CR26","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/0022-0000(89)90020-2","volume":"39","author":"U Sch\u00f6ning","year":"1989","unstructured":"Sch\u00f6ning, U.: Probabilistic complexity classes and lowness. J. Comput. Syst. Sci. 39, 84\u2013100 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"560_CR27","doi-asserted-by":"crossref","unstructured":"Sipser, M.: A complexity theoretic approach to randomness. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pp. 330\u2013335. ACM Press (1983)","DOI":"10.1145\/800061.808762"},{"key":"560_CR28","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In: Proceedings of the Nineteenth Annual ACM Symposium on the Theory of Computing, pp. 77\u201382. ACM Press (1987)","DOI":"10.1145\/28395.28404"},{"issue":"5","key":"560_CR29","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1007\/s00224-004-1210-2","volume":"39","author":"H Straubing","year":"2006","unstructured":"Straubing, H., Th\u00e9rien, D.: A note on $$MOD_p$$-$$MOD_m$$ circuits. Theory Comp. Syst. 39(5), 699\u2013706 (2006)","journal-title":"Theory Comp. Syst."},{"key":"560_CR30","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0304-3975(93)90214-E","volume":"113","author":"J Tarui","year":"1993","unstructured":"Tarui, J.: Probabilistic polynomials, AC$${}^0$$ functions and the polynomial-time hierarchy. Theor. Comput. Sci. 113, 167\u2013183 (1993)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"560_CR31","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865\u2013877 (1991)","journal-title":"SIAM J. Comput."},{"key":"560_CR32","doi-asserted-by":"crossref","unstructured":"Toda, S., Ogiwara, M.: Counting classes are at least as hard as the polynomial-time hierarchy. In: Proc. 6th Structure in Complexity Theory Conference, pp. 2\u201312 (1991)","DOI":"10.1137\/0221023"},{"key":"560_CR33","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"LG Valiant","year":"1986","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. Theor. Comput. Sci. 47, 85\u201393 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"560_CR34","doi-asserted-by":"crossref","unstructured":"Williams, R.: Non-uniform ACC circuit lower bounds. Shorter version appeared in 26th IEEE Conference on Computational Complexity (CCC). Journal of the ACM, 61, pp. 115\u2013125 (article 2) (2014)","DOI":"10.1109\/CCC.2011.36"},{"key":"560_CR35","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: On ACC and threshold circuits. In: Proc. 31st IEEE Symp. on Foundations of Computer Science (FOCS), pp. 619\u2013627 (1990)","DOI":"10.1109\/FSCS.1990.89583"}],"container-title":["Archive for Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00153-017-0560-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-017-0560-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-017-0560-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:20:02Z","timestamp":1750278002000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00153-017-0560-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,26]]},"references-count":35,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["560"],"URL":"https:\/\/doi.org\/10.1007\/s00153-017-0560-9","relation":{},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"type":"print","value":"0933-5846"},{"type":"electronic","value":"1432-0665"}],"subject":[],"published":{"date-parts":[[2017,5,26]]},"assertion":[{"value":"8 July 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 May 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}