{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T16:30:03Z","timestamp":1648830603549},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1-6","license":[{"start":{"date-parts":[[1991,6,1]],"date-time":"1991-06-01T00:00:00Z","timestamp":675734400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1991,6]]},"DOI":"10.1007\/bf01759055","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T10:43:56Z","timestamp":1118918636000},"page":"479-489","source":"Crossref","is-referenced-by-count":0,"title":["Large parallel machines can be extremely slow for small problems"],"prefix":"10.1007","volume":"6","author":[{"given":"Vince","family":"Grolmusz","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF01759055_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Ben-Or, M.: A Theorem on Probabilistic Constant Depth Computation,Proc. 16th Annual ACM Symposium on Theory of Computing, 1984, pp. 471\u2013474.","DOI":"10.1145\/800057.808715"},{"key":"BF01759055_CR2","unstructured":"Beame, P.: Lower Bounds in Parallel Machine Computation, Ph.D. Thesis, University of Toronto, 1986."},{"key":"BF01759055_CR3","doi-asserted-by":"crossref","unstructured":"Beame, P., Hastad, J.: Optimal Bounds for Decision Problems on the CRC W PRAM,Proc. 19th Annual ACM Symposium on Theory of Computing, 1987, pp. 83\u201393.","DOI":"10.1145\/28395.28405"},{"key":"BF01759055_CR4","unstructured":"Chlebus, B. S., Diks, K., Hagerup, T., Radzik T.: Efficient Simulations Between Concurrent-Write PRAM Models,Proc. 13th Symposium on the Mathematical Foundations of Computer Science, 1988, pp. 230\u2013239."},{"issue":"no. 1","key":"BF01759055_CR5","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1137\/0215006","volume":"15","author":"S. A. Cook","year":"1986","unstructured":"Cook, S. A., Dwork, C., Reischuk, R.: Upper and Lower Bounds for Parallel Random Access Machines Without Simultaneous Writes,SIAM Journal on Computing, vol. 15, no. 1, 1986, pp. 87\u201397.","journal-title":"SIAM Journal on Computing"},{"key":"BF01759055_CR6","doi-asserted-by":"crossref","unstructured":"Fich, F. E., Meyer auf der Heide, F., Wigderson, A.: One, Two, Three,..., Infinity: Lower Bounds for Parallel Computation,Proc. 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 48\u201358.","DOI":"10.1145\/22145.22151"},{"issue":"no. 1","key":"BF01759055_CR7","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/BF01762109","volume":"3","author":"F. E. Fich","year":"1988","unstructured":"Fich, F. E., Ragde, P., Wigderson, A.: Simultaneous Among Concurrent-Write PRAMs,Algorithmica, vol. 3, no. 1, 1988, pp. 43\u201352.","journal-title":"Algorithmica"},{"key":"BF01759055_CR8","doi-asserted-by":"crossref","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,Mathematical Systems Theory, vol. 17, 1984, pp. 13\u201327.","journal-title":"Mathematical Systems Theory"},{"issue":"no. 4","key":"BF01759055_CR9","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1145\/322344.322353","volume":"29","author":"L. Goldschlager","year":"1982","unstructured":"Goldschlager, L.: A Unified Approach to Models of Synchronous Parallel Machines,Journal of the Association for Computing Machinery, vol. 29, no. 4, 1982, pp. 1073\u20131086.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF01759055_CR10","unstructured":"Grolmusz, V.: On the Complexity of Parallel Algorithms, Ph.D Thesis, E\u00f6tv\u00f6s University, Hungarian Academy of Sciences, 1988 (in Hungarian)."},{"key":"BF01759055_CR11","doi-asserted-by":"crossref","unstructured":"Grolmusz, V., Ragde, P.: Incomparability in Parallel Computation,Proc. 27th Annual IEEE Symposium on Foundations of Computer Science, 1987, pp. 89\u201398.","DOI":"10.1109\/SFCS.1987.34"},{"key":"BF01759055_CR12","doi-asserted-by":"crossref","unstructured":"Hastad, J.: Almost Optimal Lower Bounds for Small Depth Circuits,Proc. 18th Annual ACM Symposium on Theory of Computing, 1986, pp. 6\u201320.","DOI":"10.1145\/12130.12132"},{"issue":"no. 2","key":"BF01759055_CR13","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0020-0190(82)90093-X","volume":"14","author":"L. Ku\u010dera","year":"1982","unstructured":"Ku\u010dera, L.: Parallel Computation and Conflicts in Memory Access,Information Processing Letters, vol. 14, no. 2, 1982, pp. 93\u201396.","journal-title":"Information Processing Letters"},{"key":"BF01759055_CR14","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1137\/0216008","volume":"16","author":"F. Meyer auf der Heide","year":"1987","unstructured":"Meyer auf der Heide, F., Wigderson, A.: The Complexity of Parallel Sorting,SIAM Journal of Computing, vol. 16, 1987, pp. 100\u2013108.","journal-title":"SIAM Journal of Computing"},{"issue":"no. 3","key":"BF01759055_CR15","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1137\/0401040","volume":"1","author":"P. Ragde","year":"1988","unstructured":"Ragde, P., Steiger, W., Szemer\u00e9di, E., Wigderson, A.: The Parallel Complexity of Element Distinctness in \u03c9(\u221alogn),SIAM Journal of Discrete Mathematics, vol. 1, no. 3, 1988, pp. 399\u2013410.","journal-title":"SIAM Journal of Discrete Mathematics"},{"issue":"no. 2","key":"BF01759055_CR16","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1137\/0213027","volume":"13","author":"L. Stockmeyer","year":"1984","unstructured":"Stockmeyer, L., Vishkin, U.: Simulation of Parallel Random Access Machines by Circuits,SIAM Journal on Computing, vol. 13, no. 2, 1984, pp. 409\u2013422.","journal-title":"SIAM Journal on Computing"},{"key":"BF01759055_CR17","doi-asserted-by":"crossref","unstructured":"Yao, A.: Separating the Polynomial-Time Hierarchy by Oracles.Proc. 25th Annual IEEE Symposium on Foundations of Computer Science, 1985 pp. 1\u201310.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759055.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01759055\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759055","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T19:28:13Z","timestamp":1586287693000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01759055"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":17,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1991,6]]}},"alternative-id":["BF01759055"],"URL":"https:\/\/doi.org\/10.1007\/bf01759055","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}