Abstract
We study the question of local testability of low (constant) degree functions from a product domain ?_1 × … × ?_n to a field ?, where ?_i ⊆ ? can be arbitrary constant sized sets. We show that this family is locally testable when the grid is "symmetric". That is, if ?_i = ? for all i, there is a probabilistic algorithm using constantly many queries that distinguishes whether f has a polynomial representation of degree at most d or is Ω(1)far from having this property. In contrast, we show that there exist asymmetric grids with ?_1 = ⋯ = ?_n = 3 for which testing requires ω_n(1) queries, thereby establishing that even in the context of polynomials, local testing depends on the structure of the domain and not just the distance of the underlying code.
The lowdegree testing problem has been studied extensively over the years and a wide variety of tools have been applied to propose and analyze tests. Our work introduces yet another new connection in this rich field, by building lowdegree tests out of tests for "juntadegrees". A function f:?_1 × ⋯ × ?_n → ?, for an abelian group ? is said to be a juntadegreed function if it is a sum of djuntas. We derive our lowdegree test by giving a new local test for juntadegreed functions. For the analysis of our tests, we deduce a smallset expansion theorem for spherical/hamming noise over large grids, which may be of independent interest.
BibTeX  Entry
@InProceedings{amireddy_et_al:LIPIcs.APPROX/RANDOM.2023.41,
author = {Amireddy, Prashanth and Srinivasan, Srikanth and Sudan, Madhu},
title = {{LowDegree Testing over Grids}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
pages = {41:141:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772969},
ISSN = {18688969},
year = {2023},
volume = {275},
editor = {Megow, Nicole and Smith, Adam},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18866},
URN = {urn:nbn:de:0030drops188665},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.41},
annote = {Keywords: Property testing, Lowdegree testing, Smallset expansion, Local testing}
}
Keywords: 

Property testing, Lowdegree testing, Smallset expansion, Local testing 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) 
Issue Date: 

2023 
Date of publication: 

04.09.2023 