Approximations of general independent distributions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximations of general independent distributions

Full text

Pdf (737 KB)

Source

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

Victoria, British Columbia, Canada

Pages: 10 - 16

Year of Publication: 1992

ISBN:0-89791-511-9

Authors

Guy Even	Computer Science Department, Technion, Haifa, Israel
Oded Goldreich	Computer Science Department, Technion, Haifa, Israel
Michael Luby	International Computer Science Institute, 1947 Center Street, Berkeley, California
Noam Nisan	Department of Computer Science, Hebrew University, Jerusalem, Israel
Boban Veličkovic	Department of Mathematics, U.C. Berkeley

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): 27, Citation Count: 13

Additional Information:

abstract 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/129712.129714 What is a DOI?

ABSTRACT

We describe efficient constructions of small probability spaces that approximate the independent distribution for general random variables. Previous work on efficient constructions concentrate on approximations of the independent distribution for the special case of uniform boolean-valued random variables. Our results yield efficient constructions of small sets with low discrepancy in high dimensional space and have applications to derandomizing randomized algorithms.

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	Alon, N., Goldreich, O., It#tad, J., Peralta, R., "Simple Constructions of Almost k-wise Independent Random Variables", Proc. 31st FOGS, 1990.
	3	Azar, Y., Motwani, R., Naor, J., "An efficient construction of a multiple value small bias probability space", to appear.
	4	Beck, J., Chen, W., "irregularities of distribution", Cambridge University Press, 1987.
	5	Chor,B., Freidmann, J., Goldreich, O., H#tad, J., Rudich, S., Smolensky, R., "The bit extraction problem and t-resilient functions", Proc. 26th FOCS, 1985, pp. 396-407
	6	B. Chor , O. Goldreich, On the power of two-point based sampling, Journal of Complexity, v.5 n.1, p.96-106, March 1989 [doi>10.1016/0885-064X(89)90015-0]
	7	Even, G., "Construction of Small Probabilistic Spaces for Deterministic Simulation", M. Sc. (in Computer Science) thesis, submitted to the Senate of the Technion (Israel Institute of Technology) in Aug. 1991. (In Hebrew, abstract in English).
	8	Richard M. Karp , Avi Wigderson, A fast parallel algorithm for the maximal independent set problem, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.266-272, December 1984 [doi>10.1145/800057.808690]
	9	Knuth, D., Yao, A., "The complexity of non uniform random number generation", in Algorithms and Complexity, Ed. J. Traub, AC Press, New York, pp. 357-428, 1976.
	10	N. Linial , N. Nisan, Approximate inclusion-exclusion, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.260-270, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100250]
	11	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]
	12	Michael Luby , Boban Veličkovic, On deterministic approximation of DNF, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.430-438, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103464]
	13	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]
	14	N. Nisan, Pseudorandom generators for space-bounded computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.204-212, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100242]
	15	Niederreiter, H., "Constructions of Low-Discrepancy Point Sets and Sequences", manuscript and lecture notes.

CITED BY 13

	Nati Linial , Michael Luby , Michael Saks , David Zuckerman, Efficient construction of a small hitting set for combinatorial rectangles in high dimension, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.258-267, 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
	Oded Goldreich , Avi Wigderson, Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.574-584, May 23-25, 1994, Montreal, Quebec, Canada
	Peter Auer , Philip M. Long , Aravind Srinivasan, Approximating hyper-rectangles: learning and pseudo-random sets, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.314-323, May 04-06, 1997, El Paso, Texas, 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
	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
	Eli Ben-Sasson , Madhu Sudan , Salil Vadhan , Avi Wigderson, Randomness-efficient low degree tests and short PCPs via epsilon-biased sets, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Amir Shpilka , Avi Wigderson, Derandomizing homomorphism testing in general groups, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Danny Harnik , Ran Raz, Higher lower bounds on monotone size, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.378-387, May 21-23, 2000, Portland, Oregon, United States
	Avi Wigderson, The amazing power of pairwise independence (abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.645-647, May 23-25, 1994, Montreal, Quebec, Canada
	L. Sunil Chandran, A lower bound for the hitting set size for combinatorial rectangles and an application, Information Processing Letters, v.86 n.2, p.75-78, 30 April 2003
	Benjamin Doerr , Michael Gnewuch , Anand Srivastav, Bounds and constructions for the star-discrepancy via δ-covers, Journal of Complexity, v.21 n.5, p.691-709, October 2005
	Yuval Rabani , Amir Shpilka, Explicit construction of a small epsilon-net for linear threshold functions, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA