Tiny families of functions with random properties (preliminary version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing

Full text

Pdf (817 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: 574 - 584

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Oded Goldreich	Department of Applied Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel.
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): 3, Downloads (12 Months): 14, 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.195410 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 , 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]
	2	N Alon, Eigenvalues, geometric expanders, sorting in rounds, amd Ramsey theory, Combinatorica, v.6 n.3, p.207-219, 1986 [doi>10.1007/BF02579382]
	3	N. Alon, O. Goldreich, J. Hastad, R. Peralta, "Simple Constructions of Almost k-wise Independent Random Variables", Journal of Random structures and Algorithms, Vol. 3, No. 3, (1992), pp. 289-304.
	4	N. Alon and V.D. Milman, "EigenvMues, Expanders and Superconcentrators", 25th FOCS, 1984, pp. 320-322.
	5	M. Bellare, O. Goldreich, and S. Goldwasser "Randomness in Interactive Proofs", 31 st FOCS, 1990, pp. 318-326.
	6	Ran Canetti , Guy Even , Oded Goldreich, Lower bounds for sampling algorithms for estimating the average, Information Processing Letters, v.53 n.1, p.17-25, Jan. 13, 1995 [doi>10.1016/0020-0190(94)00171-T]
	7	L. Carter and M. Wegman, "Universal Classes of Hash Functions", J. Computer and System Sciences, Vol. 18, pp. 143-154 (1979).
	8	A. Cohen, A. Wigderson, " Dispersers, Deterministic Amplification and Weak random Sources", Proc. of the 30th FOCS, pp. 14-19, 1989.
	9	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]
	10	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]
	11	A. Cohen and A. Wigderson, "Dispensers, Deterministic Amplification, and Weak Random Sources", 30th FOCS, 1989, pp. 14-19.
	12	P. ErdSs and J. Spencer, Probabilistic Methods in Combinatorics, Academic Press, 1974.
	13	G. Even, "Construction of Small Probability Spaces for Deterministic Simulation", M.Sc. thesis, Computer Science Department, Technion, Haifa, Israel, 1991. (In Hebrew, abstract in English)
	14	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]
	15	O. Gaber and Z. Galil, "Exphcit Constructions of Linear Size Superconcentrators", JCSS, 22 (1981), pp. 407-420.
	16	O. Goldreich, H. Krawcyzk and M. Luby, "On the Existence of Pseudorandom Generators", 29th FOCS, pp. 12-24, 1988.
	17	O. Goldreich and A. Wigderson, Technical Report CS94-03, Weizmann Institute, israel, 1994.
	18	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]
	19	R. Impagliazzo and M. Luby, "One-Way Functions are Essential for Complexity Based Cryptography", 30th FOCS, pp. 230-235, 1989.
	20	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.
	21	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]
	22	R. Impagliazzo and D. Zuckerman, "How to Recycle Random Bits", 30th FOCS, 1989, pp. 248-253.
	23	R.M. Karp, N. Pippinger and M. Sipser, "A Time-Randomness Tradeoff", AMS Conference on Probabilistic Computational Complexity, Durham, New Hampshire (1985).
	24	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]
	25	G.A. Margulis, "Explicit Construction of Concentrators", Prob. Per. infor. 9 (4) (1973), 71- 80. (English translation in Problems of infor. Trans. (1975), 325-332.)
	26	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]
	27	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]
	28	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]
	29	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]
	30	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]
	31	M Sipser, Expanders, randomness, or time versus space, Proc. of the conference on Structure in complexity theory, p.325-329, June 1986, Berkeley, California, United States
	32	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]
	33	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]
	34	A. Srinivasan and D. Zuckerman, "Computing with Very Weak Random Sources", manuscript, 1993.
	35	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
	36	U. Vazirani and V. Vazirasd, "Random Polynomial Time Equal to Semi-Random Polynomial Time", Proc. 26th FOCS, pp. 417-428, 1985.
	37	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

	Amnon Ta-Shma, On extracting randomness from weak random sources (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.276-285, May 22-24, 1996, Philadelphia, Pennsylvania, 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