Summer 2019

From local to robust testing via high-dimensional expansion

Tuesday, Jul. 23, 2019 10:00 am10:45 am PDT

Add to Calendar


Noga Ron Zewi


Room 116

A local tester for an error-correcting code is a probabilistic procedure that queries a small subset of coordinates, accepts codewords with probability one, and rejects non-codewords with probability proportional to their distance from the code. The local tester is said to be robust if for non-codewords it satisfies the stronger property that the average distance of local views from accepting views is proportional to the distance from the code. We show that for certain codes, satisfying certain high-dimensional expansion properties, any (natural) local tester can be converted to a robust tester with roughly the same number of queries.