pipette
ENEnglish

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

Chen Yuan, Ruiqi Zhu

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 22 pages