Expanders, sorting in rounds and superconcentrators of limited depth

ABSTRACT

Expanding graphs and superconcentrators are relevant to theoretical computer science in several ways. Here we use finite geometries to construct explicitly highly expanding graphs with essentially the smallest possible number of edges. Our graphs enable us to improve significantly previous results on a parallel sorting problem, by describing an explicit algorithm to sort n elements in k time units using &Ogr;(n&agr;k) processors, where, e.g., &agr;2 = 7/4. Using our graphs we can also construct efficient n-superconcentrators of limited depth. For example, we construct an n superconcentrator of depth 3 with &Ogr;(n4/3) edges; better than the previous known results.

REFERENCES

• 1: iI. Abelson, A note on time space tradeoffs for computing continuous l'unctioas, !nfor. Proc. l,ettcrs 8 (1979), 215-217.
• 2: M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
• 3: N. A!on, Eigenvalues, geometric expanders, sorting in rounds and I/amsey theory, preprint.
• 4: N. Aton and V.D. Miiman, ki, isoperimetrlc inequalities for graphs and superconcentrators, J. Combinatorial theory, Set. B, to appear.
• 5: N. Alon and V.D. Milman, eigenvalues, expanders and superconcentrators, Proc. 25th Annual Syrup.on Foundations of Comp. Sci., Florida (1984), 320-322.
• 6: B. Bol!obds, "E.,,.tremal Graph Theory," Academic Press, London and New York (1978).
• 7: V.E. Bench, *'Mathematical Theory or Connecting Networks and Telephone Traffic," Academic Press, London and New York (1965).
• 8: N.G. deBruijn and P. Erdi3s, On a combinatorial problem, Indagationes Math. 20 (1948), 421-423.
• 9: B. Bollob~s and P. Itell, Sorting antt Graphs, prepdnt.
• 10: B. Boliobfis and M. Rosenfeld, sorting in one round, Israel J. Math 38 (1981), 154-160.
• 11: B. Bollob~s and A. Thomason, Pare!lel sorting, Discrete Appl. Math $ 09as), 1-11.
• 12: F.R.K. Chung, On Concentrators, superconcentrators, generalizers, and nonblocking networks, Bell Sys. Tech. J. 58 (1978), 1765-1777.
• 13: D. Dolev, C. Dwork, N. Pippong;cr and A. Wigderson, Superconcentrators, Generalizers and generalized connectors with limited depth, preprint.
• 14: O. Gabber and Z. Calil, Explicit construction of linear sized superconcentrators, J. Comp. and Sys. Sci. 22 (1981), 407-420.
• 15: R.K. Guy and S. Znam, A problem of Zarenkiewicz, in ~Recent Progress in combinatorics" (W.T. Tutte, ed.), Academic Press (1969), 237-243.
• 16: M. Hall, Jr., "Combina,.orial Theory," Wiley and Sons, New York and London (1967), 128-131.
• 17: R. Hiiggvist and P. Hell, Graphs and parallel comparison agorithms, Congr. Num. 29 (1980), 497-509.
• 18: R. Hiiggvist and P. tlell, Parallel sorting with constant time for comparisons, SIAM J. Comp. 10 (1081), 465-472.
• 19: R. }I:~ggvist and P. ltell, Sorting and merging in rounds, SIAM J. Alg. and Disc. Meth. 3 (1082), 465-473.
• 20: Joseph Ja'Ja', Time-space tradeoffs for some algebraic problems, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.339-350, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804683]
• 21: M. Klawe, Non-existence of one-dimensional expanding graphs, Proc. 22nd Ann. Syrup. Found. Comp. Sci. Nashville (1981), 10~}-113.
• 22: 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]
• 23: G.A. Margulis, Explicit constructions of concentrators, Prob. Per. Infor. 9 (4), (1973), 71-80 (english translation in Problems of Infor. Trans. (1975), 325-332.).
• 24: R. Meshulam, A geometric construction of n superconcentrator of depth 2, preprint.
• 25: M. l'inkser, On the complexity of a concentrator, 7th International TeleLramc Conference, Stockholm, June 1973, 318/1-318/4.
• 26: N. Pippenger, Superconcentrators, SiAM J. Computing 6 (1977), 298-304.
• 27: Nicholas Pippenger, Advances in Pebbling (Preliminary Version), Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.407-417, July 12-16, 1982
• 28: N. Pippenger, Explicit construction of highly expanding graphs, preprint.
• 29: W.j. Paul, R.E. Tarjan and J.R. Celoni, Space bounds for a game on graphs, Math. Sys. Theory 20 {1977), 239-251.
• 30: S. Scheele, Final report to office of environmental education, Dept. of Health, Education and Welfare, Social Engineering Technology, Los Angeles, CA 1977.
• 31: R.M. Tanner, Explicit construction of concentrators from generalized N-gons, SIAM 3. AIg. diBcr. Meth. 5 (1984), 287-293.
• 32: M. Tompa, time space tradeoffs for computing functions, using connectivity properties of their circuits, J. Comp. and Sys. Sci. 20 (1980), 118-132.
• 33: L.G. Valiant, Parallelism in comparison networks. SIAM J. Comp. 4 (1975), 348-355.
• 34: L.G. Valiant, Graph theoretic properties in computational complexity, J. Comp. and Sys. Sci. 13 (1976), 278-285.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory, Verification