We consider the size of circuits which perfectly hash
an arbitrary subset $S\!\subset\!\bitset^n$ of cardinality $2^k$
into $\bitset^m$.
We observe that, in general, the size of such circuits is
exponential in $2k-m$,
and provide a matching upper bound.
We consider the size of circuits which perfectly hash
an arbitrary subset $S\!\subset\!\bitset^n$ of cardinality $2^k$
into $\bitset^m$.
We observe that, in general, the size of such circuits is
exponential in $2k-m$,
and provide a matching upper bound.
In TR96-041, Goldreich and Wigderson show their
upper bounds on perfect hashing circuits to be optimal, but
only up to a polynomial in n. In a recent paper, available as
<http://www.brics.dk/~bromille/Papers/err.ps>,
we look more closely at the dependence upon n and provide an
improved construction.
We found out that, in contrast to our previous impression, the lower bound has been known.
In fact, our lower bound argument is analogous to the one presented in pages 128-129 of Mehlhorn's book,{\em Data Structures and Algorithms} (Vol.~1), EATCS Monographs on Theoretical Computer Science, 1984.
