Events
Summer 2019
From local to robust testing via high-dimensional expansion
Tuesday, July 23rd, 2019, 10:00 am–10:45 am
Speaker:
Noga Ron Zewi
Location:
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.