Oblivious Deletion Codes

Roni Con, Ray Li · 2025

Read Oblivious Deletion Codes by Roni Con, Ray Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-18878.txt.

Description

Roni Con and Ray Li construct error-correcting codes for a middle kind of noise, where symbols are deleted but the damage is not aimed at the code. In this oblivious model, the errors are hostile in effect yet blind to the random choices made while encoding. DNA storage motivates the setting, since its noise comes from hard-to-model physical processes rather than an attacker.

Their first construction matches the best known redundancy bound for fully hostile deletions. They then show that any good list-decodable code can be turned into an oblivious deletion code with nearly the same cost. A randomized version does better still, and the same idea improves codes built for hostile deletions too. The shared trick shrinks the hash by working modulo a prime picked from a small set, with the prime itself tucked into the encoding.

Catalog record

CREATORRoni Con, Ray Li
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-18878

Browse the full library · About the Tower of Babel