Superconcentrators, generalizers and generalized connectors with limited depth

ABSTRACT

We show that the minimum possible size of an n-superconcentrator with depth 2k≥4 is &thgr;(n&lgr;(k, n)), where &lgr;(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 &thgr;(&bgr;(n)), where &bgr; 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 &Ohgr;(n1+1/k) and 0((n log n)1+1/k).

REFERENCES

• 1: L. A. Bassalygo, "Asymptotically Optimal Switching Circuits", Prob. Info. Trans., 17 (1981) 206-211.
• 2: Ashok K. Chandra , Steven Fortune , Richard Lipton, Unbounded fan-in circuits and associative functions, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.52-60, December 1983 [doi>10.1145/800061.808732]
• 3: Ashok K. Chandra , Steven Fortune , Richard J. Lipton, Lower Bounds for Constant Depth Circuits for Prefix Problems, Proceedings of the 10th Colloquium on Automata, Languages and Programming, p.109-117, July 18-22, 1983
• 4: K. M. Chung and C. K. Wong, "Construction of a Generalized Connector with 5.8n log2 n Edges", IEEE Trans. on Comp., 29 (1980) 1029-1032.
• 5: M. Furst, J. B. Saxe and M. Sipser, "Parity, Circuits and the Polynomial-Time Hierarchy", IEEE Symp. on Found. of Comp. Sci., 22 (1981) 260-270.
• 6: Zvi Galil , Wolfgang J. Paul, An efficient general purpose parallel computer, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.247-262, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802478]
• 7: V. A. Garmash and L. A. Shor, "Multistage One-Shot Batch Switching Arrangements", Prob. of Info. Trans., 13 (1978) 320-323.
• 8: Thomas Lengauer , Robert E. Tarjan, Asymptotically tight bounds on time-space trade-offs in a pebble game, Journal of the ACM (JACM), v.29 n.4, p.1087-1130, Oct. 1982 [doi>10.1145/322344.322354]
• 9: G. Lev, "Size Bounds and Parallel Algorithms for Networks", Thesis, Department of Computer Science, University of Edinburgh, September 1980.
• 10: G. M. Masson and B. W. Jordan, Jr., "Generalized Multi-Stage Connection Networks", Networks, 2 (1972) 191-209.
• 11: S. Nakamura and G. M. Masson, "Lower Bounds on Crosspoints in Concentrators", IEEE Trans. on Comp., (to appear).
• 12: David Nassimi , Sartaj Sahni, Parallel permutation and sorting algorithms and a new generalized connection network, Journal of the ACM (JACM), v.29 n.3, p.642-667, July 1982 [doi>10.1145/322326.322329]
• 13: Yu. P. Ofman, "A Universal Automaton", Trans. Moscow Math. Soc., 14 (1965) 200-215.
• 14: W. J. Paul, R. E. Tarjan and J. R. Celoni, "Space Bounds for a Game on Graphs", Math. Sys. Theory, 10 (1977) 239-251.
• 15: M. S. Pinsker, "On the Complexity of a Concentrator", Internat. Teletraffic Conf., 7 (1973) 318/1-4.
• 16: N. Pippenger, "Superconcentrators", SIAM J. Comp., 6 (1977) 298-304.
• 17: N. Pippenger, "Generalized Connectors", SIAM J. Comp., 7 (1978) 510-514.
• 18: N. Pippenger, "On Rearrangeable and Non-Blocking Switching Networks", J. Comp. and Sys. Sci., 17 (1978) 145-162.
• 19: N. Pippenger, "A New Lower Bound for the Number of Switches in Rearrangeable Networks", SIAM J. Alg. and Disc. Meth., 1 (1980) 164-167.
• 20: N. Pippenger, "Superconcentrators of Depth 2", J. Comp. and Sys. Sci., 24 (1982) 82-90.
• 21: Nicholas Pippenger, Advances in Pebbling (Preliminary Version), Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.407-417, July 12-16, 1982
• 22: N. Pippenger and A. C.-C. Yao, "Rearrangeable Networks with Limited Depth", SIAM J. Alg. and Disc. Meth., to appear.
• 23: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 24: C. D. Thompson, "Generalized Connection Networks for Parallel Processor Interconnection", IEEE Trans. on Comp., 27 (1978) 1119-1125.
• 25: M. Tompa, "Time-Space Tradeoffs for Computing Functions, Using Connectivity Properties of Their Circuits", J. Comp. and Sys. Sci., 20 (1980) 118-132.
• 26: L. G. Valiant, "Graph-Theoretic Properties in Computational Complexity", J. Comp. and Sys. Sci., 13 (1976) 278-285.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Theory