Resource bounds for parallel computation of threshold and symmetric functions

DOI10.1016/0022-0000(91)90042-4zbMath0715.68025OpenAlexW1977014832MaRDI QIDQ751804

Yaacov Yesha, Ming Li

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

symmetric functionslower boundsdeterministic 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)

Cites Work

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

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