Exact lower time bounds for computing Boolean functions on CREW PRAMs

DOI10.1016/S0022-0000(05)80003-0zbMath0822.68049MaRDI QIDQ1329159

Martin Dietzfelbinger, Mirosław Kutyłowski, K. Ruediger Reischuk

Publication date: 29 June 1994

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

Boolean functionstime complexityparallel random access machines

Mathematics Subject Classification ID

Related Items (14)

An insight on PRAM computational bounds ⋮ Gossiping and broadcasting versus computing functions in networks ⋮ Retrieval of scattered information by EREW, CREW and CRCW PRAMs ⋮ Complementing two-way finite automata ⋮ Retrieval of scattered information by EREW, CREW, and CRCW PRAMs ⋮ FAST, EFFICIENT MUTUAL AND SELF SIMULATIONS FOR SHARED MEMORY AND RECONFIGURABLE MESH ⋮ Separating the power of EREW and CREW PRAMs with small communication width ⋮ On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata ⋮ The queue-read queue-write asynchronous PRAM model ⋮ On the power of randomized multicounter machines ⋮ On probabilistic pushdown automata ⋮ On the power of Las Vegas II: Two-way finite automata ⋮ The Queue-Read Queue-Write PRAM Model: Accounting for Contention in Parallel Algorithms ⋮ On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Properties of complexity measures for PRAMs and WRAMs
• Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Limits on the power of concurrent-write parallel machines
• On recognizing graph properties from adjacency matrices
• One-way functions and the nonisomorphism of NP-complete sets
• Improved Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functions
• Time Complexity of Boolean Functions on CREW PRAM<scp>s</scp>
• Harmonic Analysis of Polynomial Threshold Functions
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• On Parallel Searching
• CREW PRAM<scp>s</scp> and Decision Trees

This page was built for publication: Exact lower time bounds for computing Boolean functions on CREW PRAMs