Resource bounds for parallel computation of threshold and symmetric functions

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

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

lower boundssymmetric functionsdeterministic priorityone shared memory cellparalle computationPRIORITY PRAMprobabilistic PRIORITYthreshold language

Mathematics Subject Classification ID

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

Recommendations

• Publication:3783554
• Lower Bounds for Threshold and Symmetric Functions in Parallel Computation
• Publication:3751010
• New lower bounds for parallel computation
• Improved Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Cites work

• scientific article; zbMATH DE number 3543634 (Why is no real title available?)
• 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
• 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

(7)

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

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)