ECCC-Report TR96-041https://eccc.weizmann.ac.il/report/1996/041Comments and Revisions published for TR96-041en-usSat, 18 Jun 2016 14:43:17 +0300
Comment 2
| the lower bound was known |
Oded Goldreich
https://eccc.weizmann.ac.il/report/1996/041#comment2We 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.Sat, 18 Jun 2016 14:43:17 +0300https://eccc.weizmann.ac.il/report/1996/041#comment2
Revision 1
| On the Circuit Complexity of Perfect Hashing Revision of: TR96-041 |
Oded Goldreich,
Avi Wigderson
https://eccc.weizmann.ac.il/report/1996/041#revision1We 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.
Tue, 03 Mar 1998 00:00:00 +0200https://eccc.weizmann.ac.il/report/1996/041#revision1
Comment 1
| Comment on TR96-041. Comment on: TR96-041 |
Peter Bro Miltersen
https://eccc.weizmann.ac.il/report/1996/041#comment1In 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.
Fri, 27 Jun 1997 15:04:42 +0300https://eccc.weizmann.ac.il/report/1996/041#comment1
Paper TR96-041
| On the Circuit Complexity of Perfect Hashing |
Oded Goldreich,
Avi Wigderson
https://eccc.weizmann.ac.il/report/1996/041We 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.
Thu, 25 Jul 1996 09:24:51 +0300https://eccc.weizmann.ac.il/report/1996/041