Simulating (logcn)-wise independence in NC

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Simulating (logcn)-wise independence in NC

Full text

Pdf (1.28 MB)

Source

Journal of the ACM (JACM) archive
Volume 38 , Issue 4 (October 1991) table of contents

Pages: 1026 - 1046

Year of Publication: 1991

ISSN:0004-5411

Authors

Bonnie Berger	Massachusetts Institute of Technology, Cambridge
John Rompel	Massachusetts Institute of Technology, Cambridge

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): , Downloads (12 Months): , Citation Count: 17

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/115234.115347 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	Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
	2	B. Awerbuch , A. Israeli , Y. Shiloach, Finding euler circuits in logarithmic parallel time, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.249-257, December 1984 [doi>10.1145/800057.808688]
	3	BECK, J, AND FIALA, T. Integral approximation sequences. Math. Prog. 30 (1984), 88-98.
	4	BECK, J. AND SPENCER, J. Interger-making theorems. Disc. Appl. Math. 3 (1981), 1-8.
	5	BERGER, B. Data structures for removing randomness. Tech. Rep. MIT/LCS/TR-436. Laboratory for Computer Science, MIT, Cambridge, Mass., Dec. 1988.
	6	BERGER, B. Using randomness to design efficient deterministic algorithms. PhD dissertation. Dept. Elect. Eng. Comput. Sci., MIT, Cambridge, Mass., May 1990.
	7	CHOR, B., GOLDREICH, O., HASTAD, J., FRIEDMAN, J., RUDICH, S., AND SMOLENSKY. R. The bit extraction problem or t-resilient functions. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science (Oct.). IEEE, New York, 1985, pp. 396-407.
	8	COLE, R., AND HOPCROFT, J. On edge coloring bipartite graphs. SIAM J. Comput. 11 (1982), 540-546.
	9	ERD(~S, P., AND KLEITMAN, D. On coloring graphs to maximize the proportion of multi-colored k-edges. J. Combin. Theory 5, 2 (Sept. 1968), 164-169.
	9a	ERD6s, P., AND SELFRIDGE, J.L. On a combinatorial game. J. Combin. Theory B14, (1973), 298-301.
	10	GABOW, H. N., AND KARIV, O. Algorithms for edge coloring bipartite graphs and multigraphs. SIAM J. Comput. 11 (1982), 117-129.
	11	KILN, J., KALAI, G., AND LINIAL, N. The influence of variables on Boolean functions. In Proceedings of the 29th Annual Symposmm on Foundations of Computer Science (Oct.). IEEE, New York, 1988, pp. 68-80.
	12	Howard J. Karloff , David B. Shmoys, Efficient parallel algorithms for edge coloring problems, Journal of Algorithms, v.8 n.1, p.39-52, March 1987 [doi>10.1016/0196-6774(87)90026-5]
	13	Richard M. Karp , Avi Wigderson, A fast parallel algorithm for the maximal independent set problem, Journal of the ACM (JACM), v.32 n.4, p.762-773, Oct. 1985 [doi>10.1145/4221.4226]
	14	LEV, G. F., PIPPENGER, N. AND VALIANT, L. G. A fast parallel algorithm for routing in permutation networks. IEEE Trans. Comput. 30 (1981), 93-100.
	15	Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
	16	LuBY, M. Removing randomness in parallel computation without a processor penalty. In Proceedings of the 29th Annual Syrnposium on Foundations of Computer Science (Oct.). IEEE, New York, 1988, pp. 162-173.
	17	MOTWANI, R., NAOR, J., AND NAOR, M. A generalized technique for derandomizing parallel algorithms. Unpublished manuscript, Jan. 1989.
	18	Rajeev Motwani , Joseph Seffi Naor , Moni Naor, The probabilistic method yields deterministic parallel algorithms, Proceedings of the 30th IEEE symposium on Foundations of computer science, p.478-516, December 1994, Research Triangle Park, North Carolina, United States
	19	Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]
	20	Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
	21	SPENCER, J Balancing games. J. Combin. Theory, B 23 (1977), 68-74.
	22	Joel Spencer, The probabilistic method, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.41-47, September 1992, Orlando, Florida, United States
	23	VIZING, V.G. On the estimate of the chromatic class of a P-graph. Dlskret. Anal. 3 (1964), 25-30 (in Russian).

CITED BY 17

	Pierre Kelsen, On the parallel complexity of computing a maximal independent set in a hypergraph, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.339-350, May 04-06, 1992, Victoria, British Columbia, Canada
	Noam Nisan , David Zuckerman, More deterministic simulation in logspace, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.235-244, May 16-18, 1993, San Diego, California, United States
	Jeanette P. Schmidt , Alan Siegel , Aravind Srinivasan, Chernoff-Hoeffding bounds for applications with limited independence, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.331-340, January 25-27, 1993, Austin, Texas, United States
	Bonnie Berger, The fourth moment method, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.373-383, January 28-30, 1991, San Francisco, California, United States
	Seth Pettie , Vijaya Ramachandran, Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.713-722, January 06-08, 2002, San Francisco, California
	Bernard Chazelle , Jiří Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.281-290, January 25-27, 1993, Austin, Texas, United States
	László Babai, Paul Erdös (1913-996): his influence on the theory of computing, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.383-401, May 04-06, 1997, El Paso, Texas, United States
	Alessandro Panconesi , Aravind Srinivasan, Fast randomized algorithms for distributed edge coloring, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.251-262, August 10-12, 1992, Vancouver, British Columbia, Canada
	Aravind Srinivasan, New approaches to covering and packing problems, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.567-576, January 07-09, 2001, Washington, D.C., United States
	Suresh Chari , Pankaj Rohatgi , Aravind Srinivasan, Improved algorithms via approximations of probability distributions (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.584-592, May 23-25, 1994, Montreal, Quebec, Canada
	Bernard Chazelle, Computational geometry: a retrospective, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.75-94, May 23-25, 1994, Montreal, Quebec, Canada
	David A. Grable , Alessandro Panconesi, Nearly optimal distributed edge colouring in O(log log n) rounds, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.278-285, January 05-07, 1997, New Orleans, Louisiana, United States
	Maria Serna , Fatos Xhafa, Approximating Scheduling Unrelated Parallel Machines in Parallel, Computational Optimization and Applications, v.21 n.3, p.325-338, March 2002
	Maria Serna , Fatos Xhafa, Approximating Scheduling Unrelated Parallel Machines in Parallel, Computational Optimization and Applications, v.21 n.3, p.325-338, March 2002
	G. Sajith , S. Saxena, Fast parallel edge colouring of graphs, Journal of Parallel and Distributed Computing, v.63 n.9, p.775-785, September 2003
	Aravind Srinivasan, An extension of the Lovász local lemma, and its applications to integer programming, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.6-15, January 28-30, 1996, Atlanta, Georgia, United States
	Harry B. Hunt, III , Madhav V. Marathe , Venkatesh Radhakrishnan , S. S. Ravi , Daniel J. Rosenkrantz , Richard E. Stearns, Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems, Information and Computation, v.173 n.1, p.40-63, February 25, 2002