TY - CONF T1 - Trade-offs between depth and width in parallel computation T2 - Foundations of Computer Science, 1983., 24th Annual Symposium on Y1 - 1983 A1 - Vishkin, Uzi A1 - Wigderson,A. AB - A new technique for proving lower bounds for parallel computation is introduced. This technique enables us to obtain, for the first time. non-trivial tight lower bounds for shared-memory models of parallel computation that allow simultaneous read/write access to the same memory location. The size m of the common memory is called communication width or width in short. For a wide variety of problems (including parity and majority) we show that the time complexity T (depth) and the communication width m are related by the trade-off curve mT2 = #x03A9;(n) (where n is the size of the input). This bound is tight lot every m #x02264;n/log2n We extend our technique to prove mT3 = #x03A9;(n) trade-off for a class of "simpler" functions (includind Boolean Or) on a weaker model that forbids simultaneous write access. This result improves the lower bound of Cook and Dwork [CD-82] when communication is limited. JA - Foundations of Computer Science, 1983., 24th Annual Symposium on M3 - 10.1109/SFCS.1983.77 ER -