The zero-rate threshold for adversarial bit-deletions is less than 1/2.

Venkatesan Guruswami, Xiaoyu He, Ray Li

Browse the full FOCS paper archive.