Lower bounds for sorting networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lower bounds for sorting networks

Full text

Pdf (1.02 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-seventh annual ACM symposium on Theory of computing table of contents

Las Vegas, Nevada, United States

Pages: 437 - 446

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Nabil Kahale	Xerox Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, CA and DIMACS
Tom Leighton	Department of Mathematics and Laboratory for Computer Science, MIT, Cambridge, MA
Yuan Ma	Department of Computer Science, Stanford University, Stanford, CA and DIMACS
C. Greg Plaxton	Department of Computer Science, University of Texas at Austin, Austin, TX and DIMACS
Torsten Suel	NEC Research Institute, 4 Independence Way, Princeton, NJ and DIMACS
Endre Szemerédi	Department of Computer Science, Rutgers University, Piscataway, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 25, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/225058.225178 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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]
	2	M. Ajtai, J. Kom16s, and E. Szemer&li. Halvers and expanders. In Proceedings of the .93rd Annual IEEE Symposium on Foundations of Computer Sci-ence, pages 686-689, October 1992.
	3	V. E. Alekseyev. Sorting algorithms with minimum memory. Kibernetika, 5:99-103, 1969.
	4	N. Alon and J. H. Spencer. The Probabilistic Method. Wiley-Interscience, New York, NY, 1991.
	5	K. E. Batcher. Sorting networks and their applica-tions. In Proceedings of the AFIPS Spring Joint Com-puter Conference, volume 32, pages 307-314, 1968.
	6	W. Daniel Hillis, Co-evolving parasites improve simulated evolution as an optimization procedure, Physica D, v.42 n.1-3, p.228-234, June 1990
	7	Takahiro Ikeda, A Probabilistic Selection Network with Butterfly Networks, Proceedings of the 4th International Symposium on Algorithms and Computation, p.267-276, December 15-17, 1993
	8	Shuji Jimbo , Akira Maruoka, Selection Networks with 8n log2n Size and O(log n) Depth, Proceedings of the Third International Symposium on Algorithms and Computation, p.165-174, December 16-18, 1992
	9	N. Kahale. Eigenvalues and expansion of regular graphs. Technical Report 93-7oR, DIMACS, Rutgers University, 1993.
	10	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	11	E. A. Lamagna. The complexity of monotone net-works for certain bilinear forms, routing problems, sorting, and merging. IEEE Trans. Comput., 28:773- 782, 1979.
	12	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	13	Tom Leighton , Yuan Ma, Tight bounds on the size of fault-tolerant merging and sorting networks with destructive faults, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.30-41, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165235]
	14	T. Leighton, Y. Ma, and T. Suel. On probabilistic net-works for selection, merging, and sorting. Manuscript, 1994.
	15	T. Leighton and C. G. Plaxton. A (fairly) simple cir-cuit that (usually) sorts. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Com-puter Science, pages 458-469, October 1990.
	16	P. B. Miltersen, M. S. Paterson, and J. Tarui. The asymptotic complexity of merging networks. In Pro-ceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, pages 236-246, Oc-tober 1992.
	17	1. Parbemy. A computer-assisted optimal depth lower bound for nine-input sorting networks. Mathematical Systems Theory, 24:101-116, 1991.
	18	M. S. Paterson. Improved sorting net works with O(log N) depth. Aigorithmica, 5:75-92, 1990.
	19	Nicholas Pippenger, Communication networks, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	20	Nicholas Pippenger, Selection networks, SIAM Journal on Computing, v.20 n.5, p.878-887, Oct. 1991 [doi>10.1137/0220054]
	21	Nicholas Pippenger , Leslie G. Valiant, Shifting Graphs and Their Applications, Journal of the ACM (JACM), v.23 n.3, p.423-432, July 1976 [doi>10.1145/321958.321962]
	22	D. C. Van Voorhis. An improved lower bound for sorting networks. IEEE Trans. Comput., 21:612-613, 1972.
	23	D. C. Van Voorhis. Toward a lower bound for sort-ing networks. In R. E. Miller and J. W. Thatcher, editors, The Complexity of Computer Computations, pages 119-129. Plenum Press, New York, NY, 1972.
	24	A. C. Yao. Bounds on selection networks. SIAM J. Comput., 9:566-582, 1980.
	25	Andrew Chi-Chih Yao , Foong Frances Yao, Lower Bounds on Merging Networks, Journal of the ACM (JACM), v.23 n.3, p.566-571, July 1976 [doi>10.1145/321958.321976]

CITED BY 2

	Tom Leighton , Yuan Ma , Torsten Suel, On probabilistic networks for selection, merging, and sorting, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.106-118, June 24-26, 1995, Santa Barbara, California, United States
	Giuseppe Campobello , Marco Russo, A scalable VLSI speed/area tunable sorting network, Journal of Systems Architecture: the EUROMICRO Journal, v.52 n.10, p.589-602, October 2006