pipette
ESEspañol

Beating the Probabilistic Bound for Hashing and Improving Lower Bounds for Trifferent Codes

Chen Yuan, Ruiqi Zhu

Preprint

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