Limits on the power of concurrent-write parallel machines

DOI10.1016/0890-5401(88)90040-5zbMath0645.68060OpenAlexW2061503133MaRDI QIDQ1103403

P. W. Beame

Publication date: 1988

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(88)90040-5

zbMATH Keywords

paritypolynomial number of processorsconcurrent-read-concurrent-write parallel RAMfunction of Boolean inputsinteger addition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of operating systems (68N25)

Related Items

Exact lower time bounds for computing Boolean functions on CREW PRAMs, The parallel complexity of integer prefix summation, Lower bounds for recognizing small cliques on CRCW PRAM's

Cites Work

• Unnamed Item
• Unnamed Item
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Parallel computation and conflicts in memory access
• Simulation of Parallel Random Access Machines by Circuits
• Parity, circuits, and the polynomial-time hierarchy
• Constant Depth Reducibility
• Trade-Offs between Depth and Width in Parallel Computation
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• On Parallel Searching