2026-07-21T00:57:02Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:26403 2026-07-01T07:16:09Z ddc:004 open_access
Testing Sparse Functions over the Reals Arora, Vipul Bhattacharyya, Arnab George John, Philips Sen, Sayantan Property testing sparsity linearity low-degree polynomials juntas computation over reals Over the last three decades, function testing has been extensively studied over Boolean, finite fields, and discrete settings. However, to encode the real-world applications more succinctly, function testing over the reals (where the domain and range, both are reals) is of prime importance. Recently, there have been some works in the direction of testing for algebraic representations of such functions: the work by Fleming and Yoshida (ITCS 20), Arora, Kelman, and Meir (SOSA 25) on linearity testing and the work of Arora, Bhattacharyya, Fleming, Kelman, and Yoshida (SODA 23) for testing low-degree polynomials. Our work follows the same avenue, wherein we study three well-studied sparse representations of functions, over the reals, namely (i) k-linearity, (ii) k-sparse, low-degree polynomials, and (iii) k-juntas. In this setting, given approximate query access to some f:ℝⁿ β†’ ℝ, we want to decide if the function satisfies some property of interest, or if it is far from all functions that satisfy the property. Here, the distance is measured in the 𝓁₁-metric, under the assumption that we are drawing samples from the Standard Gaussian distribution. We present efficient testers and Ξ©(k) lower bounds for testing each of these three properties. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Vipul Arora and Arnab Bhattacharyya and Philips George John and Sayantan Sen 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.14 urn:nbn:de:0030-drops-264038 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.14 eng https://creativecommons.org/licenses/by/4.0/legalcode