Superconcentrators, generalizers and generalized connectors with limited depth
Danny Dolev, Cynthia Dwork, Nicholas J. Pippenger, Avi Wigderson · 1983
We show that the minimum possible size of an n-superconcentrator with depth 2k≥4 is θ(nλ(k, n)), where λ(k, .) is the inverse of a certain function at the k-th level of the primitive recursive hierarchy. It follows that the minimum possible depth of an n-superconcentrator with linear size is θ(β(n)), where β is the inverse of a function growing more rapidly than any primitive recursive function. Similar results hold for generalizers. We give a simple explicit construction for a (d1...dk)-generalizer with depth k and size (d1+...+dk)d1...dk. This is applied to give a simple explicit construction for a generalized n-connector with depth 2k−3 and size (2d1+3d2+...+3dk−1+2dk) d1...dk. These are the best explicit constructions currently available. We also show that, for each fixed k≥2, the minimum possible size of a generalized n-connector with depth k is Ω(n1+1/k) and 0((n log n)1+1/k).