Exact lower time bounds for computing Boolean functions on CREW PRAMs
type: Item
instance of: scholarly article
title: Exact lower time bounds for computing Boolean functions on CREW PRAMs
zbMATH Open document ID: 0822.68049
DOI: 10.1016/S0022-0000(05)80003-0
author: Martin Dietzfelbinger
author: Mirosław Kutyłowski
author: Rüdiger Reischuk
published in: Journal of Computer and System Sciences
publication date: 1994-06-29T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 598090
zbMATH Keywords: time complexity
zbMATH Keywords: Boolean functions
zbMATH Keywords: parallel random access machines
MaRDI profile type: Publication
cites work: Limits on the power of concurrent-write parallel machines
cites work: Harmonic Analysis of Polynomial Threshold Functions
cites work: Properties of complexity measures for PRAMs and WRAMs
cites work: Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
cites work: One-way functions and the nonisomorphism of NP-complete sets
cites work: Time Complexity of Boolean Functions on CREW PRAM<scp>s</scp>
cites work: Q5595902
cites work: CREW PRAM<scp>s</scp> and Decision Trees
cites work: Improved Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
cites work: On recognizing graph properties from adjacency matrices
cites work: A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functions
cites work: On Parallel Searching
cites work: Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
cites work: Q3762226
Recommended article: Time Complexity of Boolean Functions on CREW PRAM<scp>s</scp>
Recommended article: Lower bounds for the complexity of restrictions of Boolean functions
Recommended article: Q4733406
Recommended article: Q3822100
Recommended article: Q5202146
Recommended article: A large lower bound on the query complexity of a simple Boolean function
Recommended article: Q4850554
Recommended article: Lower bounds on the formula complexity of a linear Boolean function
Recommended article: Complexity lower bound for Boolean functions in the class of extended operator forms
Recommended article: Upper Bounds on Boolean-Width with Applications to Exact Algorithms
description: scientific article; zbMATH DE number 598090