Name
Abstract | ||
|---|---|---|
Summary form only given. Any implementation of Carter-Wegman universal hashing from n-b strings to m-b strings requires a time-space tradeoff of TS=Ω(nm). 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 AT2 bound for VLSI implementation; Ω(log n) parallel time bound on a CREW PRAM; and exponential size for constant depth circuits. The results on VLSI implementation are proved using information transfer bounds derived from the definition of a universal family of hash functions |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1016/0304-3975(93)90257-T | Theor. Comput. Sci. |
Keywords | Field | DocType |
computational complexity,vlsi,very large scale integration,model of computation,branching program,computational modeling,circuits,lower bound,hash functions,hash function,information transfer,computer science | Discrete mathematics,Combinatorics,Universal hashing,Binary decision diagram,Quadratic equation,Model of computation,Hash function,K-independent hashing,Mathematics,Dynamic perfect hashing,Computational complexity theory | Journal |
Volume | Issue | ISSN |
107 | 1 | Theoretical Computer Science |
ISBN | Citations | PageRank |
0-89791-361-2 | 95 | 15.29 |
References | Authors | |
17 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yishay Mansour | 1 | 6211 | 745.95 |
| Noam Nisan | 2 | 8170 | 809.08 |
| Prasoon Tiwari | 3 | 592 | 96.81 |