Better bounds for perfect hashing into a 4-element set
April 26, 2017

What is the largest size of a universe that can be perfectly hashed into a k-element set? Equivalently, how large can a subset C of {1,2,…,k}^n be such that every k distinct elements of C have a coordinate where they all differ? We prove an improved upper bound on the size of such sets for k=4. Specifically, we prove such a subset of {1,2,3,4}^n has size at most 2^{6n/19+o(n)}, or rate at most 6/19 < 0.3158 measured in bits. This improves the previous best upper bound of 0.3512 due to (Arikan 1994), which in turn improved the 0.375 bound that followed from general bounds for perfect hashing due to (Fredman and Komlós, 1984) and (Körner and Marton, 1988). This question has another context besides hashing, namely the zero-error list decoding capacity of certain channels.

Our approach is based on a delicate probabilistic combination of the Plotkin bound in coding theory and Hansel's lemma for covering the complete graph by bipartite graphs. For the case k=3, whether one can improve the easy (3/2)^n upper bound remains a notable challenge in the area.

The talk should be self-contained and not require any particular background.

Joint work with Marco Dalai and Jaikumar Radhakrishnan.