The computational complexity of universal hashing. (English) Zbl 0764.68080
Summary: Any implementation of Carter-Wegman universal hashing from \(n\)-bit strings to \(m\)-bit strings requires a time-space tradeoff of \(TS=\Omega(nm)\). J. L. Carter and M. N. Wegman, J. Comput. Syst. Sci. 18, 143-154 (1979; Zbl 0412.68090)]. The bound holds in the general boolean branching program model and, thus, in essentially any model of computation. As a corollary, computing \(a+b*c\) in any field \(F\) requires a quadratic time-space tradeoff, and the bound holds for any representation of the elements of the field.
Other lower bounds on the complexity of any implementation of universal hashing are given as well: quadratic \(AT^ 2\) bounds for VLSI implementation; \(\Omega(\log n)\) parallel time bound on a CREW PRAM; and exponential size for constant-depth circuits.
Other lower bounds on the complexity of any implementation of universal hashing are given as well: quadratic \(AT^ 2\) bounds for VLSI implementation; \(\Omega(\log n)\) parallel time bound on a CREW PRAM; and exponential size for constant-depth circuits.
Keywords:
universal family of hash functionsCitations:
Zbl 0412.68090References:
| [1] | Abrahamson, K., Time-space tradeoffs for branching programs constructed with those straight line programs, (27th Ann. Symp. on Foundations of Computer Science (1986)), 402-409, Toronto, Ontario |
| [2] | Babai, L.; Frankl, P.; Simon, J., Complexity classes in communication complexity theory, (Proc. 27th Ann. Symp. on Foundations of Computer Science (1986)), 337-347 |
| [3] | Beame, P., A general sequential time space tradeoff for finding unique elements, (Proc. 21st Ann. ACM Symp. on Theory of Computing (1989)), 197-203, Seattle, Washington |
| [4] | P. Beame, M. Tompa and P. Yan, Communication-space tradeoffs in the boolean model (manuscript).; P. Beame, M. Tompa and P. Yan, Communication-space tradeoffs in the boolean model (manuscript). · Zbl 0809.68078 |
| [5] | Boppana, R.; Sipser, M., The complexity of finite functions, (van Leeuwen, J., Handbook of Theoretical Computer Science, Vol. A (1990), Elsevier: Elsevier Amsterdam), 757-804 · Zbl 0900.68268 |
| [6] | Borodin, A.; Cook, S., A time-space tradeoff for sorting on a general sequential model of computation, SIAM J. Comput., 1, 287-297 (1982) · Zbl 0478.68061 |
| [7] | Borodin, A.; Cook, S.; Pippenger, N., Parallel computation for well-endowed rings and space-bounded probabilistic machines, Inform. and Control, 58, 113-136 (1983) · Zbl 0598.68043 |
| [8] | Borodin, A.; Fischer, M.; Kirkpatrik, D.; Lynch, N.; Tompa, M., A time-space tradeoff for sorting on non-oblivious machines, J. Comput. System Sci., 22, 351-364 (1981) · Zbl 0462.68011 |
| [9] | Carter, L.; Wegman, M., Universal hash functions, J. Comput. System. Sci., 18, 143-154 (1979) · Zbl 0412.68090 |
| [10] | Cobham, A., The recognition problem for the set of perfect squares, conference record, (Proc. IEEE 7th Ann. Symp. on Switching and Automata Theory (1966)), 78-87 |
| [11] | Cook, S.; Dwork, C.; Reischuk, R., Upper and lower bounds for parallel random access machines without simultaneous writes, SIAM J. Comput., 15, 87-97 (1986) · Zbl 0591.68049 |
| [12] | Erdös, P.; Spencer, J., Probabilistic Methods in Combinatorics (1974), Academic Press · Zbl 0308.05001 |
| [13] | Goldwasser, S.; Sipser, M., Private coins versus public coins in interactive proof systems, (Proc. 18th Ann. ACM Symp. on Theory of Computing (1986)), 59-68, Berkeley, CA |
| [14] | Impagliazzo, R.; Zuckerman, D., How to recycle random bits, (Proc. 30th Ann. Symp. on Foundations of Computer Science (1989)), 248-253, Reseach Triangle Park, NC |
| [15] | Krapchenko, V., A method of determining lower bounds for the complexity of π schemes, Math. Notes Acad. Sci. USSR, 10, 1, 474-479 (1971) · Zbl 0231.68023 |
| [16] | Lam, T.; Tiwari, P.; Tompa, M., Tradeoffs between communication and space, (Proc. 21st Ann. ACM Symp. on Theory of Computing (1989)), 217-226, (To appear in JCSS) |
| [17] | Linial, N.; Mansour, Y.; Nisan, N., Constant depth circuits, fourier transform and learnability, (Proc. 30th Ann. Symp. on Foundations of Computer Science (1989)), 574-579, Reseach Triangle Park, NC |
| [18] | Nisan, N., Pseudorandom generators for space-bounded computation, (Proc. 22nd Ann. ACM Symp. on Theory of Computing (1990)), 204-212, Baltimore, MD |
| [19] | Siegel, A., On universal classes of fast high performance hash functions, their time-space tradeoff, and their application, (Proc. 30th Ann. Symp. on Foundations of Computer Science (1989)), 20-25, Reseach Triangle Park, NC |
| [20] | Sipser, M., A complexity theoretic approach to randomness, (Proc. 15th Ann. ACM Symp. on Theory of Computing (1983)), 330-335, Boston, MA |
| [21] | Ph.D. thesis, Department of Computer Science.; Ph.D. thesis, Department of Computer Science. |
| [22] | Tiwari, P., The communication complexity of distributed computing and a parallel algorithm for polynomial roots, (Ph.D. thesis (1986), University of Illinois: University of Illinois Urbana-Champaign) |
| [23] | Tompa, M., Time-space tradeoffs for computing functions, using connectivity properties of their circuits, J. Comput. System Sci., 20, 118-132 (1980) · Zbl 0435.68034 |
| [24] | Yao, A. C., The entropic limitations on VLSI computations, (Proc. 13th Ann. ACM Symp. on Theory of Computing (1981)), 308-311, Milwaukee, WI |
| [25] | Yesha, Y., A time-space tradeoff for matrix multiplication and the discrete fourier transform on a general sequential random access computer, J. Comput. System Sci., 29, 183-197 (1984) · Zbl 0577.68060 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
