zbMATH — the first resource for mathematics

New bounds for perfect hashing via information theory. (English) Zbl 0676.68007
Körner and Marton consider the problem of finding bounds for the largest size of a k-separated subset for a family of perfect hash- functions. By extending an information theoretic bounding technique based on graph entropy to more general structures they are able to improve the Fredman-Komlòs [M. Fredman and J. Komlòs, On the size of separating systems and perfect hash functions, SIAM J. Algebraic Discrete Methods 5, 61-68 (1984; Zbl 0525.68037) bounds in several cases: They give a new lower bound for the size of a 3-separated subset on a 3- element alphabet, namely \[ 1/t\quad \log N(t,3,3)\gtrsim 1/4 \log 9/5 \] and they present better bounds for a subclass of problems which includes a 3-separated subset on a 3-element alphabet as a special case. For all k-separated subsets on k-element alphabets with \(k>3\) they could not improve the Fredman-Komlòs bounds.
Reviewer: W.Janko

68P05 Data structures
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Fredman, M.; Komlos, J., On the size of separating systems and perfect hash functions, SIAM J. algebraic discr. meth, 5, 61-68, (1984) · Zbl 0525.68037
[2] Körner, J., Fredman-komlos bounds and information theory, SIAM J. algebraic discr. meth, 7, 560-570, (1986) · Zbl 0603.05034
[3] Körner, J., Coding of an information source having ambiguous alphabet and the entropy of graphs, (), 411-425 · Zbl 0298.94022
[4] Csiszar, I.; Körner, J., ()
[5] McEliece, R., ()
[6] Conway, J.H.; Sloane, N.J.A., Lexicographic codesxxx error correcting codes from game theory, (), 337-348 · Zbl 0594.94023
[7] Hardy, G.H.; Littlewood, J.E.; Polya, G., ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.