← 研踪 PaperTrailarXiv:2611.11262 · v1
Beating the Probabilistic Bound for Hashing and Improving Lower Bounds for Trifferent Codes
首次提交 2026-11-08 17:29
版本更新 2026-11-08 17:29
雷达观测 2026-11-10 12:16
摘要
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.
作者备注：22 pages
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-08 17:29 · 最新观测版本
Beating the Probabilistic Bound for Hashing and Improving Lower Bounds for Trifferent Codes
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.
查看此版本解读 →查看此版本原文 ↗