The computational complexity of universal hashing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The computational complexity of universal hashing

Full text

Pdf (729 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: 235 - 243

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

Y. Mansour	Laboratory for Computer Science, MIT, 545 Tech. Sq., Cambridge, MA
N. Nisan	Laboratory for Computer Science, MIT, 545 Tech. Sq., Cambridge, MA
P. Tiwari	IBM Research Division, T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 53, Citation Count: 12

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.100246 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	K. Abrahamson. Time-space tradeoffs for branching programs constructed with those for straight line programs. In 27 th Annual Symposium on Foundations of Computer Science, Toronto, Ontario, Canada, pages 402-409, October 1986.
	2	P. Beame, A general sequential time-space tradeoff for finding unique elements, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.197-203, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73026]
	3	P. Beame, M. Tompa, and P. Yan. Communication-space tradeoffs in the boolean model, manuscript.
	4	R. Boppana and M. Sipser. The complexity of finite functions. To appear in Handbook of theor. comp. sci.
	5	A. Borodin and S. Cook. A time-space tradeoff for sorting on a general sequential model of computation. SIAM J. Comput., 1(2):287-297, 1982.
	6	A. Borodin, M. Fischer, D. Kirpatrick, N. Lynch, and M. Tompa. A time-space tradeoff for sorting on non-oblivious machines. Journal of Comput. Syst. and Sci., 22:351-364, 1981.
	7	L. Carter and M. Wegman. Universal hash functions. J. Comp. and Syst. Sci., 18(2):143-154, 1979.
	8	A. Cobham. The recognition problem fro the set of perfect squares, conference record. In IEEE 7th Annual Symposium on Switching and Automata Theory, pages 78-87, 1966.
	9	Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
	10	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]
	11	R. Impagliazzo and D. Zuckerman. How to recycle random bits. In 30 th Annual Symposium on Foundations of Computer Science, Reseach Triangle Park, NC, pages 248-253, October 1989.
	12	V. Krapchenko. A method of determining lower bounds for the complexity of schemes. Math. Notes Acad. Sci. USSR, pages 474-479, 1971.
	13	T. Lam , P. Tiwari , M. Tompa, Tradeoffs between communication and space, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.217-226, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73028]
	14	N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits, fourier transform and learnability. In 30 th Annual Symposium on Foundations of Computer Science, Reseach Triangle Park, NC, pages 574-579, October 1989.
	15	N. Nisan. Pseudorandom generators for spacebounded computation, manuscript, 1989.
	16	A. Siegal. On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications. In 30 th Annual Symposium on Foundations of Computer Science, Reseach Triangle Park, NC, pages 20-25, October 1989.
	17	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]
	18	Clark David Thompson, A complexity theory for vlsi, 1980
	19	Prasoon Tiwari, The communication complexity of distributed computing and a parallel algorithm for polynomial roots, 1986
	20	M. Tompa. Time-space tradeoffs for computing functions, using connectivity properties of their circuits. Journal of Comput. Syst. and Sci., 20:118-132, 1980.
	21	Andrew C. Yao, The entropic limitations on VLSI computations(Extended Abstract), Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.308-311, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802483]
	22	Y. Yesha. A time-space tradeoff for matrix multiplication and the discrete fourier transform on a general sequential random access computer. J. Comp. and Syst. Sci., 29:183-197, 1984.

CITED BY 12

	Nathan Linial , Yishay Mansour , Noam Nisan, Constant depth circuits, Fourier transform, and learnability, Journal of the ACM (JACM), v.40 n.3, p.607-620, July 1993
	Yishay Mansour , Noam Nisan , Uzi Vishkin, Trade-offs between communication throughput and parallel time, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.372-381, May 23-25, 1994, Montreal, Quebec, Canada
	Tim J. Harris, A survey of PRAM simulation techniques, ACM Computing Surveys (CSUR), v.26 n.2, p.187-206, June 1994
	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
	Jens-Peter Kaps , Kaan Yuksel , Berk Sunar, Energy Scalable Universal Hashing, IEEE Transactions on Computers, v.54 n.12, p.1484-1495, December 2005
	Noam Nisan , Avi Widgerson, Rounds in communication complexity revisited, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.419-429, May 05-08, 1991, New Orleans, Louisiana, United States
	André Gronemeier, A note on the decoding complexity of error-correcting codes, Information Processing Letters, v.100 n.3, p.116-119, 15 November 2006
	Yin Hu , Ghaith Hammouri , Berk Sunar, A fast real-time memory authentication protocol, Proceedings of the 3rd ACM workshop on Scalable trusted computing, October 31-31, 2008, Alexandria, Virginia, USA
	L. H. Nguyen , A. W. Roscoe, Authenticating ad hoc networks by comparison of short digests, Information and Computation, v.206 n.2-4, p.250-271, February, 2008
	Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Cryptography with constant computational overhead, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Colin Boyd , Yvonne Cliff , Juan M. Gonzalez Nieto , Kenneth G. Paterson, One-round key exchange in the standard model, International Journal of Applied Cryptography, v.1 n.3, p.181-199, February 2009
	Alexander D. Healy, Randomness-Efficient Sampling within NC1, Computational Complexity, v.17 n.1, p.3-37, April 2008