Speaker: Nithin Varma
Affiliation: Boston University

Title: Separating erasures and errors in property testing using local list decoding

Abstract:
Corruption in data can be in the form of erasures (missing data) or errors (wrong data). Erasure-resilient property testing (Dixit, Raskhodnikova, Thakurta, Varma ’16) and tolerant property testing (Parnas, Ron, Rubinfeld ’06) are two formal models of sublinear algorithms that account for the presence of erasures and errors in input data, respectively.

We first show that there exists a property P that has an erasure-resilient tester whose query complexity is independent of the input size n, whereas every tolerant tester for P has query complexity that depends on n. We obtain this result by designing a local list decoder for the Hadamard code that works in the presence of erasures, thereby proving an analog of the famous Goldreich-Levin Theorem. We also show a strengthened separation by proving that there exists another property R such that R has a constant-query erasure-resilient tester, whereas every tolerant tester for R requires n^{Omega(1)} queries. The main tool used in proving the strengthened separation is an approximate variant of a locally list decodable code that works against erasures.

Joint work with Sofya Raskhodnikova and Noga Ron-Zewi.