Random Reed--Solomon Codes Correcting Permutations, Insertions, and Deletions over Polynomial-Size Alphabets (opens in new tab)

We study Reed--Solomon codes against adversarial coordinate permutations followed by insertion-deletion (insdel) errors. It was previously shown by Con (2025) that Reed--Solomon codes can attain the exact half-Singleton bound in this setting, but only over exponentially large alphabets. We prove that, by allowing an additive $\epsilon n$ gap from this bound, the alphabet size can be reduced to polynomial. More precisely, for fixed constants $R,\...