{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T20:44:12Z","timestamp":1749847452646},"publisher-location":"Berlin\/Heidelberg","reference-count":13,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540123172"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0036901","type":"book-chapter","created":{"date-parts":[[2006,1,25]],"date-time":"2006-01-25T17:38:14Z","timestamp":1138210694000},"page":"109-117","source":"Crossref","is-referenced-by-count":19,"title":["Lower bounds for constant depth circuits for prefix problems"],"prefix":"10.1007","author":[{"given":"Ashok K.","family":"Chandra","sequence":"first","affiliation":[]},{"given":"Steven","family":"Fortune","sequence":"additional","affiliation":[]},{"given":"Richard","family":"Lipton","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"S. Cook and C. Dwork,\u201cBounds on the Time for Parallel RAM's to Compute Simple Functions,\u201d Proceedings of the 14th ACM Symposium on Theory of Computing, 1982, 231\u2013233.","DOI":"10.1145\/800070.802196"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"A.K. Chandra, S.J. Fortune, R. Lipton, \u201cUnbounded Fanin Circuits and Associative Functions,\u201d Proceedings of the 15th ACM Symposium on Theory of Computing, 1983.","DOI":"10.1145\/800061.808732"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"A.K. Chandra, L.J. Stockmeyer, U. Vishkin, \u201cA Complexity Theory for Unbounded Fan-in Parallelism,\u201d Proceedings 23rd Annual Symposium on the Foundations of Computer Science, 1982, pp. 1\u201313.","DOI":"10.1109\/SFCS.1982.3"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"D. Dolev, C. Dwork, N. Pippenger, A. Wigderson, \u201cSuperconcentrators, Generalizers and Generalized Connectors with Limited Depth,\u201d Proceedings of the 15th ACM Symposium on Theory of Computing, 1983.","DOI":"10.1145\/800061.808731"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"M. Furst, J. Saxe, M. Sipser, \u201cParity, Circuits, and the Polynomial-time Hierarchy,\u201d Proceedings of the 22nd Annual Symposium on the Foundations of Computer Science, 1981, pp. 260\u2013270.","DOI":"10.1109\/SFCS.1981.35"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"O. Gabber and Z. Galil, \u201cExplicit Constructions of Linear Size Concentrators,\u201d Proceedings of the 20th Annual Symposium on the Foundations of Computer Science, 1979, pp. 364\u2013370.","DOI":"10.1109\/SFCS.1979.16"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"L.M. Goldschlager, \u201cA Unified Approach to Models of Synchronous Parallel Machines,\u201d Proceedings of the Tenth ACM Symposium on Theory of Computing, 1978, pp. 89\u201394.","DOI":"10.1145\/800133.804336"},{"key":"9_CR8","volume-title":"Graph Theory","author":"F. Harary","year":"1971","unstructured":"F. Harary, Graph Theory, Addison-Wesley Publishing Co., Reading, Mass, 1971."},{"key":"9_CR9","volume-title":"Research Monograph No. 65","author":"R. McNaughton","year":"1971","unstructured":"R. McNaughton, S. Papert, Counter-Free Automata, Research Monograph No. 65, The MIT Press, Cambridge, Mass., 1971."},{"key":"9_CR10","volume-title":"Report RJ3431","author":"R. Reischuk","year":"1982","unstructured":"R. Reischuk, \u201cA Lower Time Bound for Parallel Random Access Machines without Simultaneous Writes,\u201d Report RJ3431, IBM Research Lab, San Jose, Ca, 1982."},{"key":"9_CR11","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/0196-6774(81)90010-9","volume":"2","author":"Y. Shiloach","year":"1981","unstructured":"Y. Shiloach and U. Vishkin, \u201cFinding the Maximum, Merging, and Sorting in a Parallel Computation Model,\u201d J. of Algorithms 2 (1981), pp. 88\u2013102.","journal-title":"J. of Algorithms"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"L.G. Valiant, \u201cOn Non-linear Lower Bounds in Computational Complexity,\u201d Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, 1975, pp. 45\u201353.","DOI":"10.1145\/800116.803752"},{"key":"9_CR13","volume-title":"Tech Report No 210","author":"U. Vishkin","year":"1981","unstructured":"U. Vishkin \u201cImplementation of Simultaneous Memory Access in Models that Forbid it,\u201d Tech Report No 210, Dept of Computer Science, Technion, Haifa, Israel, 1981."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0036901.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T22:21:29Z","timestamp":1607552489000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0036901"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540123172"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/bfb0036901","relation":{},"subject":[]}}