{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:35:55Z","timestamp":1725536155422},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642033506"},{"type":"electronic","value":"9783642033513"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03351-3_13","type":"book-chapter","created":{"date-parts":[[2009,8,3]],"date-time":"2009-08-03T08:53:58Z","timestamp":1249289638000},"page":"117-128","source":"Crossref","is-referenced-by-count":5,"title":["Depth Reduction for Circuits with a Single Layer of Modular Counting Gates"],"prefix":"10.1007","author":[{"given":"Kristoffer Arnsfelt","family":"Hansen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"13_CR1","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. Information and Computation\u00a0112(2), 217\u2013238 (1994)","journal-title":"Information and Computation"},{"issue":"3","key":"13_CR2","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/s000370050030","volume":"8","author":"D.A.M. Barrington","year":"1999","unstructured":"Barrington, D.A.M., Straubing, H.: Lower bounds for modular counting by circuits with modular gates. Computational Complexity\u00a08(3), 258\u2013272 (1999)","journal-title":"Computational Complexity"},{"issue":"2","key":"13_CR3","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0890-5401(90)90007-5","volume":"89","author":"D.A.M. Barrington","year":"1990","unstructured":"Barrington, D.A.M., Straubing, H., Th\u00e9rien, D.: Non-uniform automata over groups. Information and Computation\u00a089(2), 109\u2013132 (1990)","journal-title":"Information and Computation"},{"issue":"3","key":"13_CR4","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/BF01294257","volume":"6","author":"R. Beigel","year":"1997","unstructured":"Beigel, R., Maciel, A.: Upper and lower bounds for some depth-3 circuit classes. Computational Complexity\u00a06(3), 235\u2013255 (1997)","journal-title":"Computational Complexity"},{"key":"13_CR5","first-page":"286","volume-title":"Proceedings of the 6th Annual Conference on Structure in Complexity Theory","author":"R. Beigel","year":"1991","unstructured":"Beigel, R., Reingold, N., Spielman, D.: The perceptron strikes back. In: Proceedings of the 6th Annual Conference on Structure in Complexity Theory, pp. 286\u2013293. IEEE Computer Society Press, Los Alamitos (1991)"},{"issue":"4","key":"13_CR6","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. Computational Complexity\u00a04(4), 350\u2013366 (1994)","journal-title":"Computational Complexity"},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/3-540-56279-6_94","volume-title":"Algorithms and Computation","author":"R. Beigel","year":"1992","unstructured":"Beigel, R., Tarui, J., Toda, S.: On probabilistic ACC circuits with an exact-threshold output gate. In: Ibaraki, T., Iwama, K., Yamashita, M., Inagaki, Y., Nishizeki, T. (eds.) ISAAC 1992. LNCS, vol.\u00a0650, pp. 420\u2013429. Springer, Heidelberg (1992)"},{"issue":"2","key":"13_CR8","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1137\/0403015","volume":"3","author":"J. Bruck","year":"1990","unstructured":"Bruck, J.: Harmonic analysis of polynomial threshold functions. SIAM Journal on Discrete Mathematics\u00a03(2), 168\u2013177 (1990)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"13_CR9","first-page":"709","volume-title":"Proceedings og the 47st Annual IEEE Symposium on Foundations of Computer Science","author":"A. Chattopadhyay","year":"2006","unstructured":"Chattopadhyay, A., Goyal, N., Pudl\u00e1k, P., Th\u00e9rien, D.: Lower bounds for circuits with $\\textrm{MOD}_m$ gates. In: Proceedings og the 47st Annual IEEE Symposium on Foundations of Computer Science, pp. 709\u2013718. IEEE Computer Society, Los Alamitos (2006)"},{"key":"13_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1007\/11523468_80","volume-title":"Automata, Languages and Programming","author":"A. Chattopadhyay","year":"2005","unstructured":"Chattopadhyay, A., Hansen, K.A.: Lower bounds for circuits with few modular and symmetric gates. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 994\u20131005. Springer, Heidelberg (2005)"},{"issue":"6","key":"13_CR11","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0020-0190(94)00221-J","volume":"53","author":"M. Goldmann","year":"1995","unstructured":"Goldmann, M.: A note on the power of majority gates and modular gates. Information Processing Letters\u00a053(6), 321\u2013327 (1995)","journal-title":"Information Processing Letters"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Grolmusz, V.: A weight-size trade-off for circuits with $\\textrm{MOD}_m$ gates. In: Proceedings of the 26th annual ACM Symposium on the Theory of Computing, pp. 68\u201374 (1994)","DOI":"10.1145\/195058.195108"},{"issue":"4","key":"13_CR13","doi-asserted-by":"publisher","first-page":"1209","DOI":"10.1137\/S0097539798340850","volume":"29","author":"V. Grolmusz","year":"2000","unstructured":"Grolmusz, V., Tardos, G.: Lower bounds for $(\\textrm{MOD}_p - \\textrm{MOD}_m)$ circuits. SIAM Journal on Computing\u00a029(4), 1209\u20131222 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"13_CR14","unstructured":"Hansen, K.A.: Lower bounds for circuits with few modular gates using exponential sums. Technical Report\u00a079, Electronic Colloquium on Computational Complexity (2006)"},{"key":"13_CR15","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF01272517","volume":"1","author":"J. H\u00e5stad","year":"1991","unstructured":"H\u00e5stad, J., Goldmann, M.: On the power of small-depth threshold circuits. Computational Complexity\u00a01, 113\u2013129 (1991)","journal-title":"Computational Complexity"},{"issue":"6","key":"13_CR16","doi-asserted-by":"publisher","first-page":"855","DOI":"10.1017\/S0963548306007620","volume":"15","author":"S. Jukna","year":"2006","unstructured":"Jukna, S.: On graph complexity. Combinatorics, Probability & Computing\u00a015(6), 855\u2013876 (2006)","journal-title":"Combinatorics, Probability & Computing"},{"issue":"1-2","key":"13_CR17","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0304-3975(96)00019-9","volume":"174","author":"M. Krause","year":"1997","unstructured":"Krause, M., Pudl\u00e1k, P.: On the computational power of depth-2 circuits with threshold and modulo gates. Theoretical Computer Science\u00a0174(1-2), 137\u2013156 (1997)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"13_CR18","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF01137685","volume":"41","author":"A.A. Razborov","year":"1987","unstructured":"Razborov, A.A.: Lower bounds for the size of circuits of bounded depth with basis (\u2227, \u2295). Mathematical Notes of the Academy of Science of the USSR\u00a041(4), 333\u2013338 (1987)","journal-title":"Mathematical Notes of the Academy of Science of the USSR"},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In: Proceedings of the 19th annual ACM Symposium on Theory of Computing, pp. 77\u201382 (1987)","DOI":"10.1145\/28395.28404"},{"issue":"5","key":"13_CR20","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 $\\textrm{MOD}_p$ - $\\textrm{MOD}_m$ circuits. Theory of Computing Systems\u00a039(5), 699\u2013706 (2006)","journal-title":"Theory of Computing Systems"},{"issue":"1","key":"13_CR21","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, $\\textbf{AC}^0$ functions and the polynomial-time hierarchy. Theoretical Computer Science\u00a0113(1), 167\u2013183 (1993)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"13_CR22","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L.G. Valiant","year":"1986","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. Theoretical Computer Science\u00a047(1), 85\u201393 (1986)","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"13_CR23","doi-asserted-by":"publisher","first-page":"1387","DOI":"10.1137\/050640941","volume":"36","author":"E. Viola","year":"2007","unstructured":"Viola, E.: Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates. SIAM Journal on Computing\u00a036(5), 1387\u20131403 (2007)","journal-title":"SIAM Journal on Computing"},{"key":"13_CR24","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1109\/FSCS.1990.89583","volume-title":"Proceedings og the 31st Annual IEEE Symposium on Foundations of Computer Science","author":"A.C. Yao","year":"1990","unstructured":"Yao, A.C.: On ACC and threshold circuits. In: Proceedings og the 31st Annual IEEE Symposium on Foundations of Computer Science, pp. 619\u2013627. IEEE Computer Society Press, Los Alamitos (1990)"}],"container-title":["Lecture Notes in Computer Science","Computer Science - Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03351-3_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T16:40:31Z","timestamp":1558456831000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03351-3_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642033506","9783642033513"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03351-3_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}