Sorting and Selecting in Rounds
From MaRDI portal
Publication:3801081
DOI10.1137/0216066zbMath0654.68068OpenAlexW1973732321MaRDI QIDQ3801081
Publication date: 1987
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://scholarship.claremont.edu/cgi/viewcontent.cgi?article=1119&context=hmc_fac_pub
Related Items (19)
Recursive construction for 3-regular expanders ⋮ Search problems: One, two or many rounds ⋮ A time-randomness tradeoff for selection in parallel ⋮ Connection of \(p\)-ary \(t\)-weight linear codes to Ramanujan Cayley graphs with \(t+1\) eigenvalues ⋮ Constant time parallel sorting: An empirical view. ⋮ Constructions of strongly regular Cayley graphs derived from weakly regular bent functions ⋮ A complexity theory of efficient parallel algorithms ⋮ Parallel selection ⋮ Meeting the deadline: on the complexity of fault-tolerant continuous gossip ⋮ Computation of best possible low degree expanders ⋮ Doing-it-all with bounded work and communication ⋮ On partial sorting in restricted rounds ⋮ Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory ⋮ Extracting all the randomness and reducing the error in Trevisan's extractors ⋮ The acyclic orientation game on random graphs ⋮ Ramanujan graphs and expander families constructed from \(p\)-ary bent functions ⋮ Extracting randomness: A survey and new constructions ⋮ Parallel comparison merging of many-ordered lists ⋮ Parallel comparison algorithms for approximation problems
This page was built for publication: Sorting and Selecting in Rounds
