Constructing small sample spaces satisfying given constraints

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Constructing small sample spaces satisfying given constraints

Full text

Pdf (950 KB)

Source

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

San Diego, California, United States

Pages: 268 - 277

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Daphne Koller
Nimrod Megiddo

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/167088.167168 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	L. Adleman, "Two theorems on random polynomial time," in: Proceedings of the 19th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Angeles, 1978, pp. 75-83.
	3	N. Alon, O. Goldreich, J. Hastad, and R. Peralta, "Simple constructions of almost k-wise independent random variables," in: Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Angeles, 1990, pp. 544-553.
	4	N. Alon, Private communication.
	5	Y. Azar, R. Motwani, and J. Naor. "Approximating arbitrary probability distributions using small sample spaces," unpublished m#nuscript.
	6	B. Berger and J. Rompel. "Simulating (log# n)-wise independence in NC," in: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Angeles, 1989, pp. 2-7.
	7	B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich, and R. Smolensky, "tresilient functions," in: Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Angeles, 1985, pp. 396- 407, 1985.
	8	Guy Even , Oded Goldreich , Michael Luby , Noam Nisan , Boban Veličkovic, Approximations of general independent distributions, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.10-16, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129714]
	9	A. Joffe, "On a set of almost deterministic k-independent random variables," Annals of Probability 2 (1974) 161-162.
	10	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]
	11	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
	12	J. Naor , M. Naor, Small-bias probability spaces: efficient constructions and applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.213-223, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100244]
	13	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]
	14	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]
	15	J. Spencer, Ten Lectures on the Probabilistic Method, Society for Industrial and Applied Mathematics, 1987.

CITED BY 8

	Yishay Mansour , Mariano Schain, Learning with maximum-entropy distributions, Proceedings of the tenth annual conference on Computational learning theory, p.201-210, July 06-09, 1997, Nashville, Tennessee, United States
	D. Sivakumar, Algorithmic derandomization via complexity theory, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Howard Karloff , Yishay Mansour, On construction of k-wise independent random variables, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.564-573, May 23-25, 1994, Montreal, Quebec, Canada
	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
	Mihir Bellare , Madhu Sudan, Improved non-approximability results, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.184-193, May 23-25, 1994, Montreal, Quebec, Canada
	Uri Feige , Joe Kilian, Two prover protocols: low error at affordable rates, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.172-183, May 23-25, 1994, Montreal, Quebec, Canada
	Yishay Mansour , Mariano Schain, Learning with Maximum-Entropy Distributions, Machine Learning, v.45 n.2, p.123-145, November 2001
	Noga Alon , Dana Moshkovitz , Shmuel Safra, Algorithmic construction of sets for k-restrictions, ACM Transactions on Algorithms (TALG), v.2 n.2, p.153-177, April 2006