A Construction Method for Optimally Universal Hash Families and its Consequences for the Existence of RBIBDs

Abstract. We introduce a method for constructing optimally universal hash families and equivalently RBIBDs. As a consequence of our construction we obtain minimal optimally universal hash families, if the cardinalities of the universe and the range are powers of the same prime. A corollary of this result is that the necessary condition for the existence of an RBIBD with parameters (v,k,lambda), namely

v mod k = lambda(v-1) mod (k-1) = 0,

is sufficient, if v and k are powers of the same prime. As an application of our construction, we show that the k-MAXCUT algorithm of Hofmeister and Lefmann (1996) can be implemented such that it has a polynomial running time, in the case that the number of vertices and k are powers of the same prime.

Notes

• Appeared in
  Theoretical Computer Science, Volume 363, Number 1, pp. 76-84, 2006.
  ( electronic edition available via ScienceDirect).
  


• Extended Abstract appeared in
  Computing and Combinatorics: 10th Annual International Conference (COCOON),
  Lecture Notes in Computer Science 3106, Springer, pp. 23-32, 2004

• Extended abstract: pdf, postscript (© Springer)

• Preliminary long version: pdf, postscript