Trade-Offs between Depth and Width in Parallel Computation

DOI10.1137/0214024MaRDI QIDQ3691060zbMATH OpenOpenAlexFDO

Authors Uzi Vishkin, A. Wigderson

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

communication widthlower boundsPRAM models of parallel computationtime complexitytrade offs between complexity measures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Depth-size trade-offs for parallel prefix computation
• Time-work tradeoffs for parallel algorithms
• scientific article; zbMATH DE number 3940742
• Processor Allocation for Horizontal and Vertical Parallelism and Related Speedup Bounds
• Dimension-wise decompositions and their efficient parallelization
• On saving space in parallel computation
• scientific article; zbMATH DE number 4085015
• Modular-width: an auxiliary parameter for parameterized parallel complexity
• Width, depth, and space: tradeoffs between branching and dynamic programming

Cited in

(26)

• 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
• On saving space in parallel computation
• Processor-time tradeoffs in PRAM simulations
• PRAMs with variable word-size
• Separating the power of EREW and CREW PRAMs with small communication width
• Gossiping and broadcasting versus computing functions in networks.
• Processor-time tradeoffs under bounded-speed message propagation. II: Lower bounds
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• scientific article; zbMATH DE number 1696521 (Why is no real title available?)
• scientific article; zbMATH DE number 3940742 (Why is no real title available?)
• scientific article; zbMATH DE number 4060722 (Why is no real title available?)
• Lower bounds on the complexity of real-time branching programs
• Gossiping and broadcasting versus computing functions in networks
• Separating the power of EREW and CREW PRAMs with small communication width
• 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
• Trade-offs between communication throughput and parallel time
• Compression using efficient multicasting
• Resource bounds for parallel computation of threshold and symmetric functions
• Parallel random access machines with bounded memory wordsize
• Lower bounds for recognizing small cliques on CRCW PRAM's

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

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