Srinivasan, Srikanth ;
Sudan, Madhu
Local Decoding and Testing of Polynomials over Grids
Abstract
The wellknown DeMilloLiptonSchwartzZippel lemma says that nvariate polynomials of total degree at most d over grids, i.e. sets of the form A_1 \times A_2 \times \cdots \times A_n, form errorcorrecting codes (of distance at least 2^{d} provided \min_i\{A_i\}\geq 2). In this work we explore their local decodability and local testability. While these aspects have been studied extensively when A_1 = \cdots = A_n = \F_q are the same finite field, the setting when A_i's are not the full field does not seem to have been explored before.
In this work we focus on the case A_i = {0,1} for every i. We show that for every field (finite or otherwise) there is a test whose query complexity depends only on the degree (and not on the number of variables). In contrast we show that decodability is possible over fields of positive characteristic (with query complexity growing with the degree of the polynomial and the characteristic), but not over the reals, where the query complexity must grow with $n$. As a consequence we get a natural example of a code (one with a transitive group of symmetries) that is locally testable but not locally decodable.
Classical results on local decoding and testing of polynomials have relied on the 2transitive symmetries of the space of lowdegree polynomials (under affine transformations). Grids do not possess this symmetry: So we introduce some new techniques to overcome this handicap and in particular use the hypercontractivity of the (constant weight) noise operator on the Hamming cube.
BibTeX  Entry
@InProceedings{srinivasan_et_al:LIPIcs:2018:8329,
author = {Srikanth Srinivasan and Madhu Sudan},
title = {{Local Decoding and Testing of Polynomials over Grids}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {26:126:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770606},
ISSN = {18688969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8329},
URN = {urn:nbn:de:0030drops83294},
doi = {10.4230/LIPIcs.ITCS.2018.26},
annote = {Keywords: Property testing, Coding theory, Lowdegree testing, Local decoding, Local testing}
}
12.01.2018
Keywords: 

Property testing, Coding theory, Lowdegree testing, Local decoding, Local testing 
Seminar: 

9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Issue date: 

2018 
Date of publication: 

12.01.2018 