{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T19:56:14Z","timestamp":1742932574611,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642029264"},{"type":"electronic","value":"9783642029271"}],"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-02927-1_7","type":"book-chapter","created":{"date-parts":[[2009,7,4]],"date-time":"2009-07-04T04:37:10Z","timestamp":1246682230000},"page":"59-70","source":"Crossref","is-referenced-by-count":9,"title":["Bounds on the Size of Small Depth Circuits for Approximating Majority"],"prefix":"10.1007","author":[{"given":"Kazuyuki","family":"Amano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"7_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"Ajtai, M.: $\\Sigma_1^1$ -formulae on Finite Structures. Annals of Pure and Applied Logic\u00a024, 1\u201348 (1983)","journal-title":"Annals of Pure and Applied Logic"},{"key":"7_CR2","first-page":"1","volume-title":"Approximate Counting with Uniform Constant-Depth Circuits. Advances in Computational Complexity Theory","author":"M. Ajtai","year":"1993","unstructured":"Ajtai, M.: Approximate Counting with Uniform Constant-Depth Circuits. Advances in Computational Complexity Theory, pp. 1\u201320. Amer. Math. Soc., Providence (1993)"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtai","year":"1983","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: Sorting in c logn Parallel Steps. Combinatorica\u00a03, 1\u201319 (1983)","journal-title":"Combinatorica"},{"issue":"5","key":"7_CR4","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0020-0190(97)00131-2","volume":"63","author":"R. Boppana","year":"1997","unstructured":"Boppana, R.: The Average Sensitivity of Bounded-Depth Circuits. Inf. Proc. Lett.\u00a063(5), 257\u2013261 (1997)","journal-title":"Inf. Proc. Lett."},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Almost Optimal Lower Bounds for Small Depth Circuits. In: Proc. of 18th ACM Symposium on Theory of Computing (STOC 1986), pp. 6\u201320 (1986)","DOI":"10.1145\/12130.12132"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Klawe, M., Paul, W.J., Pippenger, N., Yannakakis, M.: On Monotone Formulae with Restricted Depth. In: Proc. of 16th ACM Symposium on Theory of Computing (STOC 1984), pp. 480\u2013487 (1984)","DOI":"10.1145\/800057.808717"},{"key":"7_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-540-73420-8_19","volume-title":"Automata, Languages and Programming","author":"R. O\u2019Donnell","year":"2007","unstructured":"O\u2019Donnell, R., Wimmer, K.: Approximation by DNF: Examples and Counterexamples. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 195\u2013206. Springer, Heidelberg (2007)"},{"issue":"3","key":"7_CR8","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0196-6774(84)90016-6","volume":"5","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G.: Short Monotone Formulae for the Majority Function. J. Algorithms\u00a05(3), 363\u2013366 (1984)","journal-title":"J. Algorithms"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Viola, E.: On Approximate Majority and Probabilistic Time. In: Proc. of 22nd IEEE Conference on Computational Complexity (CCC 2007), pp. 155\u2013168 (2007)","DOI":"10.1109\/CCC.2007.16"},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"Wegener, I.: The Complexity of Boolean Functions. Willey-Teubner (1987)","DOI":"10.1007\/3-540-18170-9_185"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02927-1_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T02:54:11Z","timestamp":1558407251000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02927-1_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029264","9783642029271"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02927-1_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}