On construction of k-wise independent random variables

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On construction of k-wise independent random variables

Full text

Pdf (924 KB)

Source

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

Montreal, Quebec, Canada

Pages: 564 - 573

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Howard Karloff	College of Computing, Georgia Institute of Technology, Atlanta, GA
Yishay Mansour	Computer science Dept., Tel-Aviv University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

	ABI86	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]
	AS92	N. Alon and J. Spencer, The Probabilistic Method, Wiley, 1992.
	BR89	B. Berger and J. Rompel, "Simulating (Iog#n)-wise independence in NC," Pvoc. 30th IEEE Symposium on Foundations of Computer Science, 1989, pages 2-7.
	CGHFRS85	B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich, and R. Smolensky, "The Bit Extraction Problem or t- Resilient Functions," Proc. 26th IEEE Symposium on Foundations of Computer Science, 1985, pages 396-407.
	Fri92	J. Friedman, "On the Bit Extraction Problem," Proc. 33rd IEEE Symposium on Foundations of Computer Science, 1992, pages 314-319.
	Joffe74	A. Joffe, "On a Set of Almost Deterministic k-Independent Random Variables," Annals of Probability 2 (1974), pages 161-162.
	KM93	Daphne Koller , Nimrod Megiddo, Constructing small sample spaces satisfying given constraints, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.268-277, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167168]
	Lub86	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]
	Lub88	M. Luby, "Removing Randomness in Parallel Computation Without a Processor Penalty," Proc. 29th IEEE Symposium on Foundations of Computer Science, 1988, pages 162-173.
	MNN89	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
	Sch92	Leonard J. Schulman, Sample spaces uniform on neighborhoods, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.17-25, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129715]

CITED BY 6

	Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Amortizing randomness in private multiparty computations, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.81-90, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Michael T. Goodrich, Fixed-dimensional parallel linear programming via relative &egr;-approximations, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.132-141, January 28-30, 1996, Atlanta, Georgia, United States
	Eyal Kushilevitz , Yishay Mansour, Randomness in private computations, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.181-190, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Ran Canetti , Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Randomness vs. fault-tolerance, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.35-44, August 21-24, 1997, Santa Barbara, California, United States
	Florin Rusu , Alin Dobra, Fast range-summable random variables for efficient aggregate estimation, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	Hanno Lefmann, Sparse Parity-Check Matrices over ${GF(q)}$, Combinatorics, Probability and Computing, v.14 n.1, p.147-169, January 2005