Exact lower time bounds for computing Boolean functions on CREW PRAMs
- 30 April 1994
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 48 (2) , 231-254
- https://doi.org/10.1016/s0022-0000(05)80003-0
Abstract
No abstract availableKeywords
This publication has 12 references indexed in Scilit:
- CREW PRAMs and Decision TreesSIAM Journal on Computing, 1991
- Time Complexity of Boolean Functions on CREW PRAM sSIAM Journal on Computing, 1991
- Improved Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous WritesSIAM Journal on Computing, 1991
- Harmonic Analysis of Polynomial Threshold FunctionsSIAM Journal on Discrete Mathematics, 1990
- Limits on the power of concurrent-write parallel machinesInformation and Computation, 1988
- Properties of complexity measures for PRAMs and WRAMsTheoretical Computer Science, 1986
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous WritesSIAM Journal on Computing, 1986
- A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functionsInformation and Control, 1982
- On recognizing graph properties from adjacency matricesTheoretical Computer Science, 1976
- A class of multiple-error-correcting codes and the decoding schemeTransactions of the IRE Professional Group on Information Theory, 1954