{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,13]],"date-time":"2024-12-13T05:30:11Z","timestamp":1734067811830,"version":"3.30.2"},"reference-count":26,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2003,8,1]],"date-time":"2003-08-01T00:00:00Z","timestamp":1059696000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3674,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2003,8]]},"DOI":"10.1016\/s0022-0000(03)00040-0","type":"journal-article","created":{"date-parts":[[2003,6,2]],"date-time":"2003-06-02T23:16:03Z","timestamp":1054595763000},"page":"63-91","source":"Crossref","is-referenced-by-count":3,"title":["Constant time parallel sorting: an empirical view"],"prefix":"10.1016","volume":"67","author":[{"given":"William","family":"Gasarch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evan","family":"Golub","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Clyde","family":"Kruskal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"year":"1997","series-title":"Parallel Computation: Models and Methods","author":"Akl","key":"10.1016\/S0022-0000(03)00040-0_BIB1"},{"key":"10.1016\/S0022-0000(03)00040-0_BIB2","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/BF02579382","article-title":"Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory","volume":"6","author":"Alon","year":"1986","journal-title":"Combinatorica"},{"key":"10.1016\/S0022-0000(03)00040-0_BIB3","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1137\/0401028","article-title":"Sorting, approximate sorting, and searching in rounds","volume":"1","author":"Alon","year":"1988","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0022-0000(03)00040-0_BIB4","doi-asserted-by":"crossref","unstructured":"N. Alon, Y. Azar, U. Vishkin, Tight bounds for parallel comparison sorting, in: Proceedings of the 29th IEEE Symposium on Found. of Comp. Sci. 1988, pp. 502\u2013510.","DOI":"10.1109\/SFCS.1986.57"},{"year":"1992","series-title":"The Probabilistic Method","author":"Alon","key":"10.1016\/S0022-0000(03)00040-0_BIB5"},{"key":"10.1016\/S0022-0000(03)00040-0_BIB6","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0012-365X(88)90190-2","article-title":"Sorting in rounds","volume":"72","author":"Bollob\u00e1s","year":"1988","journal-title":"Discrete Math."},{"key":"10.1016\/S0022-0000(03)00040-0_BIB7","series-title":"Graphs and Orders","first-page":"169","article-title":"Sorting and graphs","author":"Bollob\u00e1s","year":"1985"},{"key":"10.1016\/S0022-0000(03)00040-0_BIB8","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/BF02761857","article-title":"Sorting in one round","volume":"38","author":"Bollob\u00e1s","year":"1981","journal-title":"Israel J. Math."},{"key":"10.1016\/S0022-0000(03)00040-0_BIB9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(83)90095-1","article-title":"Parallel sorting","volume":"6","author":"Bollob\u00e1s","year":"1983","journal-title":"Discrete Appl. Math."},{"year":"1980","series-title":"Multiplicative Number Theory","author":"Davenport","key":"10.1016\/S0022-0000(03)00040-0_BIB10"},{"key":"10.1016\/S0022-0000(03)00040-0_BIB11","first-page":"623","article-title":"On a problem in the theory of graphs","volume":"7","author":"Erdos","year":"1962","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"10.1016\/S0022-0000(03)00040-0_BIB12","first-page":"84","article-title":"A survey of constant round parallel sorting","volume":"72","author":"Gasarch","year":"2000","journal-title":"Bull. European Assoc. Theor. Comput. Sci. (BEATCS)"},{"key":"10.1016\/S0022-0000(03)00040-0_BIB13","unstructured":"E. Golub, Empirical studies in parallel sorting, Ph.D. Thesis, University of MD, College Park, 1999, www.cs.umd.edu\/~egolub\/dissert.pdf."},{"issue":"3","key":"10.1016\/S0022-0000(03)00040-0_BIB14","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1137\/0210034","article-title":"Parallel sorting with constant time for comparisons","volume":"10","author":"Haggkvist","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(03)00040-0_BIB15","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1137\/0603047","article-title":"Sorting and merging in rounds","volume":"3","author":"Haggkvist","year":"1982","journal-title":"SIAM J. Algebraic Discrete Methods"},{"year":"1992","series-title":"Introduction to Parallel Algorithms and Architectures: Arrays, Trees, and Hypercubes","author":"Leighton","key":"10.1016\/S0022-0000(03)00040-0_BIB16"},{"key":"10.1016\/S0022-0000(03)00040-0_BIB17","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02126799","article-title":"Ramanujan graphs","volume":"8","author":"Lubotzky","year":"1988","journal-title":"Combinatorica"},{"issue":"1","key":"10.1016\/S0022-0000(03)00040-0_BIB18","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1006\/jcss.1996.0004","article-title":"Randomness is linear in space","volume":"52","author":"Nisan","year":"1996","journal-title":"J. Comput. Systems Sci."},{"key":"10.1016\/S0022-0000(03)00040-0_BIB19","unstructured":"A.W. Omer Reingold, R. Shaltiel, Extracting randomness via repeated condensing, Technical Report TR 00-059, Electronic Colloquium on Computational Complexity (ECCC), 2000, See www.eccc.unitrier.de\/eccc\/."},{"key":"10.1016\/S0022-0000(03)00040-0_BIB20","doi-asserted-by":"crossref","first-page":"1032","DOI":"10.1137\/0216066","article-title":"Sorting and selecting in rounds","volume":"16","author":"Pippenger","year":"1987","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(03)00040-0_BIB21","unstructured":"N. Pippenger, Personal communication, 2000."},{"key":"10.1016\/S0022-0000(03)00040-0_BIB22","doi-asserted-by":"crossref","unstructured":"S.P.V. Ran Raz, Omer Reingold, Extracting all the randomness and reducing the error in trevisan's extractors, in: Proceedings of the 31st ACM Symposium on Theory of Computing, 1999.","DOI":"10.1145\/301250.301292"},{"year":"1987","series-title":"Ten Lectures on the Probabilistic Method, Conference Board of the Mathematical Sciences, Regional Conference Series","author":"Spencer","key":"10.1016\/S0022-0000(03)00040-0_BIB23"},{"key":"10.1016\/S0022-0000(03)00040-0_BIB24","doi-asserted-by":"crossref","DOI":"10.1137\/0605030","article-title":"Explicit construction of concentrators from generalized n-gons","volume":"5","author":"Tanner","year":"1984","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"3","key":"10.1016\/S0022-0000(03)00040-0_BIB25","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1137\/0204030","article-title":"Parallelism in comparison problems","volume":"4","author":"Valiant","year":"1975","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(03)00040-0_BIB26","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s004930050049","article-title":"Expanders that beat the eigenvalue bound","volume":"19","author":"Wigderson","year":"1999","journal-title":"Combinatorica"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000400?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000400?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T19:46:16Z","timestamp":1734032776000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000003000400"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,8]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,8]]}},"alternative-id":["S0022000003000400"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(03)00040-0","relation":{},"ISSN":["0022-0000"],"issn-type":[{"type":"print","value":"0022-0000"}],"subject":[],"published":{"date-parts":[[2003,8]]}}}