Sofya Raskhodnikova
Erasure-Resilience vs. Tolerance to Errors

Abstract: We provide a separation between erasure-resilient and
tolerant property testing. Specifically, we exhibit a property which
is testable (with the number of queries independent of the length of
the input) in the presence of adversarial erasures, but is not
testable tolerantly. To achieve this, we use codes locally list
decodable in the presence of a constant fraction of erasures,
arbitrary close to 1. To the best of our knowledge, local list
erasure-decoders have not been considered previously.

(Based on joint work with Nithin M. Varma)