Superconcentrators of Depth 2
It is shown that every n-superconcentrator of depth 2 has size μ(n log n); that there exist n-superconcentrators of depth 2 and size O(n(log n)2); and that there exist n-superconcentrators on which the pebble game can be played in space S and time [image], for a wide range of values of S.
© 1982 Elsevier Ltd.
Nicholas Pippenger, Superconcentrators of depth 2, Journal of Computer and System Sciences, Volume 24, Issue 1, February 1982, Pages 82-90, ISSN 0022-0000, 10.1016/0022-0000(82)90056-3. (http://www.sciencedirect.com/science/article/pii/0022000082900563)