Trade-Offs between Depth and Width in Parallel Computation

DOI10.1137/0214024zbMath0573.68015OpenAlexW2126552237MaRDI QIDQ3691060

Avi Wigderson, Uzi Vishkin

Publication date: 1985

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0214024

zbMATH Keywords

lower boundstime complexitycommunication widthPRAM models of parallel computationtrade offs between complexity measures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (17)

Gossiping and broadcasting versus computing functions in networks ⋮ Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions ⋮ Separation and lower bounds for ROM and nondeterministic models of parallel computation ⋮ Limits on the power of concurrent-write parallel machines ⋮ Simulations among concurrent-write PRAMs ⋮ Lower bound arguments with ``inaccessible numbers ⋮ Some considerations about NPRIORITY(1) without ROM ⋮ Separating the power of EREW and CREW PRAMs with small communication width ⋮ Gossiping and broadcasting versus computing functions in networks. ⋮ Lower bounds on the complexity of real-time branching programs ⋮ Trade-offs between communication throughput and parallel time ⋮ Compression using efficient multicasting ⋮ Properties of complexity measures for PRAMs and WRAMs ⋮ On the power of concurrent-write PRAMs with read-only memory ⋮ The power of multimedia: Combining point-to-point and multi-access networks ⋮ Separating the power of EREW and CREW PRAMs with small communication width ⋮ Resource bounds for parallel computation of threshold and symmetric functions

This page was built for publication: Trade-Offs between Depth and Width in Parallel Computation