{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,12]],"date-time":"2022-04-12T18:53:14Z","timestamp":1649789594003},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1995,6,1]],"date-time":"1995-06-01T00:00:00Z","timestamp":801964800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1995,6]]},"DOI":"10.1007\/bf01268141","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T03:03:06Z","timestamp":1111633386000},"page":"113-131","source":"Crossref","is-referenced-by-count":2,"title":["Retrieval of scattered information by EREW, CREW, and CRCW PRAMs"],"prefix":"10.1007","volume":"5","author":[{"given":"Faith","family":"Fich","sequence":"first","affiliation":[]},{"given":"Miros\u0142aw","family":"Kowaluk","sequence":"additional","affiliation":[]},{"given":"Miros\u0142aw","family":"Kuty\u0142owski","sequence":"additional","affiliation":[]},{"given":"Krzysztof","family":"Lory\u015b","sequence":"additional","affiliation":[]},{"given":"Prabhakar","family":"Ragde","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01268141_CR1","doi-asserted-by":"crossref","unstructured":"H. Bast and T. Hagerup, Fast and Reliable Parallel Hashing. InProc. 3rd Ann. ACM Symp. Parallel Algorithms and Architectures, 1991, 50\u201361.","DOI":"10.1145\/113379.113384"},{"key":"BF01268141_CR2","unstructured":"P. Beame,Lower Bounds in Parallel Machine Computation. Ph.D. thesis, University of Toronto, 1986."},{"key":"BF01268141_CR3","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1142\/S012962649400017X","volume":"4.1&2","author":"P. Beame","year":"1994","unstructured":"P. Beame, M. Kik, andM. Kuty\u0142owski, Information Broadcasting by Exclusive Read PRAMs.Parallel Processing Letters 4.1&2 (1994), 159\u2013169.","journal-title":"Parallel Processing Letters"},{"key":"BF01268141_CR4","volume-title":"Graphs and Hypergraphs","author":"C. Berge","year":"1976","unstructured":"C. Berge,Graphs and Hypergraphs. North-Holland, Amsterdam, 1976."},{"key":"BF01268141_CR5","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole, Parallel Merge Sort.SIAM J. Comput. 17 (1988), 770\u2013785.","journal-title":"SIAM J. Comput."},{"key":"BF01268141_CR6","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1137\/0215006","volume":"15","author":"S. Cook","year":"1986","unstructured":"S. Cook, C. Dwork, andR. Reischuk, Upper and Lower Time Bounds for Parallel Random Access Machines Without Simultaneous Writes.SIAM J. Comput. 15 (1986), 87\u201397.","journal-title":"SIAM J. Comput."},{"key":"BF01268141_CR7","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/S0022-0000(05)80003-0","volume":"48","author":"M. Dietzfelbinger","year":"1994","unstructured":"M. Dietzfelbinger, M. Kuty\u0142owski, andR. Reischuk, Exact Time Bounds for Computing Boolean Functions on PRAMs Without Simultaneous Writes.J. Comput. System Sci. 48 (1994), pp. 231\u2013254.","journal-title":"J. Comput. System Sci."},{"key":"BF01268141_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1007\/3-540-56503-5_39","volume-title":"Proc. 10th Ann. Symp. Theoret. Aspects Comput. Sci.","author":"F. E. Fich","year":"1993","unstructured":"F. E. Fich, R. Impagliazzo, B. Kapron, V. King, andM. Kuty\u0142owski, Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution. InProc. 10th Ann. Symp. Theoret. Aspects Comput. Sci., Lecture Notes in Computer Science665, Springer-Verlag, Berlin, 1993, 386\u2013397."},{"key":"BF01268141_CR9","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1137\/0217037","volume":"17","author":"F. E. Fich","year":"1988","unstructured":"F. E. Fich, P. Ragde, andA. Wigderson, Relations Between Concurrent-Write Models of Parallel Computation.SIAM J. Comput. 17 (1988), 606\u2013627.","journal-title":"SIAM J. Comput."},{"key":"BF01268141_CR10","unstructured":"J. Gil and Y. Matias, Fast Hashing on a PRAM-Designing by Expectation. InProc. 2nd Ann. ACM Symp. Discrete Algorithms, 1991, 271\u2013280."},{"key":"BF01268141_CR11","doi-asserted-by":"crossref","unstructured":"J. Gil, Y. Matias, and U. Vishkin, Towards a Theory of Nearly Constant Parallel Time Algorithms. InProc. 32nd Ann. IEEE Symp. Found. Comput. Sci., 1991, 698\u2013710.","DOI":"10.1109\/SFCS.1991.185438"},{"key":"BF01268141_CR12","unstructured":"J. Gil and L. Rudolph, Counting and Packing in Parallel. InProc. 1986 Int. Conf. Parallel Processing, IEEE Comput. Soc. Press, 1986, 1000\u20131002."},{"key":"BF01268141_CR13","doi-asserted-by":"crossref","unstructured":"M. Goodrich, Using Approximation Algorithms to Design Parallel Algorithms that may Ignore Processor Allocation. InProc. 32nd Ann. IEEE Symp. Found. Comput. Sci., 1991, 711\u2013722.","DOI":"10.1109\/SFCS.1991.185439"},{"key":"BF01268141_CR14","unstructured":"T. Hagerup. Personal communication."},{"key":"BF01268141_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/3-540-55210-3_172","volume-title":"Proc. 9th Symp. Theoret. Aspects Comput. Sci.","author":"T. Hagerup","year":"1992","unstructured":"T. Hagerup, Fast and Optimal Simulations between CRCW PRAMs. InProc. 9th Symp. Theoret. Aspects Comput. Sci., Lecture Notes in Computer Science577, Springer-Verlag, Berlin, 1992, 45\u201356."},{"key":"BF01268141_CR16","series-title":"Lecture Notes in Computer Science","first-page":"259","volume-title":"Proc. 9th Symp. Theoret. Aspects Comput. Sci.","author":"T. Hagerup","year":"1992","unstructured":"T. Hagerup, The Log-Star Revolution. InProc. 9th Symp. Theoret. Aspects Comput. Sci., Lecture Notes in Computer Science578, Springer-Verlag, Berlin, 1992, 259\u2013278."},{"key":"BF01268141_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/BFb0035775","volume-title":"Proc. 16th Int. Colloq. Automata Languages and Programming","author":"T. Hagerup","year":"1989","unstructured":"T. Hagerup andM. Nowak, Parallel Retrieval of Scattered Information. InProc. 16th Int. Colloq. Automata Languages and Programming, Lecture Notes in Computer Science372, Springer-Verlag, Berlin, 1989, 439\u2013450."},{"key":"BF01268141_CR18","doi-asserted-by":"crossref","unstructured":"T. Hagerup and T. Radzik, Every ROBUST CRCW PRAM can Efficiently Simulate a PRIORITY PRAM. InProc. 2nd ACM Symp. Parallel Algorithms and Architectures, 1990, 125\u2013135.","DOI":"10.1145\/97444.97677"},{"key":"BF01268141_CR19","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1137\/0220051","volume":"20","author":"M. Kuty\u0142owski","year":"1991","unstructured":"M. Kuty\u0142owski, Time Complexity of Boolean Functions on CREW PRAMs.SIAM J. Comput. 20 (1991), 824\u2013833.","journal-title":"SIAM J. Comput."},{"key":"BF01268141_CR20","doi-asserted-by":"crossref","unstructured":"P. D. MacKenzie, Lower Bounds for Randomized Exclusive Write PRAMs InProc. 7th Ann. ACM Symp. Parallel Algorithms and Architectures, 1995, pp 254\u2013263.","DOI":"10.1145\/215399.215454"},{"key":"BF01268141_CR21","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1016\/0196-6774(91)90034-V","volume":"12","author":"Y. Matias","year":"1991","unstructured":"Y. Matias andU. Vishkin, On Parallel Hashing and Integer Sorting.J. Algorithms 12 (1991), 573\u2013606.","journal-title":"J. Algorithms"},{"key":"BF01268141_CR22","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1215\/ijm\/1255631807","volume":"6","author":"J. B. Rosser","year":"1962","unstructured":"J. B. Rosser andL. Schoenfeld, Approximate Formulas for Some Functions of Prime Numbers.Illinois J. Math. 6 (1962), 64\u201394.","journal-title":"Illinois J. Math."},{"key":"BF01268141_CR23","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1006\/jagm.1993.1019","volume":"14","author":"P. Ragde","year":"1993","unstructured":"P. Ragde, The Parallel Simplicity of Compaction and Chaining.J. Algorithms 14 (1993), 371\u2013380.","journal-title":"J. Algorithms"},{"key":"BF01268141_CR24","unstructured":"L. Rudolph and W. Steiger, Subset Selection in Parallel. InProc. 1985 Int. Conf. Parallel Processing, IEEE Comput. Soc. Press, 1985, 11\u201314."},{"key":"BF01268141_CR25","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1137\/0214051","volume":"14","author":"M. Snir","year":"1985","unstructured":"M. Snir, On Parallel Searching.SIAM J. Comput. 14 (1985), 688\u2013708.","journal-title":"SIAM J. Comput."}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01268141.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01268141\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01268141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T12:52:43Z","timestamp":1586177563000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01268141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,6]]}},"alternative-id":["BF01268141"],"URL":"https:\/\/doi.org\/10.1007\/bf01268141","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}