The computational complexity of universal hashing
Yishay Mansour, Noam Nisan, P. Tiwari · 1990
Any implementation of Carter-Wegman universal hashing from n-bit strings to m-bit strings requires a time-space tradeoff of TS = f~(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 AT 2 bound for VLSI implementation; f~(log n) parallel time bound on a CREW PRAM; and exponential size for constant depth circuits.