New bounds improve rates of hashing and trifferent codes
Beating the Probabilistic Bound for Hashing and Improving Lower Bounds for Trifferent Codes
Information Theory
Summary
Hash codes and list-recoverable codes help computers organize and retrieve data efficiently. This paper shows improved results that beat previous probabilistic limits on how well these codes can perform. It also advances understanding of trifferent codes, a special kind of code useful for unique data encoding. The improvements hold true for various code sizes and recovery parameters, indicating stronger coding strategies are possible.
What this means in practice
- •For data storage engineers: Improve error-resilient data encoding schemes by using enhanced hash code rates for better storage efficiency and reliability.
- •For communication system designers: Design communication protocols with stronger codes that correct more errors using improved list-recoverable coding rate bounds.
A theory result. No direct application yet.
Authors
Chen Yuan, Ruiqi Zhu
Abstract
We improve the probabilistic lower bounds on the rates of hash codes and list-recoverable codes. For perfect $q$-hashing, we prove $R_q>B_q$ for every $q\geq 3$. Our main result concerns non-perfect hashing. For every $q\geq 4$, we prove $R_{q,3}>B_{q,3}+\frac{1}{250000}.$ In particular, the case $q=9$, combined with the Tetra code, strictly improves the Körner-Marton lower bound $R_3\geq \frac14\log(9/5)$ for trifferent codes. We also extend the method to $(p,2,3)$-list recovery. For every $q\geq 4$ and $0\leq p<\frac{q-2}{12(q-1)}$, we prove $R_q^{\mathrm{LR}}(p)>B_q^{\mathrm{LR}}(p)$. For every fixed $0\leq p<1/18$, the rate improvement is bounded below by a positive constant independent of $q\geq 4$. The same holds for every fixed $0\le p<1/12$ when $q$ is sufficiently large.