The complexity of parallel prefix problems on small domains

DOI10.1006/INCO.1997.2654MaRDI QIDQ1373137zbMATH OpenOpenAlexFDO

Authors Shiva Chaudhuri, Jaikumar Radhakrishnan

Publication date 2 June 1998

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/5e26dfb91733a4dd8a422bee409246cd2f3bf6d7

zbMATH Keywords

CRCW-PRAM model

Mathematics Subject Classification ID

Searching and sorting (68P10) Distributed algorithms (68W15)

Recommendations

• scientific article; zbMATH DE number 1256702
• The average case complexity of the parallel prefix problem
• scientific article; zbMATH DE number 2166160
• On the complexity of parallelizing sequential circuits using the parallel-prefix method
• The parallel complexity of integer prefix summation
• scientific article; zbMATH DE number 1003255
• Probabilistic parallel prefix computation
• Depth-size trade-offs for parallel prefix computation
• Parallel computation for the all-pairs suffix-prefix problem
• Prefix computations on symmetric multiprocessors

Cites work

• scientific article; zbMATH DE number 3852437 (Why is no real title available?)
• scientific article; zbMATH DE number 4215352 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 1256702 (Why is no real title available?)
• Improved deterministic parallel integer sorting
• On Parallel Searching
• On parallel hashing and integer sorting
• Optimal bounds for decision problems on the CRCW PRAM
• Randomized range-maxima in nearly-constant parallel time
• Recursive Star-Tree Parallel Data Structure
• Sensitive functions and approximate problems
• Simulations among concurrent-write PRAMs
• The Complexity of Parallel Sorting
• The Parallel Simplicity of Compaction and Chaining
• The log-star revolution
• Tight Bounds on Oblivious Chaining
• Unbounded fan-in circuits and associative functions

Cited in

(4)

• On the weak prefix-search problem
• Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs
• scientific article; zbMATH DE number 17559 (Why is no real title available?)
• Parallel general prefix computations with geometric, algebraic, and other applications

This page was built for publication: The complexity of parallel prefix problems on small domains

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