New bounds for perfect hashing via information theory
type: Item
instance of: scholarly article
title: New bounds for perfect hashing via information theory
zbMATH Open document ID: 0676.68007
DOI: 10.1016/S0195-6698(88)80048-9
author: S. H. Smith
published in: European Journal of Combinatorics
publication date: 1988-01-01T00:00:00Z
review text: 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 [\textit{M. Fredman} and \textit{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.
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4108143
zbMATH Keywords: perfect hashing
zbMATH Keywords: information theory
MaRDI profile type: Publication
cites work: On the Size of Separating Systems and Families of Perfect Hash Functions
cites work: Fredman–Komlós bounds and information theory
cites work: Q4053473
cites work: Q4156696
cites work: Lexicographic codes: Error-correcting codes from game theory
full work available at URL: s0195-6698(88)80048-9
OpenAlex ID: W2056884477
description: scientific article; zbMATH DE number 4108143