Local decoding and testing of polynomials over grids. Issue 3 (27th June 2020)

• Record Type: Journal Article
• Authors: Bafna, Mitali; Srinivasan, Srikanth; Sudan, Madhu
• Is Part Of: Random structures & algorithms. Volume 57:Issue 3(2020)
• Page Start: 658
• Page End: 694
• Publication Date: 2020-06-27
• Subjects: coding theory -- local decoding -- local testing -- low‐degree testing -- property testing; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20933
• Languages: English
• ISSNs: 1042-9832

Abstract

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.