New lower bounds for parallel computation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

New lower bounds for parallel computation

Full text

Pdf (1.00 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 177 - 187

Year of Publication: 1986

ISBN:0-89791-193-8

Authors

M Li	Department of Computer and Information Science, The Ohio State University, Columbus, OH
Y Yesha	Department of Computer and Information Science, The Ohio State University, Columbus, OH

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 11, Citation Count: 5

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/12130.12148 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.

	AS	B. Awerbuch and Y. Shiloach, New connectivity and MSF algorithms for ultracomputers and PRAM, Proc. IEEE conf. on parallel proc., 1983, 175-179.
	B	C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
	CD	Stephen Cook , Cynthia Dwork, Bounds on the time for parallel RAM's to compute simple functions, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.231-233, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802196]
	FMRW	F E Fich , F Meyer auf der Heide , P Ragde , A Wigderson, One, two, three . . . infinity: lower bounds for parallel computation, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.48-58, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22151]
	FRW	Faith E. Fich , Prabhakar L. Ragde , Avi Wigderson, Relations between concurrent-write models of parallel computation, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.179-189, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806745]
	Ga	Zvi Galil*, Optimal parallel algorithms for string matching, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.240-248, December 1984 [doi>10.1145/800057.808687]
	H	J. Hartmanis, Generalized Kolmogorov-complexity and the structure of feasible computations. FOCS'83, p.439.
	HCS	D. S. Hirschberg , A. K. Chandra , D. V. Sarwate, Computing connected components on parallel computers, Communications of the ACM, v.22 n.8, p.461-464, Aug. 1979 [doi>10.1145/359138.359141]
	LV	Ming Li , Paul M. B. Vitanyi, Tape versus queue and stacks: the lower bounds, Information and Computation, v.78 n.1, p.56-85, July 1988 [doi>10.1016/0890-5401(88)90003-X]
	LY	M. Li and Y. Yesha, Separation results for ROM and nondeterministic models of parallel computation, Ohio State University, CISRC-TR-86-7, 1985.
	M	W. Maass, Quadratic lower bounds for deterministic and nondeterministie one-tape Turing machines, Transactions of AMS, 292,2 (Dee. 1985), pp. 675-693.
	MR	F. Meyer auf der Heide, R. Reischuk, On limits to speed up parallel machines by large hardware and unbounded communication, FOCS'84, p.56
	MW	F. Meyer auf der Heide and A. Wigderson, The complexity of parallel sorting, ACM FOCS'85, pp. 532-540.
	P	F.P. Preparata, New parallel-sorting schemes, IEEE Trans. Comp. c-27. p.669
	P1	W. Paul, Kolmogorov complexity and lower bounds, 2nd International conference on fundamentals of computation theory. {1979)
	PSS	Wolfgang J. Paul , Joel I. Seiferas , Janos Simon, An information-theoretic approach to time bounds for on-line computation (preliminary version), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.357-367, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804685]
	R	J. Reif, An optimal algorithm for integer sorting, FOCS'85. pp. 494-504.
	SV	Y. Shiloach and U. Vishkin, Finding the maximum, merging and sorting on parallel models of computation, J. of Algorithms 2, 1981, pp. 88-102.
	SV1	Y. Shiloach and U. Vishkin, An O(logn) parallel connectivity algorithm, J. of Algorithms 3, 1982, pp. 57-67.
	VW	U. Vishkin and A Wigderson, Trade-offs between depth and width in parallel computation, SIAM J. Computing, Vol. 14. No 2, May 1985, pp 303-314.
	Y	Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States

CITED BY 5

	Micah Adler , Tom Leighton, Compression using efficient multicasting, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.153-162, May 21-23, 2000, Portland, Oregon, United States
	Yishay Mansour , Noam Nisan , Uzi Vishkin, Trade-offs between communication throughput and parallel time, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.372-381, May 23-25, 1994, Montreal, Quebec, Canada
	Ming Li , Yaacov Yesha, New lower bounds for parallel computation, Journal of the ACM (JACM), v.36 n.3, p.671-680, July 1989
	P. Beame , J. Hastad, Optimal bounds for decision problems on the CRCW PRAM, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.83-93, January 1987, New York, New York, United States
	S. J. Bellantoni, Parallel RAMs with bounded memory wordsize, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.83-91, June 18-21, 1989, Santa Fe, New Mexico, United States