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.

Comment on TR96-041. Comment on: TR96-041

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.