Local decoding and testing of polynomials over grids
Mitali Bafna, Srikanth Srinivasan, Madhu Sudan · Random Structures and Algorithms · 2020
We study the local decodability and (tolerant) local testability of low‐degree n‐variate polynomials over arbitrary fields, evaluated over the domain {0,1}n. We show that for every field there is a tolerant local test whose query complexity depends only on the degree. In contrast we show that decodability is possible over fields of positive characteristic, but not over the reals.