@conference {18132,
	title = {Trade-offs between depth and width in parallel computation},
	booktitle = {Foundations of Computer Science, 1983., 24th Annual Symposium on},
	year = {1983},
	month = {1983/11//},
	pages = {146 - 153},
	abstract = {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.},
	doi = {10.1109/SFCS.1983.77},
	author = {Vishkin, Uzi and Wigderson,A.}
}
