Local decoding and testing of polynomials over grids

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.

Locations

• arXiv (Cornell University) - View - PDF
• Leibniz-Zentrum für Informatik (Schloss Dagstuhl) - View - PDF
• Random Structures and Algorithms - View