Exact lower time bounds for computing Boolean functions on CREW PRAMs
From MaRDI portal
Publication:1329159
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)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
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
