Small-bias probability spaces: efficient constructions and applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Small-bias probability spaces: efficient constructions and applications

Full text

Pdf (979 KB)

Source

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

Baltimore, Maryland, United States

Pages: 213 - 223

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

J. Naor	IBM Almaden Research Center, 650 Harry Road, San Jose, CA
M. Naor

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 37, Citation Count: 31

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/100216.100244 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	M. Ajtai and A. Wigderson, Deterministic simulation of probabilistic constant depth computation, FOCS '85, pp. 11-19.
	2	M. Ajtai , J. Komlos , E. Szemeredi, Deterministic simulation in LOGSPACE, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.132-140, January 1987, New York, New York, United States [doi>10.1145/28395.28410]
	3	N Alon, Explicit construction of exponential sized families of K-independent sets, Discrete Mathematics, v.58 n.2, p.191-193, Feb. 1986 [doi>10.1016/0012-365X(86)90161-5]
	4	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]
	5	E. Bach, Realistic analysis of some randomized algorithms, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.453-461, January 1987, New York, New York, United States [doi>10.1145/28395.28444]
	6	R. Ben-Nathan, M.Sc. Thesis, Hebrew University (1990).
	7	M. Blum , S. Kanna, Designing programs that check their work, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.86-97, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73015]
	8	B. Berger and J. Rompel, Simulating (log c n)-wise independence in NC, FOCS '89 pp. 2-7.
	9	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]
	10	B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich and R. Smolensky, The bit extraction problem or t-resilient functions, FOCS '85, pp. 396-407.
	11	A. Cohen and A. Wigderson, Dispersers, deterministic amplification and weak random sources, FOCS '89, pp. 14-19.
	12	A. Cohen and A. Wigderson, Multigraph Amplification, Survey (1989).
	13	W. Feller, An Introduction to probability theory and its applications, John Wiley, 1968.
	14	R. Freivalds, Fast probabilistic algorithms, Springer Verlag Lecture Notes in CS #74, Mathematical Foundations of CS, pp. 57-69 (1979).
	15	O. Gaber and Z. Galil, Explicit construction of linear size superconcentrators, JCSS, 22, p. 407 (1981).
	16	R. Impagliazzo and D. Zuckerman, Recycling random bits, FOCS '89, pp. 248-253.
	17	S Jimbo , A Maruoka, Expanders obtained from affine transformations, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.88-97, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22155]
	18	J. Justesen, A class of asymptotically good algebraic codes, IEEE trans. Infor. Theory, 18 (1972) 652-656.
	19	R. Karp and N. Pippenger, A time randomness tradeoff, AMS conference on probabilistic computation and complexity, Durham NC, (1983).
	20	Howard Karloff , Prabhakar Raghavan, Randomized algorithms and pseudorandom numbers, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.310-321, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62242]
	21	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]
	22	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]
	23	A Lubotzky , R Phillips , P Sarnak, Explicit expanders and the Ramanujan conjectures, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.240-246, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12154]
	24	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]
	25	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
	26	F. J. MacWilliams and N. J. A. Sloane, The theory of error correcting codes, North Holland, Amsterdam, 1977.
	27	N. Nisan and A. Wigderson, Hardness vs. Randomness, FOCS '88, pp. 2-11.
	28	R. Peralta, On the randomness complexity of algorithms, University of Wisconsin, Milwaukee, CS Research Report TR 90-1.
	29	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]
	30	R. Rivest, A. Shamir and L. Adelman, CACM (1978).
	31	Miklos Santha, On using deterministic functions to reduce randomness in probabilistic algorithms, Information and Computation, v.74 n.3, p.241-249, Sept. 1987 [doi>10.1016/0890-5401(87)90023-X]
	32	G. Seroussi and N. Bshouti, Vector sets for exhaustive testing of logic circuits, IEEE Trans. on Info. Theory, vol. 34, pp. 513-522 (1988).
	33	Michael Siper, Expanders, randomness, or time versus space, Journal of Computer and System Sciences, v.36 n.3, p.379-383, June 1988 [doi>10.1016/0022-0000(88)90035-9]
	34	J. Spencer, Ten lectures on the probabilistic method. SIAM (Philadelphia), 1987.
	35	Umesh Virkumar Vazirani, Randomness, adversaries and computation (random polynomial time), 1986

CITED BY 31

	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
	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
	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
	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
	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
	Uriel Feige , Joe Kilian, Impossibility results for recycling random bits in two-prover proof systems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.457-468, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Lisa Hellerstein , Vijay Raghavan , Krishnan Pillaipakkamnatt , Dawn Wilkins, How many queries are needed to learn?, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.190-199, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Noga Alon , Raphael Yuster , Uri Zwick, Color-coding, Journal of the ACM (JACM), v.42 n.4, p.844-856, July 1995
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Joan Boyar , Gilles Brassard , René Peralta, Subquadratic zero-knowledge, Journal of the ACM (JACM), v.42 n.6, p.1169-1193, Nov. 1995
	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
	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
	Ulf Berggren, Linear time deterministic learning of k-term DNF, Proceedings of the sixth annual conference on Computational learning theory, p.37-40, July 26-28, 1993, Santa Cruz, California, 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
	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
	Lisa Hellerstein , Krishnan Pillaipakkamnatt , Vijay Raghavan , Dawn Wilkins, How many queries are needed to learn?, Journal of the ACM (JACM), v.43 n.5, p.840-862, Sept. 1996
	Nader H. Bshouty , Sally A. Goldman , Thomas R. Hancock , Sleiman Matar, Asking questions to minimize errors, Proceedings of the sixth annual conference on Computational learning theory, p.41-50, July 26-28, 1993, Santa Cruz, 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
	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
	Avrim Blum , Steven Rudich, Fast learning of k-term DNF formulas with queries, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.382-389, May 04-06, 1992, Victoria, British Columbia, Canada
	Noga Alon , Raphy Yuster , Uri Zwick, Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.326-335, May 23-25, 1994, Montreal, Quebec, Canada
	Giovanni Di-Crescenzo , Yuval Ishai , Rafail Ostrovsky, Universal service-providers for database private information retrieval (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.91-100, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Andrej Bogdanov, Pseudorandom generators for low degree polynomials, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Avrim Blum , Jeffrey Jackson , Tuomas Sandholm , Martin Zinkevich, Preference Elicitation and Query Learning, The Journal of Machine Learning Research, 5, p.649-667, 12/1/2004
	Dana Angluin , James Aspnes , Jiang Chen , Yinghua Wu, Learning a circuit by injecting values, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	G. Edward Suh , Dwaine Clarke , Blaise Gassend , Marten van Dijk , Srinivas Devadas, Efficient Memory Integrity Verification and Encryption for Secure Processors, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.339, December 03-05, 2003
	Shachar Lovett, Unconditional pseudorandom generators for low degree polynomials, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Dana Angluin , James Aspnes , Jiang Chen , Yinghua Wu, Learning a circuit by injecting values, Journal of Computer and System Sciences, v.75 n.1, p.60-77, January, 2009
	Ali A. Kanso, An efficient cryptosystem Delta for stream cipher applications, Computers and Electrical Engineering, v.35 n.1, p.126-140, January, 2009