{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:10:16Z","timestamp":1742591416782,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540180883"},{"type":"electronic","value":"9783540477471"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1987]]},"DOI":"10.1007\/3-540-18088-5_27","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T19:26:16Z","timestamp":1330197976000},"page":"326-335","source":"Crossref","is-referenced-by-count":0,"title":["The probabilistic and deterministic parallel complexity of symmetric functions"],"prefix":"10.1007","author":[{"given":"Ming","family":"Li","sequence":"first","affiliation":[]},{"given":"Yaacov","family":"Yesha","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"L. Adleman, Two theorems on random polynomial time, Proc. 19th IEEE Symposium on Foundations of Computer Science (1978), pp. 75\u201383.","DOI":"10.1109\/SFCS.1978.37"},{"key":"27_CR2","unstructured":"B. Awerbuch and Y. Shiloach, New connectivity and MSF algorithms for ultracomputers and PRAM, Proc. IEEE conf. on parallel proc., 1983, 175\u2013179."},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"P. Beame, Limits on the power of concurrent-write parallel machines, 18th ACM Symp. on Theory of Computing, Berkeley, 1986, pp. 169\u2013176.","DOI":"10.1145\/12130.12147"},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"S.A Cook and C. Dwork, Bounds on the time for parallel RAM's to compute simple functions, Proc. 14th ACM Symp. on Theory of Computing, 1982, pp 231\u2013233.","DOI":"10.1145\/800070.802196"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"F. Fich, F. Meyer auf der Heide, P. Ragde, and A Wigderson, One, two, three, ..., infinity: lower bounds for parallel computation, 24th ACM Symp. on Theory of Computing, 1985, pp 48\u201358.","DOI":"10.1145\/22145.22151"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"F. Fich, P. Ragde, and A. Wigderson, Relations between concurrent-write models of parallel computation, Proc. 3rd ACM Symp. on Principles of Distributed computing, 1984, pp 179\u2013184.","DOI":"10.1145\/800222.806745"},{"key":"27_CR7","doi-asserted-by":"crossref","unstructured":"Z. Galil, Optimal parallel algorithms for string matching, STOC'84, p.240.","DOI":"10.1145\/800057.808687"},{"key":"27_CR8","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1109\/TC.1983.1676201","volume":"C-32","author":"A. Gottlieb","year":"1983","unstructured":"A. Gottlieb, R. Grishman, C. Kruskal, K. McAuliffe, L. Rudolf and M. Snir, The NYU Ultracomputer \u2014 Designing a MIMD shared memory parallel machine, IEEE Trans. Comput. C-32 (1983), pp 175\u2013189.","journal-title":"IEEE Trans. Comput."},{"issue":"8","key":"27_CR9","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1145\/359138.359141","volume":"22","author":"D. Hirschberg","year":"1979","unstructured":"D. Hirschberg, A. Chandra, and D. Sarwate, Computing connected components on parallel computers, CACM 22,8, 1979, pp. 461\u2013464.","journal-title":"CACM"},{"key":"27_CR10","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/356683.356686","volume":"9","author":"D. Kuck","year":"1977","unstructured":"D. Kuck, A survey of parallel machine organization and programming, Computing Surveys, 9 (1977) pp29\u201352.","journal-title":"Computing Surveys"},{"key":"27_CR11","doi-asserted-by":"crossref","unstructured":"R.M. Karp, E. Upfal and A. Wigderson, Constructing a perfect matching is in random NC, Proc. 17th ACM STOC, 1985.","DOI":"10.1145\/22145.22148"},{"key":"27_CR12","unstructured":"M. Li and Y. Yesha, Separation and lower bounds for ROM and nondeterministic models of parallel computation, Ohio State University, CISRC-TR-86-7, (To appear in Information and Control) 1985."},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"M. Li and Y. Yesha, New lower bounds for parallel computation, 18th ACM Ann. Symp. on Theory of Computing, Berkeley, 1986, pp. 177\u2013187.","DOI":"10.1145\/12130.12148"},{"key":"27_CR14","doi-asserted-by":"crossref","unstructured":"F. Meyer auf der Heide and A. Wigderson, The complexity of parallel sorting, 17th ACM Symp. on Theory of computing, 1985, pp. 532\u2013540.","DOI":"10.1109\/SFCS.1985.58"},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"F.P. Preparata, New parallel-sorting schemes, IEEE Trans. Comp. c-27. p.669","DOI":"10.1109\/TC.1978.1675167"},{"key":"27_CR16","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, Finding the maximum, merging and sorting on parallel models of computation, J. of Algorithms 2, 1981, pp. 88\u2013102.","journal-title":"J. of Algorithms"},{"key":"27_CR17","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y. Shiloach","year":"1982","unstructured":"Y. Shiloach and U. Vishkin, An O(logn) parallel connectivity algorithm, J. of Algorithms 3, 1982, pp. 57\u201367.","journal-title":"J. of Algorithms"},{"key":"27_CR18","unstructured":"U. Vishkin, Parallel-design space distributed \u2014 implementation space (PDDI) general purpose computer, RC 9541, IBM T.J. Watson Research Center, Yorktown Heights, NY."},{"issue":"2","key":"27_CR19","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1137\/0214024","volume":"14","author":"U. Vishkin","year":"1985","unstructured":"U. Vishkin and A Wigderson, Trade-offs between depth and width in parallel computation, SIAM J. Computing, Vol. 14, No 2, May 1985, pp 303\u2013314.","journal-title":"SIAM J. Computing"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-18088-5_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:36:21Z","timestamp":1742589381000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-18088-5_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987]]},"ISBN":["9783540180883","9783540477471"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-18088-5_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1987]]}}}