Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
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. -
null ; null ; null ; null ; null ; null (Ed.)