Resource bounds for parallel computation of threshold and symmetric functions

DOI10.1016/0022-0000(91)90042-4MaRDI QIDQ751804zbMATH OpenOpenAlexFDO

Authors Ming Li, Yaacov Yesha

Publication date 1991

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

Full work available at URL https://doi.org/10.1016/0022-0000(91)90042-4

zbMATH Keywords

deterministic prioritylower boundsone shared memory cellparalle computationPRIORITY PRAMprobabilistic PRIORITYsymmetric functionsthreshold language

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 4047091
• Lower Bounds for Threshold and Symmetric Functions in Parallel Computation
• scientific article; zbMATH DE number 3988712
• New lower bounds for parallel computation
• Improved Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Cites work

• A parallel-design distributed-implementation (PDDI) general-purpose computer
• An O(logn) parallel connectivity algorithm
• Computing connected components on parallel computers
• Constructing a perfect matching is in random NC
• Finding the maximum, merging, and sorting in a parallel computation model
• scientific article; zbMATH DE number 3543634 (Why is no real title available?)
• New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
• New Parallel-Sorting Schemes
• Separation and lower bounds for ROM and nondeterministic models of parallel computation
• Trade-Offs between Depth and Width in Parallel Computation

Cited in

(8)

• Parallel computation with threshold functions
• scientific article; zbMATH DE number 3988712 (Why is no real title available?)
• scientific article; zbMATH DE number 4047091 (Why is no real title available?)
• scientific article; zbMATH DE number 4064000 (Why is no real title available?)
• Lower Bounds for Threshold and Symmetric Functions in Parallel Computation
• scientific article; zbMATH DE number 1254029 (Why is no real title available?)
• New lower bounds for parallel computation
• Computational aspects of ideal (t, n)-threshold scheme of Chen, Laing, and Martin

This page was built for publication: Resource bounds for parallel computation of threshold and symmetric functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q751804)