Authors
Frederick Dehmel, Shilun Li
Description
We study public-key pseudorandom codes over fixed alphabets against adversarial deletions, where the deletion channel may depend on both the public encoding key and the transmitted codeword. Using longest common subsequences, we prove an upper bound on the deletion fraction that multi-message codes with a single-output decoder can tolerate. For binary codes, this rules out robustness against every such channel deleting more than 20.7334008% of the codeword. We also extend the argument to constant-size list decoding. These bounds apply to public-key-dependent adversarial channels; they do not apply to oblivious edit channels.