2026/07/22 by Canran Wang
#cs.IT #math.IT
Break-resilient codes protect a word against an omniscient adversary who breaks it at arbitrary boundaries between adjacent symbols. For binary codewords of length~n subject to at most~t breaks, the best known explicit construction for this model has redundancy~O(tlog nlogloglog n), whereas the information-theoretic lower bound is~Ω(tlog (n/t)). In this paper, we close this gap by presenting a break-resilient code with redundancy~O(tlog n) when~t≤ n1-ε for a fixed ε∈(0,1), matching the information-theoretic lower bound up to a constant factor. The key idea is to compute a short algebraic fingerprint of the message, which enables the decoder to reject incorrect assemblies of the received fragments.