SUPERCONCENTRATORS

Superconcentrators

Superconcentrators

Superconcentrators were defined by Valiant who showed that there exist n-superconcentrators with at most 238n edges. Superconcentrators have proved useful in counterexemplifying conjectures 1] and in demonstrating the optimality of algorithms . Valiant's proof was based on a complicated recursive construction which used a related type of graph, called a "concentrator," as a basic element. Concentrators were defined by Pinsker , who showed that there exist (n, re)- concentrators (which we shall not define here), with at most 29n edges. Pinsker's proof was based on another rather complicated recursive construction which used a nonconstructive existence theorem concerning bipartite graphs as a basic element. This theorem, though not the recursive construction for concentrators, was also obtained independently by the author . The purpose of this note is to give a sharpened version of the nonconstructive existence theorem and a simple recursive construction, using this theorem as a basic element, for superconcentrators. This yields four benefits. First, the proof that n-superconcentrators with O(n) edges exist is greatly simplified; our construction is simpler than Pinsker's, let lone its composition with Valiant's. Second, our n-superconcentrators have depth O(log n); Valiant's have depth O((log n)2). Third, our superconcentrators have maximum degree (in-degree plus out-degree) 16; Pinsker's concentrators (and thus Valiant's superconcentrators) do not have maximum degree O(1). Finally, our n-superconcentrators have 39n + O(log n) (in fact, at most 40n) edges. LEMMA. For every m, there exists a bipartite graph with 6m inputs and 4m outputs in which every input has out-degree at most 6, every output has in-degree at most 9, and, for every k <-_ 3m and every set ofk inputs, there exists a k-flow (a set ofr vertex-disjoint directed paths) from the given inputs to some set of k outputs. Proof. Let 7r be a permutation on {0, 1, , 36m 1}. From 7r we obtain a bipartite graph G(Tr) by taking {0, 1,. , 6rn 1} as inputs, {0, 1,. , 4m 1} as outputs, and, for every x in,an edge from (x mod 6m) to (Tr(x) mod 4m). In G(r), every input has out-degree at most 6 (since there are only 6 elements of in each residue class mod 6m) and each output has in-degree at most 9 (since there are only 9 elements of in each residue class mod 4m). Expander graphs (and their variations and extensions, like superconcentrators) have various applications of both theoretical and practical nature. They can be used for both, lower bound proofs (e.g. for the proof-length in resolution calculus, for straight-line computations, for pebbling strategies, and also for upper bounds (e.g. sorting networks of logarithmic depth, error-correcting codes, and parallel interconnection networks.

Concentrators are used to interface and combine together low speed communication channels onto higher speed transmission links to alleviate transmission costs. They are also used to construct more powerful switching fabrics such as permutation and broadcast networks. Using an adaptive binary sorting network model, this paper constructs new concentrators and superconcentrators. Unlike the previously reported concentrators and superconcentrators, these new constructions are fast, ...