Sorting and Selecting in Rounds

DOI10.1137/0216066zbMath0654.68068OpenAlexW1973732321MaRDI QIDQ3801081

Nicholas J. Pippenger

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

zbMATH Keywords

sortingparallel computationmedianexpanding graphsselecting

Mathematics Subject Classification ID

Searching and sorting (68P10)

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