Exact lower time bounds for computing Boolean functions on CREW PRAMs
From MaRDI portal
Recommendations
- Time Complexity of Boolean Functions on CREW PRAM<scp>s</scp>
- Lower bounds for the complexity of restrictions of Boolean functions
- scientific article; zbMATH DE number 4119627
- scientific article; zbMATH DE number 4095386
- scientific article; zbMATH DE number 4193610
- A large lower bound on the query complexity of a simple Boolean function
- scientific article; zbMATH DE number 806753
- Lower bounds on the formula complexity of a linear Boolean function
- Complexity lower bound for Boolean functions in the class of extended operator forms
- Upper Bounds on Boolean-Width with Applications to Exact Algorithms
Cites work
- 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
- Harmonic Analysis of Polynomial Threshold Functions
- scientific article; zbMATH DE number 4012495 (Why is no real title available?)
- scientific article; zbMATH DE number 3314813 (Why is no real title available?)
- Improved Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Limits on the power of concurrent-write parallel machines
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- On Parallel Searching
- On recognizing graph properties from adjacency matrices
- One-way functions and the nonisomorphism of NP-complete sets
- Properties of complexity measures for PRAMs and WRAMs
- Query complexity, or why is it difficult to separate NP^ A coNP^ A from P^ A by random oracles A?
- 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
(22)- The queue-read queue-write asynchronous PRAM model
- Separating the power of EREW and CREW PRAMs with small communication width
- On the power of randomized multicounter machines
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- Retrieval of scattered information by EREW, CREW, and CRCW PRAMs
- Complementing two-way finite automata
- An insight on PRAM computational bounds
- Time Complexity of Boolean Functions on CREW PRAM<scp>s</scp>
- scientific article; zbMATH DE number 4045149 (Why is no real title available?)
- CREW PRAM<scp>s</scp> and Decision Trees
- The Queue-Read Queue-Write PRAM Model: Accounting for Contention in Parallel Algorithms
- Optimal bounds for decision problems on the CRCW PRAM
- scientific article; zbMATH DE number 4119627 (Why is no real title available?)
- FAST, EFFICIENT MUTUAL AND SELF SIMULATIONS FOR SHARED MEMORY AND RECONFIGURABLE MESH
- Gossiping and broadcasting versus computing functions in networks
- Retrieval of scattered information by EREW, CREW and CRCW PRAMs
- Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write Parallel Random-Access Machines
- On the power of Las Vegas II: Two-way finite automata
- On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
- Limitations of the QRQW and EREW PRAM models
- Time lower bounds do not exist for CRCW PRAMs
- On probabilistic pushdown automata
This page was built for publication: Exact lower time bounds for computing Boolean functions on CREW PRAMs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1329159)
