DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.14

Testing Sparse Functions over the Reals

Authors: Vipul Arora, Arnab Bhattacharyya, Philips George John, and Sayantan Sen

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

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.

Cite as

Vipul Arora, Arnab Bhattacharyya, Philips George John, and Sayantan Sen. Testing Sparse Functions over the Reals. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 14:1-14:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{arora_et_al:LIPIcs.ICALP.2026.14,
  author =	{Arora, Vipul and Bhattacharyya, Arnab and George John, Philips and Sen, Sayantan},
  title =	{{Testing Sparse Functions over the Reals}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{14:1--14:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.14},
  URN =		{urn:nbn:de:0030-drops-264038},
  doi =		{10.4230/LIPIcs.ICALP.2026.14},
  annote =	{Keywords: Property testing, sparsity, linearity, low-degree polynomials, juntas, computation over reals}
}

Search Results

Documents authored by George John, Philips

Testing Sparse Functions over the Reals

Abstract

Cite as

Thanks for your feedback!

Could not send message