Time Complexity of Boolean Functions on CREW PRAM<scp>s</scp>

DOI10.1137/0220051MaRDI QIDQ3358235zbMATH OpenOpenAlexFDO

Authors Mirosław Kutyłowski

Publication date 1991

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0220051

zbMATH Keywords

parallel computationparallel random access machinestime bounds

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write Parallel Random-Access Machines
• scientific article; zbMATH DE number 4119627
• Exact lower time bounds for computing Boolean functions on CREW PRAMs
• A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functions
• CREW PRAM<scp>s</scp> and Decision Trees

Cited in

(13)

• On separating the EREW and CREW PRAM models
• Exact lower time bounds for computing Boolean functions on CREW PRAMs
• Separating the power of EREW and CREW PRAMs with small communication width
• Retrieval of scattered information by EREW, CREW, and CRCW PRAMs
• Sensitive functions and approximate problems
• An insight on PRAM computational bounds
• A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functions
• The critical complexity of all (monotone) boolean functions and monotone graph properties
• CREW PRAM<scp>s</scp> and Decision Trees
• scientific article; zbMATH DE number 1559570 (Why is no real title available?)
• scientific article; zbMATH DE number 4119627 (Why is no real title available?)
• Separating the power of EREW and CREW PRAMs with small communication width
• Properties of complexity measures for PRAMs and WRAMs

This page was built for publication: Time Complexity of Boolean Functions on CREW PRAM<scp>s</scp>

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