Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version)
Danny Dolev, Cynthia Dwork, Nicholas J. Pippenger, Avi Wigderson · Symposium on the Theory of Computing · 1983
We show that the minimum possible size of an n-superconcentrator with depth 2k~4 is e(nX(k, n)), where k(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 8(~(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 (dl...dk)-generalizer with depth k and size (dl+...+dk)dl...dk. This is applied to give a simple explicit construction for a generalized n-connector with depth 2k-3 and size (2dl+3d2+...+3dk_l+2dk) dl...d k. 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 ~(n l+I/k) and O((n log n)l+I/k).