The amazing power of pairwise independence (abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The amazing power of pairwise independence (abstract)

Full text

Pdf (160 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: 645 - 647

Year of Publication: 1994

ISBN:0-89791-663-8

Author

Avi Wigderson

Institute for Computer Science, Hebrew University, Jerusalem, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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.195420 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	(1) N. Alon, O. Goldreich, J. Hastad, R. Peralta, "Simple Constructions of Almost k-wise Independent Random Variables", Journal of Random Structures and Algomthms, Vol. 3, No. 3, pp. 289-304, 1992.
	3	(1) B. Berger, J. Rompel, "Simulating (logCn)-wise independence in NC', 30th FOCS, pp. 2-7, 1989.
	4	(4) L. Carter and M. Wegman, "Universal Classes of Hash Functions", Y. Computer and System Sciences, Vol. 18, pp. 143-154 1979.
	5	Benny Chor , Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM Journal on Computing, v.17 n.2, p.230-261, April 1988 [doi>10.1137/0217015]
	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	(4) M. Dietzfelbinger, A. Karlin, F. Meyer auf der Heide, H. Rohnert, R. E. Tarjan, "Dynamic perfect hashing: Upper and lower bounds", 29th FOCS, pp. 524-531, 1988.
	8	(4) M. Fredman, a. Komlos, and E. Szemeredi, Storing a sparse table with O(1) worst-case access time, 23rd FOCS, pp. 165-169, 1982.
	9	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]
	10	(9) O. Goldreich, H. Krawcyzk and M. Luby, "On the Existence of Pseudorandom Generators", 29th FOCS, pp. 12-24, 1988.
	11	O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
	12	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 [doi>10.1145/195058.195410]
	13	S Goldwasser , M Sipser, Private coins versus public coins in interactive proof systems, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.59-68, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12137]
	14	(9) R. Impagliazzo and M. Luby, "One- Way Functions are Essential for Complexity Based Cryptography", 30th FOCS, pp. 230-235, 19s9.
	15	(9) R. Impagliazzo and L.A. Levin, "No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random ", 31st FOCS, pp. 812-821, 1990.
	16	R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
	17	(3) R. Impagliazzo and D. Zuckerman, "How to Recycle Random Bits", 3Oth FOCS, pp. 248-253, 1989.
	18	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]
	19	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 [doi>10.1145/167088.167166]
	20	M Luby, A simple parallel algorithm for the maximal independent set problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.1-10, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22146]
	21	(1), M. Luby, "Removing randomness in parallel computation without processor penalty", 29th FOCS, pp. 162-173, 1988.
	22	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
	23	Y. Mansour , N. Nisan , P. Tiwari, The computational complexity of universal hashing, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.235-243, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100246]
	24	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]
	25	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]
	26	Noam Nisan, RL⊆SC, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.619-623, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129772]
	27	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 [doi>10.1145/167088.167162]
	28	Prabhakar Ragde , Avi Wigderson, Linear-size constant-depth polylog-threshold circuits, Information Processing Letters, v.39 n.3, p.143-146, Aug. 16, 1991 [doi>10.1016/0020-0190(91)90110-4]
	29	Michael Sipser, A complexity theoretic approach to randomness, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.330-335, December 1983 [doi>10.1145/800061.808762]
	30	Larry Stockmeyer, The complexity of approximate counting, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.118-126, December 1983 [doi>10.1145/800061.808740]
	31	Miklos Santha , Umesh V Vazirani, Generating quasi-random sequences from semi-random sources, Journal of Computer and System Sciences, v.33 n.1, p.75-87, Aug. 1986 [doi>10.1016/0022-0000(86)90044-9]
	32	(2) A. Srinivasan and D. Zuckerman, "Computing with Very Weak Random Sources", manuscript, 1993.
	33	L. G. Valiant , V. V. Vazirani, NP is as easy as detecting unique solutions, Theoretical Computer Science, v.47 n.1, p.85-93, Nov. 1986
	34	(2) U. Vazirani and V. Vazirani, "Random Polynomial Time Equal to Semi-Random Polynomial Time", Proc. 26th FOCS, pp. 417-428, 1985.
	35	Avi Wigderson , David Zuckerman, Expanders that beat the eigenvalue bound: explicit construction and applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.245-251, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167163]
	36	David Zuckerman, Simulating BPP using a general weak random source, Proceedings of the 32nd annual symposium on Foundations of computer science, p.79-89, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185351]

CITED BY 2

	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
	A. R. Calderbank , A. Gilbert , K. Levchenko , S. Muthukrishnan , M. Strauss, Improved range-summable random variable construction algorithms, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia