Local decoding and testing of polynomials over grids. Issue 3 (27th June 2020) - Bafna, Mitali; Srinivasan, Srikanth; Sudan, Madhu
Abstract : 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.