Lower bounds for randomized exclusive write PRAMs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lower bounds for randomized exclusive write PRAMs

Full text

Pdf (1.20 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures table of contents

Santa Barbara, California, United States

Pages: 254 - 263

Year of Publication: 1995

ISBN:0-89791-717-0

Author

Philip D. MacKenzie

Sandia National Laboratories, Albuquerque, NM

Sponsors

European Theoretical :
IEEE : Institute of Electrical and Electronics Engineers
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 8, Citation Count: 1

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/215399.215454 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	S. Chaudhuri. Sensitive functions and approximate problems. In Proc. 34th Syrup. on Found. of Comp. Sci., pages 186-193, 1993.
	2	Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
	3	Martin Dietzfelbinger , Mirosław Kutyłowski , Rüdiger Reischuk, Exact lower time bounds for computing Boolean functions on CREW PRAMs, Journal of Computer and System Sciences, v.48 n.2, p.231-254, April 1994 [doi>10.1016/S0022-0000(05)80003-0]
	4	Faith E. Fich , Miroslaw Kowaluk , Krzysztof Lorys , Miroslaw Kutylowski , Prabhakar Ragde, Retrieval of scattered information by EREW, CREW and CRCW PRAMs, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.30-41, July 08-10, 1992
	5	M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial time hierarchy. Math. Syst. Theory, 17(1):13-28, 1984.
	6	Joseph Gil , Yossi Matias , Uzi Vishkin, Towards a theory of nearly constant time parallel algorithms, Proceedings of the 32nd annual symposium on Foundations of computer science, p.698-710, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185438]
	7	J. Gil and L# Rudolph. Counting and packing in parallel. In Proc. 15th Intl. Con}. on Parallel Processzng. pages 1000-1002, 1986.
	8	Leslie Ann Goldberg , Mark Jerrum , Philip D. MacKenzie, An Ω(√ log log n) lower bound for routing in optical networks, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.147-156, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181093]
	9	T. Hagerup. Fast parallel space allocation, estimation and integer sorting. Technical Report MPI-I-91- 106, Max-Planck-Institut fiir Informatik, Saarbriicken, 1991.
	10	Torben Hagerup, Fast deterministic processor allocation, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.1-10, January 25-27, 1993, Austin, Texas, United States
	11	Torben Hagerup, Fast Integer Merging on the EREW PRAM, Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.318-329, July 13-17, 1992
	12	Torben Hagerup , Manfred Nowak, Parallel Retrieval of Scattered Information, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.439-450, July 11-15, 1989
	13	Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	14	Miroslaw Kutylowski, Time complexity of Boolean functions on CREW PRAMs, SIAM Journal on Computing, v.20 n.5, p.824-853, Oct. 1991 [doi>10.1137/0220051]
	15	P. MacKenzie. The random adversary: A lower bound technique for randomized parallel algorithms and its application to load balancing. Manuscript.
	16	Noam Nisan, CREW PRAMs and decision trees, SIAM Journal on Computing, v.20 n.6, p.999-1007, Dec. 1991 [doi>10.1137/0220062]
	17	Ian Parberry , Pei Yuan Yan, Improved upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.20 n.1, p.88-99, Feb. 1991 [doi>10.1137/0220005]
	18	P. Ragde, The parallel simplicity of compaction and chaining, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.744-751, July 1990, Warwick University, England
	19	A. C.-C. Yao. Probabilistic computations; Toward a unified measure of complexity. In Proc. 18th Syrup. on Found. of Comp. Sci., pages 222-227, 1977.