Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR96-041 | 3rd March 1998 00:00

#### On the Circuit Complexity of Perfect Hashing Revision of: TR96-041

Revision #1
Authors: Oded Goldreich, Avi Wigderson
Accepted on: 3rd March 1998 00:00
Keywords:

Abstract:

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.

### Paper:

TR96-041 | 24th July 1996 00:00

#### On the Circuit Complexity of Perfect Hashing

TR96-041
Authors: Oded Goldreich, Avi Wigderson
Publication: 25th July 1996 09:24
Keywords:

Abstract:

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(s):

Comment #1 to TR96-041 | 27th June 1997 15:04

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

Comment #1
Authors: Peter Bro Miltersen
Accepted on: 27th June 1997 15:04
Keywords:

Abstract:

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.

Comment #2 to TR96-041 | 18th June 2016 14:43

#### the lower bound was known

Authors: Oded Goldreich
Accepted on: 18th June 2016 14:43
Keywords:

Comment:

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.

ISSN 1433-8092 | Imprint