Beating the Probabilistic Bound for Hashing and Improving Lower Bounds for Trifferent Codes
In the authors' words
We improve the probabilistic lower bounds on the rates of hash codes and list-recoverable codes. For perfect -hashing, we prove for every . Our main result concerns non-perfect hashing. For every , we prove In particular, the case , combined with the Tetra code, strictly improves the K\"orner-Marton lower bound for trifferent codes. We also extend the method to -list recovery. For every and , we prove . For every fixed , the rate improvement is bounded below by a positive constant independent of . The same holds for every fixed when is sufficiently large.
Main resultThe abstract does not state a limitation.
Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 22 pages