Sorting and Selecting in Rounds

DOI10.1137/0216066MaRDI QIDQ3801081zbMATH OpenOpenAlexFDO

Authors Nicholas 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

expanding graphsmedianparallel computationselectingsorting

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• Sorting, Approximate Sorting, and Searching in Rounds
• Sorting in rounds
• Probabilistic Parallel Algorithms for Sorting and Selection
• Expanders that beat the eigenvalue bound: Explicit construction and applications
• The round complexity of distributed sorting, extended abstract

Cited in

(22)

• Extracting randomness: A survey and new constructions
• Recursive construction for 3-regular expanders
• Search problems: One, two or many rounds
• Constant time parallel sorting: An empirical view.
• On partial sorting in restricted rounds
• Ramanujan graphs and expander families constructed from \(p\)-ary bent functions
• Computation of best possible low degree expanders
• The round complexity of distributed sorting, extended abstract
• scientific article; zbMATH DE number 3926257 (Why is no real title available?)
• Sorting, Approximate Sorting, and Searching in Rounds
• The acyclic orientation game on random graphs
• A time-randomness tradeoff for selection in parallel
• Doing-it-all with bounded work and communication
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Extracting all the randomness and reducing the error in Trevisan's extractors
• Connection of p-ary t-weight linear codes to Ramanujan Cayley graphs with t+1 eigenvalues
• Constructions of strongly regular Cayley graphs derived from weakly regular bent functions
• Meeting the deadline: on the complexity of fault-tolerant continuous gossip
• Parallel comparison merging of many-ordered lists
• Parallel comparison algorithms for approximation problems
• A complexity theory of efficient parallel algorithms
• Parallel selection

This page was built for publication: Sorting and Selecting in Rounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3801081)