2026-07-23T17:32:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18866 2024-03-06T11:02:47Z ddc:004 open_access

Low-Degree Testing over Grids Amireddy, Prashanth Srinivasan, Srikanth Sudan, Madhu Property testing Low-degree testing Small-set expansion Local testing 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 low-degree 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 low-degree tests out of tests for "junta-degrees". A function f:𝒮_1 × ⋯ × 𝒮_n → 𝒢, for an abelian group 𝒢 is said to be a junta-degree-d function if it is a sum of d-juntas. We derive our low-degree test by giving a new local test for junta-degree-d functions. For the analysis of our tests, we deduce a small-set expansion theorem for spherical/hamming noise over large grids, which may be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prashanth Amireddy and Srikanth Srinivasan and Madhu Sudan 2023 Is Part Of LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2023.41 urn:nbn:de:0030-drops-188665 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.41 eng https://creativecommons.org/licenses/by/4.0/legalcode