An insight on PRAM computational bounds

DOI10.1016/S0020-0190(97)00130-0MaRDI QIDQ287202zbMATH OpenOpenAlexFDO

Authors Fabrizio Luccio, L. Pagli

Publication date 26 May 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(97)00130-0

zbMATH Keywords

parallel algorithmsCREW PRAMlower bound theory

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10)

Recommendations

• Time Complexity of Boolean Functions on CREW PRAM<scp>s</scp>
• Improved Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• New lower bounds for parallel computation
• Optimal bounds for decision problems on the CRCW PRAM
• Limits on the power of parallel random access machines with weak forms of write conflict resolution

Cites work

• scientific article; zbMATH DE number 4068238 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• Exact lower time bounds for computing Boolean functions on CREW PRAMs
• Improved Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• On Parallel Searching
• Time Complexity of Boolean Functions on CREW PRAM<scp>s</scp>
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Cited in

(4)

• A theorem on the relation between \(\text{BSR}_k\) and \(\text{BSR}^+\)
• Time lower bounds do not exist for CRCW PRAMs
• ANALYSIS OF PRAM INSTRUCTION SETS FROM A LOG COST PERSPECTIVE
• scientific article; zbMATH DE number 176503 (Why is no real title available?)

This page was built for publication: An insight on PRAM computational bounds

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