O (^* n) algorithms on a Sum-CRCW PRAM

DOI10.1007/S00607-006-0214-YzbMATH Open1111.68145OpenAlexW2144841199MaRDI QIDQ873150FDOQ873150

Stanley C. Eisenstat

Publication date: 28 March 2007

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00607-006-0214-y

Recommendations

• scientific article; zbMATH DE number 1308942
• Time lower bounds do not exist for CRCW PRAMs
• Computing OR on a randomized fixed adversary CRCW PRAM
• \(O(\log \log n)\)-time integer geometry on the CRCW PRAM
• Optimal bounds for decision problems on the CRCW PRAM
• Lower bounds for recognizing small cliques on CRCW PRAM's
• PRAM processor allocation: a hidden bottleneck in sublogarithmic algorithms
• Fast and optimal simulations between CRCW PRAMs
• Lower bounds for randomized exclusive write PRAMs

zbMATH Keywords

parallel random access machinelinear integer sortingparallel prefix sums

Mathematics Subject Classification ID

Searching and sorting (68P10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10)

Cited In (5)

• \(O(\log \log n)\)-time integer geometry on the CRCW PRAM
• Computing OR on a randomized fixed adversary CRCW PRAM
• Time lower bounds do not exist for CRCW PRAMs
• Computing with Spikes: The Advantage of Fine-Grained Timing
• An Improved Parallel Prefix Sums Algorithm

This page was built for publication: \(O (\log^* n)\) algorithms on a Sum-CRCW PRAM

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