On the Connections Between Universal Hashing, Combinatorial Designs and Error-Correcting Codes
Douglas R. Stinson · 1995
In this primarily expository paper, we discuss the connections between two popular and useful tools in theoretical computer science, namely, universal hashing and pairwise independent random variables; and classical combinatorial stuctures such as error-correcting codes, balanced incomplete block designs, difference matrices and orthogonal arrays. 1 Introduction The concept known as "universal hashing" was invented by Carter and Wegman [5] in 1979. In [29, p. 18], Avi Wigderson characterizes universal hashing as being a tool which "should belong to the fundamental bag of tricks of every computer scientist". This is no exaggeration, as there are probably well in excess of fifty papers in theoretical computer science that employ universal hashing as an important tool. Several of the most attractive applications are outlined in the the lecture notes [29]. A closely related topic goes by several names: "strongly universal hashing " [27], "two-point based sampling" [6], and "pairwise indep...