Testing Sparse Functions over the Reals

Arora, Vipul; Bhattacharyya, Arnab; George John, Philips; Sen, Sayantan

doi:10.4230/LIPIcs.ICALP.2026.14

Testing Sparse Functions over the Reals

Vipul Arora

School of Computing, National University of Singapore, Singapore Arnab Bhattacharyya

University of Warwick, UK Philips George John

CQT & CNRS@CREATE, National University of Singapore, Singapore Sayantan Sen

Centre for Quantum Technologies, National University of Singapore, Singapore

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:\mathbb{R}^{n}\rightarrow\mathbb{R}$ , 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 $\ell_{1}$ -metric, under the assumption that we are drawing samples from the Standard Gaussian distribution. We present efficient testers and $\Omega(k)$ lower bounds for testing each of these three properties.

Keywords and phrases:

Property testing, sparsity, linearity, low-degree polynomials, juntas, computation over reals

Category:

Track A: Algorithms, Complexity and Games

Funding:

Vipul Arora: This work was done in part while the author was visiting the Simons Institute for the Theory of Computing.

Arnab Bhattacharyya: Research supported by a start-up grant at the University of Warwick.

Philips George John: Research supported by the NRF, Prime Minister’s Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme. This work was also done in part while supported by the CQT++ Core Research Funding Grant from Prof. Divesh Aggarwal.

Sayantan Sen: Research supported by the NRF Investigatorship award (NRF-NRFI10-2024-0006) and CQT Young Researcher Career Development Grant (25-YRCDG-SS).

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Streaming, sublinear and near linear time algorithms

Related Version:

Full version (with complete proofs): https://arxiv.org/abs/2603.28061 [6]

DOI:

10.4230/LIPIcs.ICALP.2026.14

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Property testing [24, 71, 48] is a rigorous framework for studying the global properties of large datasets by accessing only a few entries of it. In particular, given query access to an unknown “huge object”, the goal of property testing is to verify some property of the object by only inspecting a small portion of it. Formally, we can define property testing of functions, or function testing, by considering the “huge object” as a function $f$ over an underlying domain, which we can query at a small number of points in order to verify a property of the function $f$ in an approximate sense. For example, consider the problem of linearity testing of functions $f:\mathbb{F}^{n}\rightarrow\mathbb{F}$ , where $\mathbb{F}$ is a finite field. We are given access to a query oracle for $f$ ; i.e., on input $\bm{x}$ , the oracle returns $f(\bm{x})$ . The goal is to distinguish with high probability between two cases, viz. (i) $f$ is a linear function, or (ii) $f$ is “far” from all linear functions, while performing as few queries to the oracle as possible.

The field of property testing was initiated in the seminal work of [24, 25], who studied the problem of self-testing of programs, where the goal was to understand the correctness of a program by verifying its outputs on a set of correlated input data. A fundamental problem they studied is that of testing whether $f$ is linear (or generally, a homomorphism of abelian groups) or $\varepsilon$ -far from linearity, with the notion of $\varepsilon$ -farness of $f:\mathbb{F}^{n}\rightarrow\mathbb{F}$ from a function class $\mathcal{P}$ defined as: $\mathsf{dist}_{\mathsf{Unif}(\mathbb{F}^{n}),\ell_{0}}(f,\mathcal{P})=\inf_{g% \in\mathcal{P}}\Pr_{\bm{x}\sim\mathsf{Unif}(\mathbb{F}^{n})}[f({\bm{x}})\neq g% ({\bm{x}})]\geq\varepsilon$ , i.e., for any function $g$ that satisfies property $\mathcal{P}$ , $f$ disagrees with $g$ on at least an $\varepsilon$ -fraction of the inputs $\bm{x}$ (uniformly drawn from $\mathbb{F}^{n}$ ). In the context of linearity testing, $\mathcal{P}$ is the class of linear functions/homomorphisms (the $\ell_{0}$ -distance definition given above can be easily generalized in terms of function domain and range, input distribution etc). They showed a constant query (independent of $|\mathbb{F}|$ and $n$ ) linearity tester, known as the BLR tester.

Over the last three decades, property testing has been extensively studied in many settings, such as when the unknown object is a function, a graph, or a probability distribution, with many natural connections to real-world problems, e.g., in the context of probabilistically checkable proofs [3, 4, 67, 34], PAC learning [48], program checking [70, 71], approximation algorithms [48, 38] and many more.

In particular, starting from the very first work that initiated the field of property testing [24], over the last three decades, function property testing has been extensively studied in several settings, culminating in a wide array of tools and techniques. This includes settings where the function is defined over finite fields [1, 58, 57, 45, 14, 13, 51, 73], over hyper-grids [35, 21, 28, 9], etc. One may see the books [50, 15] and the surveys [41, 69, 68] for detailed references.

Our problem setting.

Suppose we are given query access to an unknown function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ , and our goal is to distinguish whether (i) $f$ satisfies some property $\mathcal{P}$ , or (ii) $f$ is $\varepsilon$ -far from all functions that satisfy $\mathcal{P}$ . We define the notion of $\varepsilon$ -farness over the reals in the following way: we fix a reference distribution $\mathcal{D}$ on $\mathbb{R}^{n}$ , and we say $f$ is $\varepsilon$ -far from $\mathcal{P}$ if the following holds¹¹1The notion of $\ell_{1}$ -distance is more appropriate for real-valued functions, rather than the commonly used Hamming ( $\ell_{0}$ ) distance, especially in the approximate query setting which we define later. For example, consider the case if $g=f+\varepsilon$ for some $\varepsilon>0$ , then $\mathsf{dist}_{\mathcal{D},\ell_{1}}(f,g)=\varepsilon$ , whereas $\mathsf{dist}_{\mathcal{D},\ell_{0}}(f,g)=1$ . : $\mathsf{dist}_{\mathcal{D},\ell_{1}}(f,\mathcal{P})\triangleq\inf_{g\in% \mathcal{P}}\left\{\mathop{\mathbb{E}}_{\bm{x}\sim\mathcal{D}}\,[|f(\bm{x})-g(% \bm{x})|]\right\}\geq\varepsilon$ .

Studying function testing over the reals often requires new techniques compared to testing on finite domains. A common reference distribution on $\mathbb{R}^{n}$ is the standard $n$ -dimensional Gaussian distribution $\mathcal{N}(\bm{0},I_{n})$ , which is approximately a uniform distribution on an $\ell_{2}$ -sphere of radius $\sqrt{n}$ . And the notion of exact queries (oracle giving $f(\bm{x})$ ) is not realistic over the reals, since one may require infinitely many bits to represent the exact function value. Although the problem of function testing over the reals has several practical motivations, there have been comparatively few works in this setting till now (compared to testing over finite domains) such as testing surface areas [64, 59], testing halfspaces [61, 62, 63], linear separators [8], high-dimensional convexity [29], linear $k$ -juntas [32] etc.

Interestingly, these works mostly focus on the setting when $f$ is Boolean valued, i.e., $f:\mathbb{R}^{n}\rightarrow\{\pm 1\}$ . The setting where the range of $f$ is real has also been studied, e.g., in the work of [12], wherein they test properties of functions, defined over finite hyper-grids, with respect to $L_{p}$ -distances. In [16], functions over the hypercube, i.e., $f:\{0,1\}^{n}\to\mathbb{R}$ are studied for monotonicity. Recently, [39, 40] studied $L^{p}$ testing of monotonicity of Lipschitz functions $f:[0,1]^{n}\to\mathbb{R}$ .

[44] studied the problem of linearity testing for real-valued real-domain functions in full generality, i.e., for functions $f:\mathbb{R}^{n}\to\mathbb{R}$ . Later, [5] studied the problem of testing low-degree polynomials in this regime, followed by the work of [7], which improved these results by achieving query-optimality with respect to the proximity parameter $\varepsilon$ . In this work, we expand the landscape of testing various fundamental notions of sparsity to the general $f:\mathbb{R}^{n}\to\mathbb{R}$ regime.

A recent work of [10] studies a problem similar to sparsity testing of low degree polynomials, in a sample-based access model. However, it assumes a promise that the unknown function $f:\mathbb{R}^{n}\to\mathbb{R}$ is a multi-linear polynomial to begin with, and needs a large gap for the sparsity parameter between the YES and NO cases.

When the function $f$ to be tested is real valued, two different models can be considered with respect to the query accuracy. In the first model, known as the arbitrary precision arithmetic or the exact testing model, we assume that the oracle representing $f$ can give the exact value of $f$ at any point of query ${\bm{x}}$ . However, this model is unrealistic from an implementation, or even from a classical complexity-theoretic, viewpoint. So, we instead consider a finite precision arithmetic or approximate testing model:

Definition 1.1 ( $\eta$ -approximate query).

The oracle, when queried for $f(\bm{x})$ , outputs $\widetilde{f}({\bm{x}})$ such that $|\widetilde{f}({\bm{x}})-f({\bm{x}})|\leq\eta$ , for some small parameter $\eta\in(0,1)$ , for every query point ${\bm{x}}$ .

It is clear that for any property $\mathcal{P}$ , any tester for $\mathcal{P}$ in the approximate model will also work in the exact model. The notion of approximate testing was studied in earlier works [46, 2, 37]. In this context, $\eta$ can be thought of as the resolution limit of the computational machine, i.e., if the machine offers some $\alpha$ bits of precision, then $\eta=2^{-\alpha}$ . $\eta$ can also be thought of the noise reliability threshold of a channel communicating reals, i.e., if some information $a\in\mathbb{R}$ is transmitted on a channel with a reliability threshold of $\eta$ , then the received observable $\widetilde{a}\in\mathbb{R}$ satisfies $|a-\widetilde{a}|\leq\eta$ . When $\eta=0$ , this is the exact query model.

All our testers in this work are analyzed in the approximate query model for $\eta>0$ . Our results also require appropriate upper bounds on $\eta$ , which will be stated in each context. But we use the exact query model for proving the lower bounds, since lower bounds for $\eta=0$ also hold for any $\eta$ -approximate query model for $\eta>0$ .

Similar to the context of access to the unknown functions, there are some variations in terms of the error profile of the testing algorithms. A tester is said to have two-sided error if it can err in both the cases: when $f\in\mathcal{P}$ , and when $f$ is $\varepsilon$ -far from $\mathcal{P}$ . This is in contrast with one-sided error testers, which always decide correctly when $f\in\mathcal{P}$ , and can only err when $f$ is $\varepsilon$ -far from $\mathcal{P}$ . Likewise, a tester is said to be adaptive if it performs queries based on the answers it obtained for the previous queries. On the other hand, a non-adaptive tester performs all its queries together in a single round. A tester over a finite domain is said to be local if the number of queries performed by it is independent of the domain size.

In this work, we design testers in the approximate query model for three sparse function representations: $k$ -linear, $k$ -sparse low-degree polynomials, and $k$ -juntas. Our testers for $k$ -linearity, and $k$ -sparse low-degree polynomials have two-sided error, whereas our $k$ -junta tester has one-sided error. Our testers for $k$ -linear functions and $k$ -juntas are adaptive, while our tester for $k$ -sparse low-degree polynomials is non-adaptive. Importantly, all our testers are local: the number of queries performed by our testers is independent of the domain dimension $n$ , and depends only on the sparsity parameter $k$ and the proximity parameter $\varepsilon$ (as well as the total degree $d$ in the $k$ -sparse low-degree polynomial case).

These properties are well-studied in the Boolean and finite fields regime, and this work strives to do the same over continuous domains. We believe the new techniques we have developed to design these testers will be of independent interest.

Boundedness.

We assume that the unknown functions are bounded inside an $\ell_{2}$ ball $\operatorname{B}$ (centered at the origin $\bm{0}$ ) of suitable radius (typically $O(\sqrt{n})$ ), i.e., for every $\bm{x}\in\operatorname{B}(\bm{0},O(\sqrt{n}))$ , $|f(\bm{x})|\leq C\|\bm{x}\|_{2}$ for some fixed constant $C$ (so $|f(\bm{x})|\leq C\sqrt{n}$ in $\operatorname{B}(\bm{0},2\sqrt{n})$ ) ²²2This boundedness notion corresponds to the bounds we get for low-degree polynomials over compact domains, e.g., if $f(x)=a_{1}x+\ldots+a_{d}x^{d}$ is a polynomial in $x$ , then $|f(x)|\leq\sum_{i=1}^{d}|a_{i}|R^{i}$ for any $x\in[-R,R]$ , for all $R\geq 0$ .. Note that testing only via bounded queries is impossible without such an assumption. For example, consider an arbitrary “good” function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ ( $k$ -linear, $k$ -sparse polynomial, or a $k$ -junta), and choose a suitably small region $R$ at random (e.g. by choosing ${\bm{y}}$ uniformly from $\mathrm{B}(\bm{0},\sqrt{n})$ and setting $R$ to be a small radius ball around ${\bm{y}}$ ), where $0<\mu_{n}(R)\ll 1/n^{c}$ for any $c>0$ under the $\mathcal{N}(\bm{0},I_{n})$ Gaussian measure on $\mathbb{R}^{n}$ . Further, subdivide $R$ equally into $R_{1}$ and $R_{2}$ , and for some $A\geq 2\varepsilon/\mu_{n}(R)$ , define a function $f^{\prime}:\mathbb{R}^{n}\to\mathbb{R}$ which is identical to $f$ outside $R$ ; while $f^{\prime}(\bm{x})=A$ for ${\bm{x}}\in R_{1}$ , $f^{\prime}(\bm{x})=-A$ for ${\bm{x}}\in R_{2}$ . As $A>0$ can be arbitrarily large, $f^{\prime}$ can be moved arbitrarily far from the required property (in $\ell_{1}$ distance over the Gaussian measure). However, since $\mu_{n}(R)$ is arbitrarily small, no algorithm using bounded queries can distinguish between $f$ and $f^{\prime}$ .

Choice of Reference Distribution.

In this work (for $k$ -linear, and $k$ -sparse low-degree testers), we have used an anti-concentration result of Glazer and Mikulincer (Theorem 4.6) which uses the Carbery-Wright anti-concentration inequality (Theorem 4.5), but with a more usable expression for the variance (in terms of the polynomial coefficients). This form assumes that the distribution (on the variables) is log-concave, isotropic, and non-discrete. We have chosen $\mathcal{N}(\bm{0},I_{n})$ as representative of such a distribution, but we can also take $P^{\otimes n}$ for any continuous, log-concave distribution $P$ on $\mathbb{R}$ . A probabilistic upper bound for the Hankel matrix eigenvalues, which we use in the analysis of the $k$ -sparsity tester, also assumes the isotropic Gaussian distribution (Theorem 2.12).

2 Our results

We focus on testing (i) $k$ -linearity, (ii) $k$ -sparse, low-degree polynomials, and (iii) $k$ -juntas, and assume that our reference distribution $\mathcal{D}$ is $\mathcal{N}(\bm{0},I_{n})$ , unless otherwise stated.

2.1 Testing $𝒌$ -linear functions

Definition 2.1 ( $k$ -linearity).

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ , and $k\in\mathbb{N}$ . $f$ is $k$ -linear if there exists a set $S\subseteq[n]:|S|\leq k$ , and there exist coefficients $\{c_{i}\in\mathbb{R}\}_{i\in S}$ , such that, $f\equiv\sum_{i\in S}c_{i}{x}_{i}$ .

This problem has been extensively studied over finite domains with exact query access. [43] designed the first tester for $k$ -linearity with query complexity $\widetilde{O}(k^{2})$ by studying the related problem of testing $k$ -juntas. Later, [18] improved the bound for testing $k$ -juntas to $O(k\log k)$ queries. Using the BLR test [24], along with this result gives a tester for $k$ -linearity with $O(k\log k)$ query complexity, as done by [26], who presented an optimal, two-sided error, non-adaptive algorithm for this problem over Boolean domains. The first lower bounds for this problem were presented by [43], proving $\Omega(\sqrt{k})$ non-adaptive, and $\Omega(\log k)$ adaptive queries are necessary for testing $k$ -linearity. These were first improved by [49], to $\Omega(k)$ non-adaptive, and $\Omega(\sqrt{k})$ adaptive query lower bounds. This was further improved by [19, 20] who proved $\Omega(k)$ adaptive query lower bound. Interestingly, the $\Omega(k)$ adaptive query lower bound by [19] was proved by showing a novel connection to communication complexity, which we will also use later to prove our lower bounds.

Theorem 2.2 (Informal, see Theorem 5.1).

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a function bounded on the ball $\operatorname{B}(\bm{0},2\sqrt{n})$ , given via an $\eta$ -approximate query oracle. Let $k\in\mathbb{N}$ , and $\varepsilon,\eta\in(0,2/3)$ be parameters such that $\eta<\min\left\{\varepsilon,O\left(\min\limits_{\begin{subarray}{c}i\in[n]:f(% \bm{e}_{i})\neq 0\end{subarray}}\frac{|f(\bm{e}_{i})|}{(nk)^{2}}\right)\right\}$ , where $\bm{e}_{i}$ denotes the $i^{th}$ standard basis vector. There exists an $\widetilde{O}(k\log k+\nicefrac{{1}}{{\varepsilon}})$ -query tester (Algorithm 1) that distinguishes whether $f$ is $k$ -linear, or is $\varepsilon$ -far from all $k$ -linear functions, with probability at least $2/3$ .

$\blacktriangleright$ Remark 2.3.

Note the necessity of sufficiently good machine precision (small $\eta$ ) to successfully test $k$ -linearity. This is inevitable because if a linear function $f$ has $k$ “large” coefficients $a_{1},\ldots,a_{k}$ ( $\geq\eta$ ), and a small coefficient $a_{k+1}$ (say $<\eta/n^{2}$ ), we cannot distinguish (up to $\ell_{1}$ distance $\varepsilon\approx\eta$ ) between $f$ and the $k$ -linear function $\sum_{i=1}^{k}a_{i}x_{i}$ using $\eta$ -approximate queries and Algorithm 1. The tester (specifically, Algorithm 2) uses the absolute difference between function values, which will be at most $|a_{k+1}(x_{k+1})|\ll 2\eta$ . Similar restrictions apply to testing $k$ -sparse polynomials, and $k$ -juntas.

In another sense, a qualitative dependence of $\eta$ on the function structure is inevitable. Otherwise, if given an $\eta$ -approximate oracle $\widetilde{f}$ to $f$ , $\widetilde{f}^{\prime}\triangleq\widetilde{f}/2^{n}$ (which can be computed in $O(n)$ time given $\widetilde{f}$ , assuming a variable-length binary floating-point representation) would be an $\eta/2^{n}$ -approximate oracle to $f$ . But such a scaling would not help with our results, since the coefficients of $f$ , the non-zero influences, etc. would be similarly scaled-down.

2.2 Testing $𝒌$ -sparse low degree polynomials

Definition 2.4 ( $k$ -sparsity).

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ , and $k\in\mathbb{N}$ be a parameter. A monomial $\bm{x}^{\bm{\alpha}}\triangleq\prod_{i=1}^{n}x_{i}^{\alpha_{i}}$ , for any ${\bm{x}}\triangleq(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}$ , and $\bm{\alpha}\triangleq(\alpha_{1},\ldots,\alpha_{n})\in\mathbb{N}^{n}$ has total degree $\|\bm{\alpha}\|_{1}\triangleq\sum_{i=1}^{n}\alpha_{i}$ . A polynomial $f(x_{1},\ldots,x_{n})=\sum_{i=1}^{\ell}a_{i}{\bm{x}}^{\bm{d}_{i}}$ , with $a_{i}\neq 0$ and $\bm{d}_{i}\in\mathbb{N}^{n}$ , $\forall\;i\in[\ell]$ , of total degree $\max_{i\in[\ell]}\{\|\bm{d}_{i}\|_{1}\}$ , is said to be a $k$ -sparse polynomial if $\ell\leq k$ .

Grigorescu et al. [52] solved this problem for polynomials on finite fields, i.e., $f:\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}$ , for large enough $q$ , using the machinery of Hankel matrices associated with polynomials:

Definition 2.5 (Hankel Matrix for polynomials [52, 11]).

Consider any $\bm{u}\triangleq(u_{1},\ldots,u_{n})\in\mathbb{R}^{n}$ , and define $\bm{u}^{i}\triangleq(u_{1}^{i},\ldots,u_{n}^{i})\in\mathbb{R}^{n},\text{for % every }i\in\mathbb{N}$ . For a function $f:\mathbb{R}^{n}\to\mathbb{R}$ and $t\in\mathbb{N}$ , define the $t$ -dimensional Hankel matrix associated with $f$ at $\bm{u}$ to be the following:

H_{t}(f,\bm{u})\triangleq\begin{pmatrix}f(\bm{u}^{0})&f(\bm{u}^{1})&\ldots&f(% \bm{u}^{t-1})\\ f(\bm{u}^{1})&f(\bm{u}^{2})&\ldots&f(\bm{u}^{t})\\ \vdots&\vdots&\ddots&\vdots\\ f(\bm{u}^{t-1})&f(\bm{u}^{t})&\ldots&f(\bm{u}^{2t-2})\end{pmatrix}\in\mathbb{R% }^{t\times t}.

We note an observation about Hankel matrices. It follows essentially the same argument as in [11, 52], since the decomposition they use over finite domains also works over the reals.

Observation 2.6 (Generalization of [11, Section 4], and [52, Lemma 4]).

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be an exactly $k$ -sparse polynomial over the reals, i.e., $f(\bm{x})=\sum_{i=1}^{k}a_{i}M_{i}(\bm{x})$ , where $a_{1},\ldots,a_{k}\in\mathbb{R}\setminus\{0\}$ , and $M_{1},\ldots,M_{k}$ are the monomials of $f$ . Then for all $\ell+1\leq k$ ,

\det\left(H_{\ell+1}(f,\bm{x})\right)=\sum_{\begin{subarray}{c}S\subseteq[k]\\ |S|=\ell+1\end{subarray}}\prod_{i\in S}a_{i}\prod_{\begin{subarray}{c}i,j\in S% \\ i<j\end{subarray}}(M_{j}(\bm{x})-M_{i}(\bm{x}))^{2},

is a non-zero polynomial of degree $\leq 2\binom{\ell+1}{2}\deg(f)$ , while $\forall\;\ell+1>k$ , $\det\left(H_{\ell+1}(f,\bm{x})\right)\equiv 0$ .

From Ben-Or and Tiwari [11]’s Observation 2.6, Grigorescu et al. [52] designed a tester with a query complexity of $O(k)$ (independent of $d$ ), assuming $f$ to be an individual-degree- $d$ polynomial (note that all functions $\mathbb{F}_{q}^{n}\rightarrow\mathbb{F}_{q}$ are polynomials of individual degree $\leq q$ ).

Note that if we have exact query access to $f$ , the Hankel matrix $H_{t}(f,\bm{u})$ can be computed using only $2t-1$ queries to $f$ for any point $\bm{u}\in\mathbb{R}^{n}$ . For the problem of testing a polynomial $f:\mathbb{R}^{n}\to\mathbb{R}$ for sparsity, given exact query access, the tester of [52] works as it is. In fact, it achieves perfect soundness and completeness (proved in Lemma 6.4). However, the assumption of an exact query oracle is not realistic. Moreover, for general functions $f:\mathbb{R}^{n}\to\mathbb{R}$ , the promise of polynomiality no longer holds, and therefore a preliminary step is needed to eliminate functions that are far from being low-degree polynomials. [5] designed a local, approximate query, low degree tester with a query complexity of $O(d^{5})$ , for polynomials over $\mathbb{R}^{n}$ with total degree $d$ , which we will use in our work. Thus, we restrict our attention to polynomials of total degree at most $d$ .

Theorem 2.7 (Informal, see Theorem 6.1).

Let $k,d\in\mathbb{N}$ , $\varepsilon,\eta\in(0,1)$ be parameters such that $\eta<\min\{\varepsilon,1/2^{2^{n}}\}$ , and $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be bounded in $\operatorname{B}(\bm{0},2d\sqrt{n})$ , given via an $\eta$ -approximate query access. Then there exists an $\widetilde{O}(d^{5}+\frac{d^{2}}{\varepsilon}+dk^{3})$ -query tester (Algorithm 4), that distinguishes whether $f$ is a $k$ -sparse, degree- $d$ polynomial, or is $\varepsilon$ -far from all such polynomials, with probability $\geq 2/3$ .

$\blacktriangleright$ Remark 2.8.

We note that Test- $k$ -Sparse (Algorithm 4) also works for testing $k$ -linear functions (by setting the degree $d=1$ ). However, we make the following remarks:

(i)

The query complexity of Test- $k$ -Sparse ( $\widetilde{O}(d^{5}+\frac{d^{2}}{\varepsilon}+dk^{3})$ ), invoked for $k$ -linearity testing, would be $\widetilde{O}(k^{3}+\frac{1}{\varepsilon})$ , which is worse than that of Test- $k$ -Linear.
(ii)

The restriction on the approximation parameter $\eta$ is $1/2^{2^{n}}$ for Test- $k$ -Sparse, as compared to $1/(nk)^{2}$ for Test- $k$ -Linear. Thus, for a wider range of parameters when $\eta$ is not too small, invoking Test- $k$ -Linear is better, compared to Test- $k$ -Sparse.
(iii)

Test- $k$ -Linear is an adaptive tester, while Test- $k$ -Sparse is non-adaptive.

2.3 Testing $𝒌$ -juntas

Definition 2.9 ( $k$ -junta).

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ , and $k\in\mathbb{N}$ be a parameter. A variable $x_{i}$ , $i\in[n]$ , is influential with respect to $f$ , if for some $\bm{x}\triangleq(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}$ , changing ${x}_{i}$ changes $f(\bm{x})$ . $f$ is a $k$ -junta, if there are at most $k$ influential variables with respect to $f$ .

Testing whether a Boolean function is a $k$ -junta has been extensively studied in the exact query model. The first result in this context was by [66], which was followed by the work of [43], who designed a $\widetilde{O}(k^{2})$ -query tester. Later, [33] extended it to the finite range setting. [17] then gave an $\widetilde{O}(k^{3/2})$ -query non-adaptive tester for this problem, while for adaptive testers, [18] showed $\widetilde{O}(k\log k+k/\varepsilon)$ queries suffice. It is important to note that all these results use Fourier-analytic techniques. Notably, [22] designed a new algorithm for testing $k$ -juntas with similar optimal bounds in the context of testing partial isomorphism of functions. Interestingly, this work deviates from the common Fourier analytic approach and instead presents a combinatorial approach to this problem. This algorithm from [22] will be used in designing our tester for $k$ -juntas. Recently [32] studied the linear $k$ -junta testing problem, where the function $f$ is defined as $f:\mathbb{R}^{n}\rightarrow\{+1,-1\}$ ³³3A function $f:\mathbb{R}^{n}\rightarrow\{-1,1\}$ is said to be a linear k-junta if there are $k$ unit vectors $u_{1}\ldots,u_{k}\in\mathbb{R}^{n}$ and $g:\mathbb{R}^{k}\rightarrow\{-1,1\}$ such that $f(x)=g(\langle u_{1},x\rangle,\ldots,\langle u_{k},x\rangle)$ .. This is different from our setting of real-valued functions. It is not clear to us if their techniques can be generalized to our setting. In terms of lower bounds, [43] showed a lower bound of $\Omega(\sqrt{k})$ queries for non-adaptive testers, which was improved to $\widetilde{\Omega}(k^{3/2}/\varepsilon)$ by [30]. For adaptive testers, [31] showed an $\Omega(k)$ lower bound, which was then improved to $\Omega(k\log k)$ by [72].

Theorem 2.10 (Informal, see Theorem 7.1).

Let $k\in\mathbb{N}$ , and $\varepsilon,\eta\in(0,1)$ be such that $\eta<\min\{O(\varepsilon/k^{2}),O(\frac{1}{k^{2}\log^{2}k})\}$ , and $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be bounded in $\operatorname{B}(\bm{0},2\sqrt{n})$ , given via $\eta$ -approximate queries. There exists a one-sided error, $\widetilde{O}\left(\frac{k\log k}{\varepsilon}\right)$ -query tester (Algorithm 6), that distinguishes if $f$ is a $k$ -junta, or is $\varepsilon$ -far from all $k$ -juntas, with probability at least $2/3$ .

2.4 Lower bounds

We briefly mention our lower bound results, which hold even for adaptive testers, and exact query access. For all three properties ( $k$ -linearity, $k$ -sparse degree- $d$ polynomials, and $k$ -juntas), we prove lower bounds of $\Omega(\max\{k,\frac{1}{\varepsilon}\})$ queries. Additionally, for $k$ -sparse, degree- $d$ polynomials, we prove a lower bound of $\Omega(\max\{k,d,\frac{1}{\varepsilon}\})$ queries. All our lower bounds follow from the general reduction from communication complexity, introduced by [19], coupled with some folklore results. We use Set-Disjointness as the hard instance to prove our results.

Theorem 2.11.

Given exact query access to $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ , some $k,d\in\mathbb{N}$ and a distance parameter $\varepsilon\in(0,1)$ , $\Omega\left(\max\{k,\frac{1}{\varepsilon}\}\right)$ queries are necessary for testing (i) $k$ -linear functions, (ii) $k$ -sparse degree- $d$ polynomials, and (iii) $k$ -juntas, with success probability at least $\nicefrac{{2}}{{3}}$ .

The lower bound for testing $k$ -sparse degree- $d$ polynomials is improved to $\Omega\left(\max\{d,k,\frac{1}{\varepsilon}\}\right)$ .

2.5 New Technical Contributions

$𝒌$ -sparsity Tester.

A critical ingredient in proving the $k$ -sparse low degree tester (Theorem 2.7) is a new probabilistic upper bound on the maximum singular value of Hankel matrices associated with sparse, low-degree polynomials. This may be of independent interest.

Theorem 2.12 (Probabilistic Upper Bound on $\sigma_{\max}$ ).

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ , $f(\bm{x})=\sum_{i=1}^{k}a_{i}M_{i}(\bm{x})$ be a $k$ -sparse, degree- $d$ polynomial, where $M_{i}$ ’s are its non-zero monomials, and $\sigma_{\max}(H_{t}(f,\bm{u}))$ denotes the largest singular value of the $t$ -dimensional Hankel matrix associated with $f$ at a point $u\in\mathbb{R}^{n}$ , $H_{t}(f,\bm{u})$ . Then, for any $\gamma\in(0,1)$ , with $\bm{a}\triangleq(a_{1},\cdots,a_{k})^{\top}\in\mathbb{R}^{k}$ ,

\Pr_{\bm{u}\sim\mathcal{N}(\bm{0},I_{n})}\left[\sigma_{\max}(H_{t}(f,\bm{u}))% \geq\|\bm{a}\|_{2}^{2}\left(2^{d/2}\lceil d/2\rceil!+\sqrt{\frac{k}{\gamma}}2^% {d/2}\sqrt{d!}\right)^{2t}\right]\leq\gamma.

Proof Sketch.

For any vector $\bm{v}\in\mathbb{R}^{n}$ , let $|\bm{v}|\in\mathbb{R}_{\geq 0}^{n}$ denote the vector with the absolute values of the coordinates of $\bm{v}$ . Then, for any $\bm{z},\bm{u}\in\mathbb{R}^{n}$ , using the triangle inequality, and a Vandermonde-like decomposition of $H_{\bm{u}}\triangleq H_{t}(|f|,|\bm{u}|)$ , (from Observation 2.6), where $|f|(\bm{x})\triangleq\sum_{i\in[k]}|a_{i}|M_{i}(\bm{x})$ , we can upper-bound $|\bm{z}^{\top}H_{\bm{u}}\bm{z}|$ by $|\bm{z}|^{\top}V^{\top}DV|\bm{z}|=\|D^{\frac{1}{2}}V|\bm{z}|\|_{2}^{2}$ , where $D=\mathrm{diag}(|\bm{a}|)$ , $V$ is the Vandermonde matrix $\mathsf{V}_{t}(|M_{1}(\bm{u})|,\ldots,|M_{k}(\bm{u})|)\in\mathbb{R}^{k\times t}$ , and $M(|\bm{u}|)=|M(\bm{u})|$ . By the Courant-Fischer characterization, we have

\sigma_{\max}(H_{\bm{u}})\leq\max_{\|\bm{z}\|_{2}\leq 1}\|D^{\frac{1}{2}}V|\bm% {z}|\|_{2}^{2}\leq\max_{\|\bm{z}\|_{2}\leq 1}\|D^{\frac{1}{2}}V\|_{\rm op}^{2}% \|\bm{z}\|_{2}^{2}\leq\|D^{\frac{1}{2}}V\|_{\rm F}^{2}.

Using some results from [36] for the moments of the folded normal distribution, along with the properties of the Gamma function and the fact that all the monomials $M_{i}$ have total degree $\leq d$ , we can upper bound

\mathop{\mathbb{E}}_{\bm{u}\sim\mathcal{N}(\bm{0},I_{n})}\left[|M_{i}(\bm{u})|% \right]\leq 2^{d/2}\lceil d/2\rceil!,\mbox{ and }\mathrm{Var}[|M_{i}(\bm{u})|]% \leq 2^{d}\cdot d!.

Chebyshev’s inequality and a union bound over the $k$ monomials completes the proof. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 2.13.

Theorem 2.12 seems to be extendable to more general mean-zero distributions of $\bm{u}$ with appropriate concentration (e.g. subgaussian, subexponential) since the crux of the proof, in addition to the use of properties of the Hankel matrix (which do not depend on the distribution of $\bm{u}$ ), is to bound all the degree $d$ moments of the distribution.

$𝒌$ -linearity Tester.

For $k$ -linearity, our tester is similar to the algorithm proposed in [26] for testing $k$ -linearity of functions $f:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}$ , with the BLR test replaced by the approximate-query linearity tester from [44, 5, 7]. The crucial difficulties in the analysis over the reals come from (i) the $\eta$ -approximate query access, and (ii) the use of $\ell_{1}$ -distance for farness. We first reject all functions which are far from linearity by means of the linearity test, and, conditioned on the fact that the tester does not reject with high probability, proceed to testing the self-corrected function instead (with closeness to linearity guaranteed). But we now have only approximate query access to the function, which we test for $k$ -linearity by splitting the variables into $O(k^{2})$ random buckets as in [26] and identify the influential ones. However, there is no analogous result for real-valued functions. Hence, we present a new analysis in Claim 5.11 for the FindInfBucket (Algorithm 2) that performs a binary search over the buckets, but with a different test for influential buckets that accounts for $\eta$ -approximate queries. The analysis with approximate queries involves the appropriate use of anti-concentration results (Theorem 4.5) for real linear polynomials.

$𝒌$ -junta tester.

Our tester is inspired by the junta testers used in [18] and [22], but our definition of influence (Definition 7.2) is different ( $\ell_{1}$ rather than Hamming), to work with approximate query oracle. Theorem 7.3, Lemma 7.4, and Lemma 7.5, in our analysis are similar to that of [22]. The significant difference in analysis for the $\ell_{1}$ distance comes in our Claim 7.7, and the subsequent proof of Theorem 7.1.

2.6 Discussion

Our efficient algorithms for the problem of testing real-valued functions given via approximate queries, over continuous domains, for three properties: (i) $k$ -linearity, (ii) $k$ -sparse, low-degree polynomials, and (iii) $k$ -juntas, summarized in Table 1, open several interesting questions:

Table 1: A comparison of the upper bounds, as well as the corresponding restrictions, for the three sparse representation testing problems. The upper bounds, and the restrictions in the three rows follow sequentially from Theorem 2.2, Theorem 2.7, and Theorem 2.10, respectively.

Problem	Upper Bound	Restriction
$k$ -linearity	$\widetilde{O}(k\log k+\frac{1}{\varepsilon})$	$\eta<\min\left\{\varepsilon,O\left(\min\limits_{\begin{subarray}{c}i\in[n]:f(% \bm{e}_{i})\neq 0\end{subarray}}\frac{\|f(\bm{e}_{i})\|}{(nk)^{2}}\right)\right\}$
$k$ -sparsity	$\widetilde{O}(d^{5}+\frac{d^{2}}{\varepsilon}+dk^{3})$	$\eta<\min\{\varepsilon,1/2^{2^{n}}\}$
$k$ -junta	$\widetilde{O}\left(\frac{k\log k}{\varepsilon}\right)$	$\eta<\min\{O(\varepsilon/k^{2}),O(\frac{1}{k^{2}\log^{2}k})\}$

$\blacksquare$

We note that our results have constraints on the approximate query parameter $\eta$ . The first open question is whether these can be improved.
$\blacksquare$

Furthermore, our $k$ -sparse degree- $d$ polynomial tester performs $\widetilde{O}(d^{5}+\frac{d^{2}}{\varepsilon}+dk^{3})$ queries, and our lower bound for this problem is $\Omega\left(\max\{d,k,\frac{1}{\varepsilon}\}\right)$ . The second open question is whether the gaps in these bounds (w.r.t. $k$ , and $d$ ) can be improved, e.g., by assuming additional structure on the underlying function, like Lipschitzness, etc.
$\blacksquare$

Another interesting direction is to design tolerant testers [65] for these properties. This is different from the approximate query testing notion, as in tolerant testing, the decision boundary is expanded to require that functions that are sufficiently close to the property are also accepted with high probability, whereas in the approximate query model, we accept functions $\widetilde{f}$ such that $\mathsf{dist}_{\mathcal{D},\infty}(f,\widetilde{f})\leq\eta$ (pointwise $\eta$ -close) which is a stronger constraint compared to the expected $\ell_{1}$ -distance $\mathsf{dist}_{\mathcal{D},\ell_{1}}(f,g)$ that we use between functions.
$\blacksquare$

We have focused on optimizing the query complexity in terms of the sparsity parameter $k$ and degree $d$ (for low-degree polynomial testing). It is an interesting problem to optimize the dependence of $\eta$ in our arguments.
$\blacksquare$

Only our $k$ -junta tester has a one-sided error profile, while our $k$ -linearity/sparsity testers have two-sided errors. Designing one-sided error testers for these problems is left open.
$\blacksquare$

Finally, we use $\mathcal{N}(\bm{0},I_{n})$ as the reference distribution. It would be interesting to see if our results can be extended to other concentrated distributions as well (see ▶ 2.13).

Organization of the paper

In Section 3, we present an overview of our results and techniques, followed by a discussion of the preliminaries in Section 4. In Section 5, we present our $k$ -linearity tester, followed by our tester for $k$ -sparse low-degree polynomials in Section 6, and our $k$ -junta tester in Section 7.

Due to space constraints here, we omit all proofs of intermediate technical lemmata and claims, an elaborate discussion of lower bounds, and all subroutines from prior works (ApproximateAdditivityTester [6, Algorithm 7], TestAdditivity [6, Algorithm 8], Approximate- $g$ [6, Algorithm 8], ApproxLowDegreeTester [6, Algorithm 9], ApproxCharacterizationTest [6, Algorithm 10], ApproxQuery- $g$ [6, Algorithm 10] and ApproxQuery- $g$ -InBall [6, Algorithm 10]). They are included in the full version [6].

3 Technical Overview

3.1 Testing $𝒌$ -linearity

We build upon the self-correct and test approach of [24, 53]. Instead of directly testing if $f$ is $k$ -linear, we construct a function $g_{\text{self-correct}}$ such that if $f$ is $k$ -linear, then $g_{\text{self-correct}}$ will also be $k$ -linear. Moreover, we simulate queries to $g_{\text{self-correct}}$ using queries to $f$ , and test this newly constructed function $g_{\text{self-correct}}$ .

We use the Gaussian distribution as the reference distribution, since there are no uniform distributions over continuous domains with infinite support. (This deviates from the self-correction approach of [24].) In particular, we evaluate $f$ on a set of points sampled from $\mathcal{N}(\bm{0},I_{n})$ to construct the self-corrected function $g_{\text{self-correct}}$ . To deal with the fact that different points from $\mathcal{N}(\bm{0},I_{n})$ have different probability masses, the idea is to radially project the sampled points from $\mathcal{N}(\bm{0},I_{n})$ into a small Euclidean ball $\operatorname{B}(\bm{0},r)$ of a small (constant) radius ( $r=1/50$ suffices) such that the probability masses of all points sampled from that ball is roughly the same. Moreover, since we work with an approximate oracle, we use a median-based notion of the self-corrected function, with a contraction factor $\kappa_{\bm{p}}:\mathbb{R}^{n}\to\mathbb{R}$ :

g(\bm{p})\triangleq\ \kappa_{\bm{p}}\cdot\mathop{\mathsf{med}}_{\bm{x}\sim% \mathcal{N}(\bm{0},I_{n})}\left[f\left(\frac{\bm{p}}{\kappa_{\bm{p}}}-\bm{x}% \right)+f\left(\bm{x}\right)\right],\text{ and }\kappa_{\bm{p}}\triangleq% \begin{cases}1&\text{, if }\|\bm{p}\|_{2}\leq r\\ \lceil\|\bm{p}\|_{2}/r\rceil&\text{, if }\|\bm{p}\|_{2}>r\end{cases},

so that $\bm{p}/\kappa_{\bm{p}}\in\operatorname{B}(\bm{0},r)$ . This definition of self-correction function was used in [44, 5, 7].

To test $k$ -linearity (Algorithm 1), we first test if $f$ is pointwise close to some additive (aka. linear) function using ApproximateAdditivityTester. If it rejects $f$ , we also reject $f$ . However, if ApproximateAdditivityTester does not reject, then the self-corrected function $g$ is pointwise close to some linear function. As we only have approximate oracle access to $f$ , we can’t simulate $g$ exactly. So, we use Approximate- $g$ , the approximate query oracle for $g$ . The work of [5, 7] proves: (i) $g$ and Approximate- $g$ are pointwise close in $\operatorname{B}(\bm{0},r)$ , and (ii) $f$ and Approximate- $g$ are also pointwise close. So, $f$ is pointwise close to Approximate- $g$ .

We partition the $n$ -variables $[n]$ into $k^{2}$ buckets uniformly at random. So if $f$ is $k$ -linear, the influential variables will be separated into different buckets w.h.p. We can then detect them via the subroutine $\mathsf{FindInfBucket}$ (Algorithm 2), which recursively isolates the variables in a bucket and returns only the influential ones. We then reject if the number of buckets with influential variables (variables whose values determine the value of $f$ ) is more than $k$ .

3.2 Testing $𝒌$ -sparsity

Our $k$ -sparse, degree- $d$ polynomial tester (Algorithm 4) adopts a similar approach. We first test if $f$ is a low-degree polynomial, using the ApproxLowDegreeTester from [5, 7]. If it rejects $f$ , we also reject $f$ . However, if ApproxLowDegreeTester does not reject $f$ , then $f$ is point-wise close to a low-degree polynomial.

As in $k$ -linearity testing, we use a self-corrected function $g$ from [5, 7]: For points $\bm{p}\in\operatorname{B}(\bm{0},r)$ , $g(\bm{p})$ is the (weighted) median value of $g_{\bm{q}}(\bm{p})\triangleq\sum_{i=1}^{d+1}(-1)^{i+1}\binom{d+1}{i}f(\bm{p}+i% \bm{q})$ , weighted according to the probability of $\bm{q}\sim\mathcal{N}(\bm{0},I_{n})$ , i.e., $g(\bm{p})\triangleq\underset{\bm{q}\sim\mathcal{N}(\bm{0},I_{n})}{\mathsf{med}% }[g_{\bm{q}}(\bm{p})].$ Intuitively, $g_{\bm{q}}(\bm{p})$ is the value that $f$ should take if, when restricted to the line $\operatorname{L}_{\bm{p},\bm{q}}\triangleq\{\bm{p}+t\bm{q},t\in\mathbb{R}\}$ , $f$ would be a degree- $d$ univariate polynomial. Taking the weighted median over all directions $\bm{q}\sim\mathcal{N}(\bm{0},I_{n})$ , ensures that the self-correction proportionately respects the values of $f$ , in a local neighborhood of $\bm{p}$ . For $\bm{p}\not\in\operatorname{B}(\bm{0},r),g$ is defined via radial extrapolation from within $\operatorname{B}(\bm{0},r)$ along the radial line $\operatorname{L}_{\bm{0},\bm{p}}$ .

Given exact query access to $f$ , we can simulate query access to the self-corrected function $g$ . As we only have approximate query access to $f$ , we use ApproxQuery-g (the approximate oracle to the self-corrected function associated with $f$ ), which was proved to be pointwise close to $g$ . As a result, $f$ will be pointwise close to ApproxQuery-g as well.

Once we have that $f$ is close to a low-degree polynomial, we use a Hankel matrix (Definition 2.5) based characterization for sparse polynomials. [52, 11] proved Observation 2.6: a polynomial $f$ (over finite fields) is $k$ -sparse, if and only if its associated Hankel matrix has a non-zero determinant. This can be efficiently tested with only $2k+1$ queries to $f$ . For polynomials over the reals with exact-queries, the idea from [52] can be extended to give a zero-error (perfect soundness and completeness), zero-gap (does not require $\varepsilon$ -farness for $\varepsilon$ > 0 in the No case) tester, making $2k+1$ queries for deciding whether (i) $f$ is $k$ -sparse, or (ii) $f$ is not $k$ -sparse (proved in Lemma 6.4). This result is even stronger than what [52] gets for finite fields, since the zero set of any polynomial over the reals has zero Gaussian (or Lebesgue) measure, whereas the corresponding probability needs to be bounded in terms of the degree of the polynomials over finite fields (e.g. by the Schwartz-Zippel lemma). Unfortunately, since we only have approximate query access to $f$ , this technique no longer works, as determinants of sums of matrices do not behave nicely. So we take a probabilistic approach, showing that the noisy Hankel matrix constructed from the approximate query to $f$ is not too far from the exact Hankel matrix (proved in Observation 6.5). Finally, we show in Theorem 6.6 using Weyl’s inequality (Theorem 4.4), that if $f$ is a $k$ -sparse, low-degree polynomial, then the smallest eigenvalue of the noisy Hankel matrix associated with ApproxQuery-g is not too large. Combining them all, our main result is proved in Section 6.2.

Since, we only have access to the Hankel matrix of $\widetilde{f}=\textnormal{{ApproxQuery}-}$ g which is $\eta^{\prime}$ -close to $f$ (on all the query points, whp), we can express $\widetilde{H}_{\bm{u}}\triangleq H_{t}(\widetilde{f},\bm{u})$ (for $t=k+1$ ) of such a $\widetilde{f}$ as the sum of $H_{\bm{u}}\triangleq H_{t}(f,\bm{u})$ and a Hankel-structured error matrix with bounded spectral/operator norm (Observation 6.5). From this, and Weyl’s inequality, we get completeness as long as we Accept when the smallest singular value $\sigma_{\min}(\widetilde{H}_{\bm{u}})\leq\eta^{\prime}(k+1)$ in all $\Theta(d(k+1)^{2})$ rounds.

To prove soundness, we need to show that $\sigma_{\min}(\widetilde{H}_{\bm{u}})>\eta^{\prime}(k+1)$ in some round with probability $\geq 2/3$ , as long as $Q(\bm{u})\triangleq\det(H_{\mathbf{u}})$ is a non-zero polynomial. This follows (in Theorem 6.6) by invoking the probabilistic upper bound on $\sigma_{\max}(H_{\mathbf{u}})$ , for $\bm{u}\sim\mathcal{N}(\bm{0},I_{n})$ .

3.3 Testing $𝒌$ -juntas

Finally, we discuss our algorithm for testing $k$ -juntas (Algorithm 6). Our approach is to first randomly partition the $n$ -variables into $k^{2}$ buckets. If $f$ is a $k$ -junta, the $k$ influential variables will be separated into distinct buckets w.h.p (by birthday paradox).

Now we run $O(k/\varepsilon)$ iterations to find if there exists any influential variable in any bucket, using the subroutine $\mathsf{FindInfBucket}$ (Algorithm 2). After these iterations, if we find more than $k$ influential variables in $f$ , we reject it. Otherwise, we accept $f$ . Our analysis follows a combinatorial style similar to [22]. We would like to note that although we use $\mathsf{FindInfBucket}$ for $k$ -linearity testing as well, the analysis here significantly deviates from that of $k$ -linearity testing and is presented in Claim 7.7. The main result is formally proved in Section 7.1.

4 Preliminaries

Notations.

Throughout this work, we use boldface letters to represent vectors of length $n$ and normal face letters for variables. Specifically, $\bm{e}_{i}\triangleq(0,\ldots,0,1_{i},0,\ldots,0)$ denotes the $i^{th}$ standard unit vector. For $n\in\mathbb{N}$ , let $[n]$ denote the set $\{1,\dots,n\}$ . For a matrix $A$ , let $\|A\|_{\infty}$ , $\|A\|_{\mathrm{op}}$ , and $\|A\|_{\mathrm{F}}$ denote the supremum, operator, and Frobenious norms of $A$ , respectively. See [56] for the formal definitions. For concise expressions and readability, we use the asymptotic complexity notion of $\widetilde{O}(\cdot)$ , where we hide poly-logarithmic dependencies of the parameters. For any $f:\mathbb{R}^{n}\to\mathbb{R}$ , let $\|f\|_{-\infty(/\infty),C}$ denote the infimum(resp. supremum) value of $f$ over some $C\subseteq\mathbb{R}^{n}$ . Let $\Pi_{n}$ be the class of functions $\mathbb{R}^{n}\rightarrow\mathbb{R}$ satisfying some particular first-order property and let $\Pi=\cup_{n\geq 1}\Pi_{n}$ .

Definition 4.1 ( $\ell_{1}$ -distance).

Let $\mathcal{D}=\{\mathcal{D}_{n}\}_{n\geq 1}$ is family of distributions with $\mathcal{D}_{n}$ being a distribution on $\mathbb{R}^{n}$ . For two arbitrary functions $f,g:\mathbb{R}^{n}\rightarrow\mathbb{R}$ , the $\ell_{1}$ -distance between $f$ and $g$ is defined as: $\mathsf{dist}_{\mathcal{D},\ell_{1}}(f,g)\triangleq\mathop{\mathbb{E}}_{\bm{x}% \sim\mathcal{D}_{n}}\,[|f(\bm{x})-g(\bm{x})|]$ . We also define the $\ell_{p}$ -distance of $f$ to the class $\Pi_{n}$ , and hence the class $\Pi$ , by $\mathsf{dist}_{\mathcal{D},\ell_{p}}(f,\Pi)\triangleq\mathsf{dist}_{\mathcal{D% },\ell_{p}}(f,\Pi_{n})\triangleq\inf_{g\in\Pi_{n}}\mathsf{dist}_{\mathcal{D},% \ell_{p}}(f,g)$ .

We have $\mathsf{dist}_{\mathcal{D},\ell_{p}}(f,\Pi)=0$ if and only if there exists a function $g\in\Pi_{n}$ which agrees with $f$ almost everywhere with respect to $\mathcal{D}_{n}$ (in the measure-theoretic sense). We will only concern ourselves with $p\in\{0,1\}$ since we are dealing with scalar-valued functions (aka functionals) and hence $\|f(\bm{x})-g(\bm{x})\|_{p}=|f(\bm{x})-g(\bm{x})|$ for all $p>0$ .

Our definitions hold for general reference distributions $\mathcal{D}$ which are suitably concentrated. Later, we work with $\mathcal{N}(\bm{0},I_{n})$ , which also has this desired concentration property.

Definition 4.2 (Concentrated distribution).

Let $\varepsilon\in(0,1),R\geq 0$ , and $\bm{c}\in\mathbb{R}^{n}$ . A distribution $\mathcal{D}$ supported on $\mathbb{R}^{n}$ is $(\varepsilon,R,\bm{c})$ -concentrated if most of its mass is contained in a ball of radius $R$ centered at some point $\bm{c}\in\mathbb{R}^{n}$ , i.e., $\Pr_{\bm{p}\sim\mathcal{D}}[\bm{p}\in\operatorname{B}(\bm{c},R)]\geq 1-\varepsilon$ .

For brevity, we may write “ $\mathcal{D}$ is $(\varepsilon,R)$ -concentrated” to mean “ $\mathcal{D}$ is $(\varepsilon,R,\bm{0})$ -concentrated”.

Fact 4.3 ([23, Theorem 2.9]).

$\mathcal{N}(\bm{0},I_{n})$ is $(0.01,2\sqrt{n},\bm{0})$ -concentrated.

4.1 Results from Perturbation Theory, and Measure Theory

For analyzing our testers, we use the following result from perturbation theory.

Theorem 4.4 (Weyl’s Inequality [55]).

Let $\hat{\Sigma}=\Sigma+E$ , where $\Sigma,E\in\mathbb{R}^{n\times n}$ are both symmetric matrices. Let $\lambda_{i}(A)$ denote the $i^{th}$ eigenvalue of (symmetric matrix) $A$ , sorted in non-increasing order, and let $\|A\|_{\mathrm{op}}$ denote its $\ell_{2}$ -operator (spectral) norm. Then,

\max_{i\in[n]}\{|\lambda_{i}(\hat{\Sigma})-\lambda_{i}(\Sigma)|\}\leq\|E\|_{% \mathrm{op}}\leq\max\{|\lambda_{d}(E)|,|\lambda_{1}(E)|\}.

The following celebrated inequality of Carbery and Wright [27] provides anti-concentration bounds for polynomials of i.i.d Gaussian random variables (more generally, log-concave), which will be used in our proofs, particularly in the analysis of our $k$ -linearity tester.

Theorem 4.5 ([27, Theorem 8]).

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be a polynomial of degree $d$ , such that $\mathop{\mathsf{Var}}_{\mathcal{N}(\bm{0},I_{n})}[f]=1$ . Then $\forall\,t\in\mathbb{R}$ and $\forall\,\varepsilon>0$ , $\Pr_{\bm{x}\sim\mathcal{N}(\bm{0},I_{n})}[|f(\bm{x})-t|\leq\varepsilon]\leq O(% d)\varepsilon^{1/d}$ .

A recent result of Glazer and Mikulincer [47] provided a more suitable form of Carbery-Wright for polynomials, with the variance lower-bounded in terms of the coefficients.

Theorem 4.6 ([47, Corollary 4]).

If $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is a polynomial $f(\bm{x})=\sum_{i=1}^{k}a_{i}\bm{x}^{\bm{M}_{i}}$ of degree $d$ , then there exists an absolute constant $C>0$ such that for any $t\in\mathbb{R}$ and $\varepsilon>0$ ,

\Pr_{\bm{x}\sim\mathcal{N}(\bm{0},I_{n})}[|f(\bm{x})-t|\leq\varepsilon]\leq Cd% \left(\frac{\varepsilon}{\mathrm{coeff}_{d}(f)}\right)^{1/d}\text{, where }% \mathrm{coeff}^{2}_{d}(f)\triangleq\sum_{\begin{subarray}{c}i\in[k]:\|\bm{M}_{% i}\|_{1}=d\end{subarray}}a_{i}^{2}.

5 $𝒌$ -linearity Testing

In this section, we present and analyze our algorithm Test- $k$ -Linear (Algorithm 1).

Theorem 5.1 (Generalization of Theorem 2.2).

Let $k\in\mathbb{N}$ , $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is a function bounded in the ball $B(\bm{0},2\sqrt{n})$ , and $\varepsilon,\eta\in(0,2/3)$ be such that $\eta<\min\left\{\varepsilon,O\left(\min\limits_{\begin{subarray}{c}i\in[n]:f(% \bm{e}_{i})\neq 0\end{subarray}}\frac{|f(\bm{e}_{i})|}{(nk)^{2}}\right)\right\}$ , where $\bm{e}_{i}$ denotes the $i^{th}$ standard unit vector. Given $\eta$ -approximate query access to $f$ , there exists a tester Test- $k$ -Linear (Algorithm 1) that, in $\widetilde{O}(k\log k+\frac{1}{\varepsilon})$ queries, guarantees:

$\blacksquare$

Completeness: If $f$ is a $k$ -linear function, 1 Accepts with probability $\geq 2/3$ .
$\blacksquare$

Soundness: If $f$ is $\varepsilon$ -far from all $k$ -linear functions, 1 Rejects w.p. $\geq 2/3$ .

Algorithm 1 Test-

k

-Linear.

Algorithm 1 uses two subroutines $\mathsf{FindInfBucket}$ (Algorithm 2) and $\mathsf{FindInfBuckets}$ (Algorithm 3). We will first present and analyze them in Section 5.1, and then analyze Algorithm 1 in Section 5.2.

A closely related (and efficiently testable) notion of additivity may be noted here.

Definition 5.2 (Additive function).

A function $f:A\to B$ is additive, if for all $x,y\in A$ , $f(x\oplus_{A}y)=f(x)\oplus_{B}f(y)$ , where $\oplus_{A}$ and $\oplus_{B}$ denote the bitwise-xor operations in $A$ and $B$ , respectively.

Over finite domains, additivity implies linearity. But over continuous domains, this isn’t always the case. However, for continuous functions, testing additivity suffices:

Fact 5.3 ([60, Section 5.2]).

For continuous functions, additivity is equivalent to linearity.

Algorithm 1 uses a query oracle to the self-corrected function, Approximate- $g$ . We now note the following results from [5, 7] about their approximate additivity tester.

Theorem 5.4 ([5, Theorem D.1], and [7, Theorem 3.3]).

Let $\alpha,\varepsilon>0$ , for $L>0$ , suppose $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is a function that is bounded in the ball $B(0,L)$ and $\mathcal{D}$ be an unknown $(\varepsilon/4,R)$ -concentrated distribution. There exists a one-sided error, $O(\frac{1}{\varepsilon})$ -query tester (ApproximateAdditivityTester) which with probability at least $99/100$ , distinguishes when $f$ is pointwise $\alpha$ -close to some additive function and when, for every additive function $h$ , $\Pr_{\bm{p}\sim\mathcal{D}}[|f(\bm{p})-h(\bm{p})|>O(Rn^{1.5}\alpha)]>\varepsilon$ .

Lemma 5.5 ([5, Lemma D.3 and D.6]).

If TestAdditivity $(f,3\alpha)$ accepts with probability at least $1/3$ , then $g$ is a $42\alpha$ -additive function inside the small ball $\operatorname{B}(\bm{0},r)$ , and furthermore, for every $\bm{p}\in\operatorname{B}(\bm{0},r)$ it holds that

\Pr_{\bm{x}\sim\mathcal{N}(\bm{0},I_{n})}[\left|g(\bm{p})-g_{\bm{x}}(\bm{p})% \right|\geq 12\alpha]<12/125.

Lemma 5.6 ([5, Lemma D.4 and D.5]).

If TestAdditivity( $f,3\alpha$ ) accepts with probability at least $1/3$ , then for every $\bm{p},\bm{q}\in\operatorname{B}(\bm{0},r)$ with $\|\bm{p}+\bm{q}\|_{2}\leq r$ , it holds that

\left|g(\bm{p}+\bm{q})-g(\bm{p})-g(\bm{q})\right|\leq 42\alpha.

The following lemma gives us a way to scale the closeness for degree- $d$ polynomials.

Lemma 5.7 ([5, Lemma 4.19]).

Let $R>r^{\prime}>0$ be any real numbers. If $g$ is pointwise $\eta$ -close to a degree- $d$ polynomial in $\operatorname{B}(\bm{0},r^{\prime})$ , then $g$ is pointwise $(12R/r^{\prime})^{d}\eta$ -close to a degree- $d$ polynomial on all points in $\operatorname{B}(\bm{0},R)$ .

Using Lemma 5.5, Lemma 5.7 and the structure of Approximate- $g$ subroutine, they bound the distance between $g$ and Approximate- $g$ .

Claim 5.8.

If TestAdditivity $(f,3\alpha)$ accepts with probability at least $1/3$ , then Approximate- $g$ is pointwise $6\alpha$ -close to $g$ , in the ball $\operatorname{B}(\bm{0},r)$ w.h.p.; i.e.,

\Pr_{\bm{p}\sim\mathcal{D}}[|g(\bm{p})-\textnormal{{Approximate}-}g(\bm{p})|% \leq 6\alpha(12R/r)\mid\bm{p}\in\operatorname{B}(\bm{0},R)]\geq 1-\varepsilon/4.

The following observation directly follows using the triangle inequality, along with the above claim and the notion of $\eta$ -approximate queries.

Observation 5.9.

If ApproximateAdditivityTester does not reject $f$ with probability at least $2/3$ , then following the description of ApproximateAdditivityTester, we have

\Pr_{\bm{p}\sim\mathcal{D}}[|f(\bm{p})-\textnormal{{Approximate}-}g(\bm{p})|% \leq 750Rn^{1.5}\alpha\mid\bm{p}\in\operatorname{B}(\bm{0},R)]\geq 1-\frac{% \varepsilon}{4}.

We will invoke them with $\mathcal{D}=\mathcal{N}(\bm{0},I_{n})$ , implying $R=2\sqrt{n}$ (from Fact 4.3).

5.1 Analyses of Subroutines

The subroutine $\mathsf{FindInfBucket}$ is presented in Algorithm 2.

Algorithm 2

\mathsf{FindInfBucket}

(

f, B, S

).

To analyze it, we need:

Definition 5.10 (Influential bucket for linear functions).

For a function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ , a bucket $B\subseteq[n]$ is said to be an influential bucket if there exists at least one variable $x_{i},i\in B$ , which is influential with respect to $f$ (i.e., $f(\bm{x})$ changes with a change in $x_{i}$ ). For a linear $f$ , with $f(\bm{x})\equiv\sum_{i\in[n]}a_{i}{x}_{i}$ , ${x}_{i}$ is influential w.r.t $f$ if and only if $a_{i}\neq 0$ , and hence $B$ is an influential bucket iff $a_{i}\neq 0$ for some $i\in B$ .

Claim 5.11 (Correctness of $\mathsf{FindInfBucket}$ ).

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ , with $f(\bm{x})=\sum_{i\in[n]}a_{i}{x}_{i}$ be given via an $\eta$ -approximate query $\tilde{f}$ , where $\eta\leq\frac{1}{100k^{2}}\min\limits_{k\in[n]:a_{k}\neq 0}|a_{k}|$ , $B=\{B_{1},\ldots,B_{r}\}$ be a partition of $[n]$ , and $\emptyset\neq S\subseteq[r]$ . Then $\mathsf{FindInfBucket}(f,B,S)$ (Algorithm 2) guarantees:

1.

If none of the buckets $\{B_{i},i\in S\}$ are influential, $\mathsf{FindInfBucket}(f,B,S)$ always returns $\emptyset$ and performs exactly $2$ queries to $f$ .
2.

Otherwise, with probability at least $1-8\lceil\log|S|\rceil^{2}/10k^{2}$ , $\mathsf{FindInfBucket}(f,B,S)$ returns $B_{j}$ for some $j\in S$ which is an influential bucket, and performs $\leq 8{\lceil{\lg(|S|)}\rceil}^{2}$ queries to $f$ .

Next we describe and analyze the subroutine $\mathsf{FindInfBuckets}$ (Algorithm 3).

Algorithm 3

\mathsf{FindInfBuckets}

(

\widetilde{f},B,X

).

Claim 5.12 (Correctness of $\mathsf{FindInfBuckets}$ ).

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ , with $f(\bm{x})=\sum_{i\in[n]}a_{i}{x}_{i}$ , be given via the $\eta$ -approximate query oracle $\tilde{f}$ , where $\eta\leq\frac{1}{100k^{2}}\min\limits_{k\in[n]:a_{k}\neq 0}|a_{k}|$ , and $\emptyset\neq X\subseteq[n]$ . Then $\mathsf{FindInfBuckets}(f,B,X)$ (Algorithm 3), in at most $64k\lceil\log(|X|)\rceil^{2}$ queries, guarantees:

(i)

If $f$ is $\ell$ -linear function for some $\ell>8k$ , then Algorithm 3 will return a set of $8k$ influential buckets in $f$ with probability at least $1-64\lceil\log|X|\rceil^{2}/10k$ .
(ii)

If $f$ is $\ell$ -linear function for some $\ell\leq 8k$ , then Algorithm 3 will return the set of all influential buckets in $f$ with probability at least $1-64\lceil\log|X|\rceil^{2}/10k$ .

5.2 Analysis of the $𝒌$ -linearity tester (Algorithm 1)

We are now ready to prove the main theorem of this section:

Proof of Theorem 5.1.

Completeness.

Since $f$ is a $k$ -linear function, following Theorem 5.4, we have: ApproximateAdditivityTester accepts $f$ , and hence by Lemma 5.6, $g$ is pointwise $42\eta$ -close to linearity in $\operatorname{B}(\bm{0},r)$ . Combined with Lemma 5.7, we get $g$ is pointwise $42\eta(12R/r)$ -close to linearity in $\operatorname{B}(\bm{0},R)$ . From Claim 5.8, we know that $g$ and Approximate- $g$ are pointwise $6\eta(12R/r)$ -close in $\operatorname{B}(\bm{0},R)$ with probability at least $1-\varepsilon/4$ . Using the triangle inequality, this implies that Approximate- $g$ is pointwise $48\eta(12R/r)$ -close to some linear function with probability $\geq 1-\varepsilon/4$ . Moreover, from Observation 5.9, we get: Approximate- $g$ is in fact pointwise $750Rn^{1.5}\eta$ -close to $f$ , with probability at least $1-\varepsilon/2$ . With $R=2\sqrt{n}$ , following the guarantee of Claim 5.12, ensured by our assumption on $\eta$ :

O(n^{2}\eta)\leq\frac{1}{100k^{2}}\min_{k\in[n]:a_{k}\neq 0}|a_{k}|\text{, or % equivalently }\eta\leq O\left(\min_{\begin{subarray}{c}i\in[n]:f(\bm{e}_{i})% \neq 0\end{subarray}}\frac{|f(\bm{e}_{i})|}{(nk)^{2}}\right),

we get that $\mathsf{FindInfBuckets}(\textnormal{{Approximate}-}$ g $,B,[r])$ will return at most $k$ -influential variables of $f$ with probability at least $1-128\lceil\log k\rceil^{2}/5k$ . Thus with probability at least $1-\varepsilon/2-128\lceil\log k\rceil^{2}/5k$ , Test- $k$ -Linear will Accept.

Soundness.

Let $f$ be $\varepsilon$ -far from $k$ -linearity. We will prove the contrapositive. We will show that if Test- $k$ -Linear does not reject $f$ with probability at least $1-\delta(\geq 2/3)$ , then $f$ is pointwise close to some $k$ -linear function, with non-zero probability.

Note that if ApproximateAdditivityTester rejects $f$ with probability $\geq 1-\delta$ , we are done. So, let us consider the case when ApproximateAdditivityTester accepts with probability $\geq\delta$ . As in the completeness proof, from Lemma 5.5, and Lemma 5.7, we know that $g$ is pointwise $42\eta(12R/r)$ -close to linearity in $\operatorname{B}(\bm{0},R)$ with probability at least $1-12/125$ , and from Claim 5.8, we have that $g$ and Approximate- $g$ are pointwise $6\eta(12R/r)$ -close in $\operatorname{B}(\bm{0},R)$ with probability at least $1-\varepsilon/4$ . This implies that Approximate- $g$ is pointwise $48\eta(12R/r)$ -close to some linear function with probability at least $1-\varepsilon/4-12/125$ . Again, from Observation 5.9, we get: Approximate- $g$ is pointwise $750Rn^{1.5}\eta$ -close to $f$ , with probability at least $1-\varepsilon/4$ , implying now $f$ must be pointwise $(48(12R/r)+750Rn^{1.5})\eta$ -close to linearity, with probability at least $1-\varepsilon/2-12/125$ . Note, here $R=2\sqrt{n}$ , and $r=1/50$ .

With our assumption on $\eta$ again ensuring the conditions for Claim 5.12 are met, i.e.,

(48(12R/r)+750Rn^{1.5})\eta\leq\frac{1}{100k^{2}}\min_{k\in[n]:a_{k}\neq 0}|a_% {k}|,

we get $\mathsf{FindInfBuckets}(\textnormal{{Approximate}-}$ g $,B,[r])$ will return at most $8k$ -influential variables of $f$ with probability at least $1-128\lceil\log k\rceil^{2}/5k$ .

Since Test- $k$ -Linear accepts $f$ with probability $\geq\delta$ , this implies that the total number of influential variables returned by $\mathsf{FindInfBuckets}$ is at most $k$ , with probability $\geq\delta$ . Combining the above, we conclude that $f$ is pointwise $(48(12R/r)+750Rn^{1.5})\eta$ -close to a $k$ -linear function, with probability at least $\delta-12/125-\varepsilon/2-128\lceil\log k\rceil^{2}/5k$ . This concludes the proof.

Query complexity.

From Theorem 5.4, we have: ApproximateAdditivityTester performs $O(\frac{1}{\varepsilon})$ queries. From Claim 5.12, we have: $\mathsf{FindInfBuckets}$ performs $\widetilde{O}(k\log k)$ queries. Combining them, we have: Test- $k$ -Linear performs $\widetilde{O}(k\log k+\frac{1}{\varepsilon})$ queries in total. $\hfill\blacktriangleleft$

6 $𝒌$ -Sparse Low Degree Testing

In this section, we present and analyze our sparse low degree tester (Algorithm 4).

Theorem 6.1 (Generalization of Theorem 2.7).

Let $\eta<\min\{\varepsilon,1/2^{2^{n}}\}$ . Given $\eta$ -approximate query access to $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ that is bounded in $\operatorname{B}(\bm{0},2d\sqrt{n})$ , there exists a tester Test- $k$ -Sparse (Algorithm 4) that performs $\widetilde{O}(d^{5}+\frac{d^{2}}{\varepsilon}+dk^{3})$ queries and guarantees:

$\blacksquare$

Completeness: If $f$ is a $k$ -sparse, degree- $d$ polynomial, then 4 Accepts with probability at least $1-\varepsilon/4$ .
$\blacksquare$

Soundness: If $f$ is $\varepsilon$ -far from all $k$ -sparse, degree- $d$ polynomials, then 4 Rejects with probability at least $2/3$ .

Algorithm 4 Test-

k

-Sparse.

We will prove Theorem 6.1 in Section 6.2, after developing the necessary machinery. Algorithm 4 first invokes ApproxLowDegreeTester to reject functions that are far from any low-degree polynomial. We record some useful claims about ApproxLowDegreeTester, and its subroutines (ApproxCharacterizationTest, ApproxQuery- $g$ and ApproxQuery- $g$ -InBall) from [5] and (its improvement in) [7]:

Theorem 6.2 ([7, Theorem 3.6]).

Let $d\in\mathbb{N}$ , for $L>0$ , $f:\mathbb{R}^{n}\to\mathbb{R}$ be bounded in the ball $\operatorname{B}(\bm{0},L)$ , and for $\varepsilon\in(0,1),R>0$ , let $\mathcal{D}$ be an $(\varepsilon/4,R)$ -concentrated distribution. For $\alpha>0,\beta\geq 2^{(2n)^{O(d)}}(R/L)^{d}\alpha$ , given $\alpha$ -approximate query access to $f$ , and sampling access to $\mathcal{D}$ , there is an one-sided error, $O(d^{5}+\frac{d^{2}}{\varepsilon})$ -query ApproxLowDegreeTester which, distinguishes between the case when $f$ is pointwise $\alpha$ -close to some degree- $d$ polynomial and the case when, for every degree- $d$ polynomial $h\colon\mathbb{R}^{n}\to\mathbb{R}$ , $\Pr_{\bm{p}\sim\mathcal{D}}[|f(\bm{p})-h(\bm{p})|>\beta]>\varepsilon$ .

Lemma 6.3 ([5, Lemma 4.4]).

Let $r=(4d)^{-6}$ , $\delta=2^{d+1}\alpha$ , and $R>r$ . If ApproxCharacterizationTest fails with probability at most $2/3$ , then $g$ is pointwise $2^{(2n)^{45d}}(R/L)^{d}\delta$ -close to a degree- $d$ polynomial in $\operatorname{B}(\bm{0},2dR\sqrt{n}/L)$ . Furthermore, $\forall\;\bm{p}\in\operatorname{B}(\bm{0},2dR\sqrt{n}/L)$ , ApproxQuery- $g$ ( $\bm{p}$ ) well approximates $g(\bm{p})$ w.h.p., i.e.,

\Pr_{\bm{p}\sim\mathcal{D}}\Big[|g(\bm{p})-\textnormal{{ApproxQuery}-}g(\bm{p}% )|\leq\Big(\frac{24dR\sqrt{n}}{Lr}\Big)^{d}2^{d+4}\delta\Big]\geq 1-\frac{% \varepsilon}{4}.

To invoke these results, we assume: (i) $f$ is bounded in $\operatorname{B}(\bm{0},R)$ , i.e., we set $L=R$ , and (ii) $\alpha=\eta$ . Additionally, since we work over standard Gaussians, we set $R=2d\sqrt{n}$ .

Testing sparsity of polynomials given exact query access.

As a preliminary, we design an algorithm for testing sparsity of polynomial functions $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ , by extending the machinery of Hankel matrices developed in [52, 11] to the real numbers. Moreover, ˜2.6 can be used to exactly determine whether a polynomial $f$ is $(\leq k)$ -sparse.

Lemma 6.4.

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a polynomial function (of any degree). Given exact query access to $f$ , there is an algorithm that makes $2k+1$ queries to $f$ , and exactly tests whether $\|f\|_{0}\leq k$ (returns Accept), or $\|f\|_{0}>k$ (returns Reject) with error probability $0$ .

6.1 Testing sparsity of polynomials given approximate query access

Now, instead of exact query access, we have $\eta$ -approximate query $\tilde{f}$ to a polynomial $f$ , which guarantees $|\tilde{f}(\bm{z})-f(\bm{z})|\leq\eta$ for all points $\bm{z}\in\mathbb{R}^{n}$ , giving us:

Observation 6.5.

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ and let $\tilde{f}$ be an $\eta$ -approximate query oracle to $f$ . Then for any $t\geq 1$ and $\bm{u}\in\mathbb{R}^{n}$ , we can express $H_{t}(\tilde{f},\bm{u})=H_{t}(f,\bm{u})+E_{t}(\bm{u})$ , where $E_{t}(\bm{u})$ is a Hankel-structured noise matrix, s.t. $\|E_{t}(\bm{u})\|_{\infty}\leq\eta$ , and $\|E_{t}(\bm{u})\|_{\rm op}\leq\eta t$ .

We now present and analyze the correctness of Algorithm 5, using Theorem 2.12:

Algorithm 5 Approx-Poly-Sparsity-Test: Approx-query sparsity test for polynomials.

Theorem 6.6 (Sparsity testing with approximate queries).

Given $\eta$ -approximate query access $\widetilde{f}$ to a polynomial $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ of total degree $\leq d$ , assuming $\eta\leq\frac{\left(\mathrm{coeff}_{d_{Q}}(Q)\right)^{\frac{1}{2}}}{(2(k+1))2^% {\Theta(k^{3}d)}\left(\sigma_{\max}(H_{\bm{u}})\right)^{k}}$ , wherein $H_{\bm{u}}=H_{k+1}(f,\bm{u}),Q_{\bm{u}}=(\det(H_{\bm{u}}))^{2},d_{Q}=\deg(Q)$ , and $\mathrm{coeff}^{2}_{d_{Q}}(Q)$ is as in Theorem 4.6, Approx-Poly-Sparsity-Test (Algorithm 5), in $O(dk^{3})$ queries, guarantees:

(i)

If $f$ has sparsity at most $k$ , the algorithm always Accepts, and
(ii)

If $f$ has sparsity $>k$ , the algorithm Rejects with probability at least $\frac{2}{3}$ .

6.2 Analysis of $𝒌$ -Sparsity Low Degree Tester

We are now ready to analyze our sparse low degree tester (Algorithm 4).

Proof of Theorem 6.1.

Let us start with completeness. Completeness: Since $f$ is a $k$ -sparse, degree- $d$ polynomial, from Theorem 6.2, we have: Approx-Low-Degree-Tester always accepts $f$ , and hence, from Lemma 6.3, we have that $g$ is pointwise $2^{(2n)^{45d}}R^{d}2^{d+1}\eta$ -close to a degree- $d$ polynomial, say $h$ , in $\operatorname{B}(\bm{0},R)$ . Moreover,

\Pr_{\bm{p}\sim\mathcal{D}}\Big[|g(\bm{p})-\textnormal{{ApproxQuery}-}g(\bm{p}% )|\leq\Big(\frac{24d\sqrt{n}}{r}\Big)^{d}2^{2d+5}\eta\mid\bm{p}\in% \operatorname{B}(\bm{0},2d\sqrt{n})\Big]\geq 1-\frac{\varepsilon}{2}.

\implies\Pr_{\bm{p}\sim\mathcal{D}}\Big[|h(\bm{p})-\textnormal{{ApproxQuery}-}% g(\bm{p})|\leq\left(\Big(\frac{24d\sqrt{n}}{r}\Big)^{d}2^{2d+5}+2^{(2n)^{45d}}% R^{d}2^{d+1}\right)\eta\Big]\geq 1-\frac{\varepsilon}{4}.

(1)

By setting $\eta=1/2^{2^{n}}$ , the conditions of Theorem 6.6 are met, giving us that Approx-Poly-Sparsity-Test(ApproxQuery- $g$ ) (Algorithm 5) will Accept with probability $\geq 1-\varepsilon/4$ . So with probability at least $1-\varepsilon/4$ , Test- $k$ -Sparse (Algorithm 4) will accept $f$ .

Soundness.

Let $f$ be $\varepsilon$ -far from all $k$ -sparse, degree- $d$ polynomials. We will show that if Algorithm 4 accepts with probability at least $1/3$ , then $f$ must be $\varepsilon$ -close to some $k$ -sparse, degree- $d$ polynomial. From the premise, Approx-Low-Degree-Tester also accepts $f$ with probability at least $1/3$ . Then, as in completeness, from Lemma 6.3, we have: $g$ is pointwise $2^{(2n)^{45d}}R^{d}2^{d+1}\eta$ -close to some degree- $d$ polynomial, say $h(\bm{x})=\sum_{\|\bm{M}_{i}\|_{1}\leq d}a_{i}\bm{M}_{i}(\bm{x})$ , i.e., for all $\bm{p}\in\operatorname{B}(\bm{0},R)$ , $|g(\bm{p})-h(\bm{p})|\leq 2^{(2n)^{45d}}R^{d}2^{d+1}\eta$ , and (1) still holds.

From the premise, Approx-Poly-Sparsity-Test(ApproxQuery-g) (Algorithm 5) does not reject with probability $\geq 1/3$ . In this case, as long as the closeness of ApproxQuery-g and $h$ satisfies the assumption in Theorem 6.6, $h$ will be $k$ -sparse. The assumption is:

(3\cdot 2^{(2n)^{45d}}+1)\eta\leq\frac{\left(\mathrm{coeff}_{d_{Q}}(Q)\right)^% {\frac{1}{2}}}{(2(k+1))2^{\Theta(k^{3}d)}\left(\sigma_{\max}(H_{\bm{u}})\right% )^{k}},

(2)

where $H_{\bm{u}}=H_{k+1}(h,\bm{u}),Q({\bm{u}})=(\det(H_{\bm{u}}))^{2},d_{Q}=\deg(Q)$ , $\mathrm{coeff}^{2}_{d_{Q}}(Q)\leq(\|\bm{a}\|_{2}^{2}n^{d})^{(k+1)}((k+1)!)^{2}$ , and $\sigma_{\max}(H_{\bm{u}})$ may be bounded using Theorem 2.12 (with $\gamma=0.01,t=k+1$ ), i.e.,

\Pr_{\bm{u}\sim\mathcal{N}(\bm{0},I_{n})}\left[\sigma_{\max}(H_{\bm{u}})\geq\|% \bm{a}\|_{2}^{2}\left(2^{d/2}\lceil d/2\rceil!+\sqrt{\frac{k}{0.01}}2^{d/2}% \sqrt{d!}\right)^{2(k+1)}\right]\leq 0.01.

So, with probability at least $0.99$ , $\sigma_{\max}(H_{\bm{u}})\leq\|\bm{a}\|_{2}^{2}\left(2^{d/2}\lceil d/2\rceil!+% 10\sqrt{k}2^{d/2}\sqrt{d!}\right)^{2(k+1)}$ . Plugging these into (2), we observe, setting $\eta\leq 1/2^{2^{n}}$ satisfies it, implying that $f$ is $\varepsilon$ -close to some $k$ -sparse, degree- $d$ polynomial.

Query complexity.

The query complexity of Algorithm 4 consists of two parts:

$\blacksquare$

query complexity of ApproxLowDegreeTester which is $O(d^{5}+d^{2}/\varepsilon)$ (from Theorem 6.2), and
$\blacksquare$

the query complexity of Approx-Poly-Sparsity-Test (Algorithm 5) which is at most $O(dk^{3})$ (from Theorem 6.6).

Combining the above, we have: Algorithm 4 performs $O(d^{5}+d^{2}/\varepsilon+dk^{3})$ queries in total. $\hfill\blacktriangleleft$

7 $𝒌$ -Junta Testing

In this section, we present and analyze our $k$ -junta tester.

Theorem 7.1 (Generalization of Theorem 2.10).

Let $\varepsilon\in(0,1)$ , $\eta<\min\{\tfrac{\varepsilon}{16k^{2}},O(\frac{1}{k^{2}\log^{2}k})\}$ . Given $\eta$ -approximate query access to an unknown function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ that is bounded in $\operatorname{B}(\bm{0},2\sqrt{n})$ , there exists a one-sided error tester Test- $k$ -Junta (Algorithm 6) that performs $\widetilde{O}((k\log k)/\varepsilon)$ queries and guarantees:

$\blacksquare$

Completeness: If $f$ is a $k$ -junta, then 6 always Accepts.
$\blacksquare$

Soundness: If $f$ is $\varepsilon$ -far from all $k$ -juntas, then 6 Rejects w.p. $\geq 2/3$ .

Algorithm 6 Test-

k

-Junta.

In order to prove Theorem 7.1, we first build some machinery, and then analyze Algorithm 6 and its subroutine (Algorithm 2 for juntas). Let us start with the notion of influence.

Definition 7.2 (Influence).

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a function. For any set $S\subseteq[n]$ , the influence of $f$ over $S$ with respect to a distribution $\mathcal{D}$ over $\mathbb{R}^{n}$ is defined as follows:

\mathsf{Infl}_{f}(S)=\mathop{\mathbb{E}}_{\bm{x},\bm{y}\sim\mathcal{D}}\left[% \left|f(\bm{y})-f(\bm{x}_{S}\bm{y}_{\overline{S}})\right|\right].

We first prove a structural result. Let $\mathcal{J}_{k}$ denote the set of all $k$ -juntas on $n$ variables.

Theorem 7.3.

If $\mathsf{dist}(f,\mathcal{J}_{k})\geq\varepsilon$ , then $\forall S\subseteq[n]:|S|\leq k$ , with $\overline{S}\triangleq[n]\setminus S$ , $\mathsf{Infl}_{f}(\overline{S})\geq\varepsilon$ .

Next we prove a lemma that connects the influence of the union of two sets of variables with the influences of individual sets.

Lemma 7.4 (Sub-additivity of Influence).

For every $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ , and any $S,T\subseteq[n]$ ,

\displaystyle\max\{\mathsf{Infl}_{f}(S),\mathsf{Infl}_{f}(T)\}\leq\mathsf{Infl% }_{f}(S\cup T)\leq\mathsf{Infl}_{f}(S)+\mathsf{Infl}_{f}(T).

Next we show, if $f$ is far from being a $k$ -junta, the influence of $\overline{S}$ in Algorithm 6 (i.e. all buckets not yet identified as influential) is high, unless we identify more than $k$ parts.

Lemma 7.5.

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ and $\mathcal{B}=\{B_{1},\ldots,B_{r}\}$ be a random partition of $[n]$ , for $r=\Theta(k^{2})$ . If $\mathsf{dist}(f,\mathcal{J}_{k})\geq\varepsilon$ , with probability $\geq 99/100$ over the randomness of the partition, we have $\mathsf{Infl}_{f}(\overline{S})\geq\varepsilon/4$ for any $S\subseteq[n]$ which is a union of at most $k$ parts of $\mathcal{B}$ .

7.1 Proof of correctness of Test- $k$ -Junta

As Algorithm 6 invokes Algorithm 2, we first prove its correctness for juntas.

Definition 7.6 (Influential variables and buckets).

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ , and $k\in\mathbb{N}$ . A variable ${x}_{i},i\in[n]$ is influential with respect to $f$ , if for some $\bm{x}\triangleq(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}$ , only changing ${x}_{i}$ changes the value of $f(\bm{x})$ . A bucket $B\subseteq[n]$ is said to be influential if it contains the index of at least one influential variable, and non-influential otherwise.

Let $\mathcal{E}$ denote the event that for $\bm{x},\bm{y}\sim\mathcal{N}(\bm{0},I_{n})$ , $\bm{x},\bm{y}\in\operatorname{B}(\bm{0},2\sqrt{n})$ . By Fact 4.3, we have $\Pr_{\bm{x},\bm{y}\sim\mathcal{N}(\bm{0},I_{n})}[\overline{\mathcal{E}}]=\Pr_{% \bm{x},\bm{y}\sim\mathcal{N}(\bm{0},I_{n})}[\bm{x},\bm{y}\not\in\operatorname{% B}(\bm{0},2\sqrt{n})\leq 0.01$ . Let

\kappa\triangleq\mathop{\text{min}}_{\begin{subarray}{c}V\subseteq[n]\\ V\mbox{ is influential}\end{subarray}}\left\{\mathop{\mathbb{E}}_{\bm{x},\bm{y% }\sim\mathcal{N}(\bm{0},I_{n})}\left[|f({\bm{x}}_{V}{\bm{y}}_{\overline{V}})-f% (\bm{y})|\mid\mathcal{E}\right]\right\}.

We use $\mathsf{FindInfBucket}$ (Algorithm 2) for testing $k$ -linearity as well. However, the proof of correctness of Algorithm 2 in Section 5, presented in Claim 5.11, holds only for linear functions, which may not be the case in general. So, we prove the same for juntas too:

Claim 7.7 (Correctness of Algorithm 2 for juntas).

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be given via the $\eta$ -approximate query $\tilde{f}$ , where $\eta\leq\min\{\kappa/4,1/(1000k^{2}\log^{2}k)\}$ , $B=\{B_{1},\ldots,B_{r}\}$ be a partition of $[n]$ , and $\emptyset\neq S\subseteq[r]$ . With $\kappa\geq\max\{2\|f\|_{\infty,\operatorname{B}(\bm{0},2\sqrt{n})},\varepsilon% /(4k^{2})\}$ , we have:

1.

If none of the $B_{i}$ ’s are influential, $\mathsf{FindInfBucket}(f,B,S)$ always returns $\emptyset$ and performs exactly $2$ queries to $f$ .
2.

Otherwise, with probability at least $1-16\eta\lceil\log|S|\rceil^{2}/\kappa$ , $\mathsf{FindInfBucket}(f,B,S)$ returns $B_{j}$ for some $j\in S$ which is $\kappa$ -influential and performs $\leq 8{\lceil{\lg(|S|)}\rceil}^{2}$ queries to $f$ .

We are now ready to prove the main theorem of this section:

Proof of Theorem 7.1.

Let us start with the completeness proof.

Completeness.

The argument of completeness of Algorithm 6 holds easily, as when $f$ is a $k$ -junta, at most $k$ of the buckets in the random partition $\mathcal{B}$ will be influential. From Claim 7.7, we get that each execution of the $\mathsf{For}$ loop increments $I$ by: either the index of an influential bucket (if it finds one), or nothing, while also removing the bucket from future loop executions. Hence after all its executions, $|I|$ is incremented at most $k$ times, falsifying the check in line 6, making $f$ Accept.

Soundness.

Here our goal is to prove if $f$ is $\varepsilon$ -far from all $k$ -juntas, then Algorithm 6 rejects it with probability $\geq 2/3$ . In particular, if $f$ is $\varepsilon$ -far from being $k$ -junta, and $S$ is the union of at most $k$ -parts of $\mathcal{I}$ , then Line 7 of Algorithm 6 will be satisfied w.h.p.

By Lemma 7.5, we have: if $|I|\leq k$ , $\mathsf{Infl}_{f}(S)\geq\varepsilon/4$ ( $S=[n]\setminus I$ in the execution of Algorithm 6). During the execution, when exactly $k$ influential buckets have been identified, $\mathsf{Infl}_{f}(S)\geq\varepsilon/4$ , $|S|=O(k^{2})-k=O(k^{2})$ , and thus, by Lemma 7.4, there must exist a bucket $B_{i},i\in S$ such that $\mathsf{Infl}_{f}(B_{i})\geq\varepsilon/(4k^{2})$ . This bucket will then be output by $\mathsf{FindInfBucket}(f,B,S)$ . So, until $k+1$ influential buckets have been identified, each invocation of $\mathsf{FindInfBucket}(f,B,S)$ in an execution of its $\mathsf{For}$ loop, returns an influential bucket with probability $\geq 1-64\eta\lceil\log k\rceil^{2}/\kappa$ . Treating the outcome of each invocation as a geometric random variable, we conclude: to recover at least $k+1$ such buckets with probability $\geq 2/3$ ,

k/\left(1-64\eta\lceil\log k\rceil^{2}/\kappa\right)=k+k\sum_{i=1}^{\infty}(64% \eta\lceil\log k\rceil^{2}/\kappa)^{i}=O(k/\varepsilon)

iterations of $\mathsf{For}$ loop suffice. When $|I|>k$ , in line 6, algorithm rejects with same probability.

Query Complexity.

From Claim 7.7, we know: each invocation of $\mathsf{FindInfBucket}(f,B,S)$ performs $\leq 4\log|S|$ queries to $f$ . With $O(k/\varepsilon)$ such invocations in total, and $|S|=r=O(k^{2})$ , the overall query complexity thus is $O((k\log k)/\varepsilon)$ . $\hfill\blacktriangleleft$

8 Lower Bounds

See 2.11 For proving the lower bounds in the exact query model (which covers approximate queries), we follow the approach of [19], i.e., we show the hardness of testing by reducing from Set-Disjointness problem, a canonical hard problem in the field of communication complexity. For brevity, we only present the lower bound argument for $k$ -linearity.

$\Omega(\frac{1}{\varepsilon})$ queries for linearity.

For any $\varepsilon\in(0,1)$ , it is a folklore result that distinguishing if a function $f$ is linear, or $\varepsilon$ -far from being linear in $\ell_{1}$ -distance, requires $\Omega(1/\varepsilon)$ queries [42].

$\Omega(d)$ queries for degree- $𝒅$ polynomial testing.

It is another folklore result that given a proximity parameter $\varepsilon\in(0,1)$ , $\Omega(d)$ queries are necessary to distinguish if an unknown function $f$ is a degree- $d$ polynomial, or a degree- $(d+1)$ (or $(d-1)$ ) polynomial (and hence, is $\varepsilon$ -far from all degree- $d$ polynomials) with probability at least $2/3$ .

To prove the $\Omega(k)$ query lower bound for $k$ -linearity, we use a reduction from Set-Disjointness which is known to require $\Omega(k)$ communication complexity [54].

Connection between Communication and Query complexity.

Consider two functions $f$ and $g$ , a property $\mathcal{P}$ , $h\triangleq f-g$ , and a communication problem $C_{h,\mathcal{P}}$ : Alice and Bob receive $f$ and $g$ , respectively, and they want to decide if $h\in\mathcal{P}$ , or $f$ is $\varepsilon$ -far from $\mathcal{P}$ . [19] (Lemma 2.2) proved that $\mathcal{R}(C_{h,\mathcal{P}})$ , the randomized communication complexity of $C_{h,\mathcal{P}}\leq 2Q(\mathcal{P})$ , the query complexity of deciding the property $\mathcal{P}$ .

Construction of the hard instances.

Given $A\subseteq[n]:|A|=k$ , Alice constructs a polynomial $f=\sum_{i\in A}{\bm{x}}_{i}$ . Similarly Bob, given $B\subseteq[n],|B|=k$ , constructs a polynomial $g=\sum_{i\in B}{\bm{x}}_{i}$ . Note that $f,g:\mathbb{R}^{n}\to\mathbb{R}$ . Let $h\triangleq f-g$ . If $|A\cap B|=1$ , $h$ would be a $(2k-2)$ linear function, whereas if $|A\cap B|=0$ , $h$ would be a $2k$ -linear function.

Lemma 8.1.

Let $f_{1}$ be a $(2k+2)$ -linear function, and $f_{2}$ be a $2k$ -linear function with coefficients from $\{0,1\}$ . Under the standard Gaussian distribution $\mathcal{N}(\bm{0},I_{n})$ , $f_{1}$ is $\Omega(1)$ -far from $f_{2}$ in $\ell_{1}$ -distance with probability at least $2/3$ .

References

[1] Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing reed-muller codes. IEEE Transactions on Information Theory, 51(11):4032–4039, 2005. doi:10.1109/TIT.2005.856958.
[2] Sigal Ar, Manuel Blum, Bruno Codenotti, and Peter Gemmell. Checking approximate computations over the reals. In Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing, pages 786–795, 1993. doi:10.1145/167088.167288.
[3] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, May 1998. doi:10.1145/278298.278306.
[4] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70–122, January 1998. doi:10.1145/273865.273901.
[5] Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, and Yuichi Yoshida. Low degree testing over the reals. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 738–792. SIAM, 2023. doi:10.1137/1.9781611977554.ch31.
[6] Vipul Arora, Arnab Bhattacharyya, Philips George John, and Sayantan Sen. Testing sparse functions over the reals. CoRR, abs/2603.28061, 2026. doi:10.48550/arXiv.2603.28061.
[7] Vipul Arora, Esty Kelman, and Uri Meir. On optimal testing of linearity. In Proceedings of the 2025 Symposium on Simplicity in Algorithms (SOSA), pages 65–76. SIAM, 2025. doi:10.1137/1.9781611978315.5.
[8] Maria-Florina Balcan, Eric Blais, Avrim Blum, and Liu Yang. Active property testing. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 21–30. IEEE, IEEE Computer Society, 2012. doi:10.1109/FOCS.2012.64.
[9] Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri. Optimal unateness testers for real-valued functions: Adaptivity helps. CoRR, abs/1703.05199, 2017. doi:10.48550/arXiv.1703.05199.
[10] Yiqiao Bao, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, and Nathan White. Testing noisy low-degree polynomials for sparsity, 2025. doi:10.48550/arXiv.2511.07835.
[11] Michael Ben-Or and Prasoon Tiwari. A deterministic algorithm for sparse multivariate polynominal interpolation (extended abstract). In Janos Simon, editor, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, STOC ’88, pages 301–309, New York, NY, USA, 1988. ACM. doi:10.1145/62212.62241.
[12] Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. L ${}_{\mbox{p}}$ -testing. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, STOC ’14, pages 164–173, New York, NY, USA, 2014. ACM. doi:10.1145/2591796.2591887.
[13] Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett. Every locally characterized affine-invariant property is testable. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 429–436, 2013. doi:10.1145/2488608.2488662.
[14] Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. Optimal testing of reed-muller codes. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 488–497. IEEE, 2010. doi:10.1109/FOCS.2010.54.
[15] Arnab Bhattacharyya and Yuichi Yoshida. Property Testing - Problems and Techniques. Springer, 2022. doi:10.1007/978-981-16-8622-1.
[16] Hadley Black, Iden Kalemaj, and Sofya Raskhodnikova. Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1–25:20, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2023.25.
[17] Eric Blais. Improved bounds for testing juntas. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 317–330. Springer, 2008. doi:10.1007/978-3-540-85363-3_26.
[18] Eric Blais. Testing juntas nearly optimally. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 151–158, 2009. doi:10.1145/1536414.1536437.
[19] Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. computational complexity, 21:311–358, 2012. doi:10.1007/s00037-012-0040-x.
[20] Eric Blais and Daniel Kane. Tight bounds for testing k-linearity. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 435–446. Springer, 2012. doi:10.1007/978-3-642-32512-0_37.
[21] Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Lower bounds for testing properties of functions over hypergrid domains. In 2014 IEEE 29th Conference on Computational Complexity (CCC), pages 309–320. IEEE, 2014. doi:10.1109/CCC.2014.38.
[22] Eric Blais, Amit Weinstein, and Yuichi Yoshida. Partially symmetric functions are efficiently isomorphism testable. SIAM Journal on Computing, 44(2):411–432, 2015. doi:10.1137/140971877.
[23] Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of Data Science. Cambridge University Press, 2020. doi:10.1017/9781108755528.
[24] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 73–83. ACM, 1990. doi:10.1145/100216.100225.
[25] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci., 47(3):549–595, 1993. doi:10.1016/0022-0000(93)90044-W.
[26] Nader H Bshouty. An optimal tester for k-linear. Theoretical Computer Science, 950:113759, 2023. doi:10.1016/j.tcs.2023.113759.
[27] Anthony Carbery and James Wright. Distributional and $L^{q}$ Norm Inequalities for Polynomials over Convex Bodies in $\mathbb{R}^{n}$ . Mathematical Research Letters, 8:233–248, 2001.
[28] Deeparnab Chakrabarty and C. Seshadhri. Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 419–428. ACM, 2013. doi:10.1145/2488608.2488661.
[29] Xi Chen, Adam Freilich, Rocco A. Servedio, and Timothy Sun. Sample-based high-dimensional convexity testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 37:1–37:20, 2017. doi:10.4230/LIPIcs.APPROX-RANDOM.2017.37.
[30] Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie. Settling the query complexity of non-adaptive junta testing. J. ACM, 65(6):40:1–40:18, 2018. doi:10.1145/3213772.
[31] Hana Chockler and Dan Gutfreund. A lower bound for testing juntas. Information Processing Letters, 90(6):301–305, 2004. doi:10.1016/j.ipl.2004.01.023.
[32] Anindya De, Elchanan Mossel, and Joe Neeman. Is your function low dimensional? In Conference on Learning Theory, pages 979–993. PMLR, 2019. URL: http://proceedings.mlr.press/v99/de19a.html.
[33] Ilias Diakonikolas, Homin K Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A Servedio, and Andrew Wan. Testing for concise representations. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 549–558. IEEE, 2007. doi:10.1109/FOCS.2007.32.
[34] Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54(3):12, June 2007. doi:10.1145/1236457.1236459.
[35] Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky. Improved testing algorithms for monotonicity. In International Workshop on Randomization and Approximation Techniques in Computer Science, pages 97–108. Springer, 1999. doi:10.1007/978-3-540-48413-4_10.
[36] Regina C. Elandt. The folded normal distribution: Two methods of estimating parameters from moments. Technometrics, 3(4):551–562, 1961. URL: http://www.jstor.org/stable/1266561.
[37] Funda Ergün, S Ravi Kumar, and Ronitt Rubinfeld. Checking approximate computations of polynomials and functional equations. SIAM Journal on Computing, 31(2):550–576, 2001. doi:10.1137/S0097539798337613.
[38] Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy. Approximating clique is almost np-complete (preliminary version). In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October 1-4, 1991, pages 2–12. IEEE Computer Society, 1991. doi:10.1109/SFCS.1991.185341.
[39] Renato Ferreira Pinto Jr. Directed Poincaré Inequalities and L¹ Monotonicity Testing of Lipschitz Functions. In Nicole Megow and Adam Smith, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023), volume 275 of Leibniz International Proceedings in Informatics (LIPIcs), pages 61:1–61:18, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.APPROX/RANDOM.2023.61.
[40] Renato Ferreira Pinto Jr. Directed isoperimetry and monotonicity testing: A dynamical approach. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 2295–2305. IEEE, 2024. doi:10.1109/FOCS61266.2024.00134.
[41] Eldar Fischer. The art of uninformed decisions. Bull. EATCS, 75:97, 2001.
[42] Eldar Fischer. A basic lower bound for property testing, 2024. doi:10.48550/arXiv.2403.04999.
[43] Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky. Testing juntas. Journal of Computer and System Sciences, 68(4):753–787, 2004. doi:10.1016/j.jcss.2003.11.004.
[44] Noah Fleming and Yuichi Yoshida. Distribution-free testing of linear functions on $\mathbb{R}^{n}$ . In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, Seattle, Washington, USA, January 12-14, 2020, volume 151 of LIPIcs, pages 22:1–22:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.ITCS.2020.22.
[45] Katalin Friedl and Madhu Sudan. Some improvements to total degree tests. In Proceedings Third Israel Symposium on the Theory of Computing and Systems, pages 190–198. IEEE, 1995. doi:10.1109/ISTCS.1995.377032.
[46] Peter Gemmell, Richard Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson. Self-testing/correcting for polynomials and for approximate functions. In STOC, volume 91, pages 32–42. Citeseer, 1991. doi:10.1145/103418.103429.
[47] Itay Glazer and Dan Mikulincer. Anti-concentration of polynomials: Dimension-free covariance bounds and decay of fourier coefficients. Journal of Functional Analysis, 283(9):109639, 2022. doi:10.1016/j.jfa.2022.109639.
[48] O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. In Proceedings of 37th Conference on Foundations of Computer Science, pages 339–348, 1996. doi:10.1109/SFCS.1996.548493.
[49] Oded Goldreich. On testing computability by small width obdds. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, pages 574–587. Springer, 2010. doi:10.1007/978-3-642-15369-3_43.
[50] Oded Goldreich. Introduction to property testing. Cambridge University Press, 2017. doi:10.1017/9781108135252.
[51] Parikshit Gopalan, Ryan O’Donnell, Rocco A Servedio, Amir Shpilka, and Karl Wimmer. Testing fourier dimensionality and sparsity. SIAM Journal on Computing, 40(4):1075–1100, 2011. doi:10.1137/100785429.
[52] Elena Grigorescu, Kyomin Jung, and Ronitt Rubinfeld. A local decision test for sparse polynomials. Inf. Process. Lett., 110(20):898–901, 2010. doi:10.1016/j.ipl.2010.07.012.
[53] Shirley Halevy and Eyal Kushilevitz. Distribution-free property-testing. SIAM Journal on Computing, 37(4):1107–1138, 2007. doi:10.1137/050645804.
[54] Johan Håstad and Avi Wigderson. The randomized communication complexity of set disjointness. Theory of Computing, 3(1):211–219, 2007. doi:10.4086/toc.2007.v003a011.
[55] Roger A. Horn and Charles R. Johnson. Topics in matrix analysis. Cambridge University Press, 1991. doi:10.1017/CBO9780511840371.
[56] Roger A. Horn and Charles R. Johnson. Matrix Analysis, 2nd Ed. Cambridge University Press, 2012. doi:10.1017/CBO9781139020411.
[57] Charanjit S Jutla, Anindya C Patthak, Atri Rudra, and David Zuckerman. Testing low-degree polynomials over prime fields. Random Structures & Algorithms, 35(2):163–193, 2009. doi:10.1002/rsa.20262.
[58] Tali Kaufman and Dana Ron. Testing polynomials over general fields. SIAM Journal on Computing, 36(3):779–802, 2006. doi:10.1137/S0097539704445615.
[59] Pravesh Kothari, Amir Nayyeri, Ryan O’Donnell, and Chenggang Wu. Testing surface area. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1204–1214. SIAM, SIAM, 2014. doi:10.1137/1.9781611973402.89.
[60] Marek Kuczma. An Introduction to the Theory of Functional Equations and Inequalities. Birkhäuser Basel, 2009.
[61] Kevin Matulef, Ryan O’Donnell, Ronitt Rubinfeld, and Rocco A Servedio. Testing halfspaces. SIAM Journal on Computing, 39(5):2004–2047, 2010. doi:10.1137/070707890.
[62] Kevin Matulef, Ryan O’Donnell, Ronitt Rubinfeld, and Rocco Servedio. Testing (subclasses of) halfspaces. In Property testing: current research and surveys, pages 334–340. Springer, 2010. doi:10.1007/978-3-642-16367-8_27.
[63] Kevin Matulef, Ryan O’Donnell, Ronitt Rubinfeld, and Rocco A Servedio. Testing $\pm$ 1-weight halfspace. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 646–657. Springer, 2009. doi:10.1007/978-3-642-03685-9_48.
[64] Joe Neeman. Testing surface area with arbitrary accuracy. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 393–397. ACM, 2014. doi:10.1145/2591796.2591807.
[65] Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. Journal of Computer and System Sciences, 72(6):1012–1042, 2006. doi:10.1016/j.jcss.2006.03.002.
[66] Michal Parnas, Dana Ron, and Alex Samorodnitsky. Testing basic boolean formulae. SIAM Journal on Discrete Mathematics, 16(1):20–46, 2002. doi:10.1137/S0895480101407444.
[67] Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability pcp characterization of np. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 475–484, 1997. doi:10.1145/258533.258641.
[68] Dana Ron. Algorithmic and analysis techniques in property testing. Found. Trends Theor. Comput. Sci., 2009. doi:10.1561/0400000029.
[69] Dana Ron et al. Property testing: A learning theory perspective. Foundations and Trends® in Machine Learning, 1(3):307–402, 2008. doi:10.1561/2200000004.
[70] Ronitt Rubinfeld and Madhu Sudan. Self-Testing Polynomial Functions Efficiently and Over Rational Domains. In Proceedings of the 3rd Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms (SODA), pages 23–32, 1992. URL: http://dl.acm.org/citation.cfm?id=139404.139410.
[71] Ronitt Rubinfeld and Madhu Sudan. Robust Characterizations of Polynomials with Applications to Program Testing. SIAM Journal on Computing, 25(2):252–271, 1996. doi:10.1137/S0097539793255151.
[72] Mert Sağlam. Near Log-Convexity of Measured Heat in (Discrete) Time and Consequences. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 967–978. IEEE Computer Society, 2018. doi:10.1109/FOCS.2018.00095.
[73] Alex Samorodnitsky. Low-degree tests at large distances. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 506–515, 2007. doi:10.1145/1250790.1250864.

[bib.bib1] [1] Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing reed-muller codes. IEEE Transactions on Information Theory, 51(11):4032–4039, 2005. doi:10.1109/TIT.2005.856958.

[bib.bib2] [2] Sigal Ar, Manuel Blum, Bruno Codenotti, and Peter Gemmell. Checking approximate computations over the reals. In Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing, pages 786–795, 1993. doi:10.1145/167088.167288.

[bib.bib3] [3] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, May 1998. doi:10.1145/278298.278306.

[bib.bib4] [4] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70–122, January 1998. doi:10.1145/273865.273901.

[bib.bib5] [5] Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, and Yuichi Yoshida. Low degree testing over the reals. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 738–792. SIAM, 2023. doi:10.1137/1.9781611977554.ch31.

[bib.bib6] [6] Vipul Arora, Arnab Bhattacharyya, Philips George John, and Sayantan Sen. Testing sparse functions over the reals. CoRR, abs/2603.28061, 2026. doi:10.48550/arXiv.2603.28061.

[bib.bib7] [7] Vipul Arora, Esty Kelman, and Uri Meir. On optimal testing of linearity. In Proceedings of the 2025 Symposium on Simplicity in Algorithms (SOSA), pages 65–76. SIAM, 2025. doi:10.1137/1.9781611978315.5.

[bib.bib8] [8] Maria-Florina Balcan, Eric Blais, Avrim Blum, and Liu Yang. Active property testing. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 21–30. IEEE, IEEE Computer Society, 2012. doi:10.1109/FOCS.2012.64.

[bib.bib9] [9] Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri. Optimal unateness testers for real-valued functions: Adaptivity helps. CoRR, abs/1703.05199, 2017. doi:10.48550/arXiv.1703.05199.

[bib.bib10] [10] Yiqiao Bao, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, and Nathan White. Testing noisy low-degree polynomials for sparsity, 2025. doi:10.48550/arXiv.2511.07835.

[bib.bib11] [11] Michael Ben-Or and Prasoon Tiwari. A deterministic algorithm for sparse multivariate polynominal interpolation (extended abstract). In Janos Simon, editor, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, STOC ’88, pages 301–309, New York, NY, USA, 1988. ACM. doi:10.1145/62212.62241.

[bib.bib12] [12] Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. L ${}_{\mbox{p}}$ -testing. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, STOC ’14, pages 164–173, New York, NY, USA, 2014. ACM. doi:10.1145/2591796.2591887.

[bib.bib13] [13] Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett. Every locally characterized affine-invariant property is testable. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 429–436, 2013. doi:10.1145/2488608.2488662.

[bib.bib14] [14] Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. Optimal testing of reed-muller codes. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 488–497. IEEE, 2010. doi:10.1109/FOCS.2010.54.

[bib.bib15] [15] Arnab Bhattacharyya and Yuichi Yoshida. Property Testing - Problems and Techniques. Springer, 2022. doi:10.1007/978-981-16-8622-1.

[bib.bib16] [16] Hadley Black, Iden Kalemaj, and Sofya Raskhodnikova. Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1–25:20, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2023.25.

[bib.bib17] [17] Eric Blais. Improved bounds for testing juntas. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 317–330. Springer, 2008. doi:10.1007/978-3-540-85363-3_26.

[bib.bib18] [18] Eric Blais. Testing juntas nearly optimally. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 151–158, 2009. doi:10.1145/1536414.1536437.

[bib.bib19] [19] Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. computational complexity, 21:311–358, 2012. doi:10.1007/s00037-012-0040-x.

[bib.bib20] [20] Eric Blais and Daniel Kane. Tight bounds for testing k-linearity. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 435–446. Springer, 2012. doi:10.1007/978-3-642-32512-0_37.

[bib.bib21] [21] Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev. Lower bounds for testing properties of functions over hypergrid domains. In 2014 IEEE 29th Conference on Computational Complexity (CCC), pages 309–320. IEEE, 2014. doi:10.1109/CCC.2014.38.

[bib.bib22] [22] Eric Blais, Amit Weinstein, and Yuichi Yoshida. Partially symmetric functions are efficiently isomorphism testable. SIAM Journal on Computing, 44(2):411–432, 2015. doi:10.1137/140971877.

[bib.bib23] [23] Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of Data Science. Cambridge University Press, 2020. doi:10.1017/9781108755528.

[bib.bib24] [24] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 73–83. ACM, 1990. doi:10.1145/100216.100225.

[bib.bib25] [25] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci., 47(3):549–595, 1993. doi:10.1016/0022-0000(93)90044-W.

[bib.bib26] [26] Nader H Bshouty. An optimal tester for k-linear. Theoretical Computer Science, 950:113759, 2023. doi:10.1016/j.tcs.2023.113759.

[bib.bib27] [27] Anthony Carbery and James Wright. Distributional and $L^{q}$ Norm Inequalities for Polynomials over Convex Bodies in $\mathbb{R}^{n}$ . Mathematical Research Letters, 8:233–248, 2001.

[bib.bib28] [28] Deeparnab Chakrabarty and C. Seshadhri. Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 419–428. ACM, 2013. doi:10.1145/2488608.2488661.

[bib.bib29] [29] Xi Chen, Adam Freilich, Rocco A. Servedio, and Timothy Sun. Sample-based high-dimensional convexity testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 37:1–37:20, 2017. doi:10.4230/LIPIcs.APPROX-RANDOM.2017.37.

[bib.bib30] [30] Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie. Settling the query complexity of non-adaptive junta testing. J. ACM, 65(6):40:1–40:18, 2018. doi:10.1145/3213772.

[bib.bib31] [31] Hana Chockler and Dan Gutfreund. A lower bound for testing juntas. Information Processing Letters, 90(6):301–305, 2004. doi:10.1016/j.ipl.2004.01.023.

[bib.bib32] [32] Anindya De, Elchanan Mossel, and Joe Neeman. Is your function low dimensional? In Conference on Learning Theory, pages 979–993. PMLR, 2019. URL: http://proceedings.mlr.press/v99/de19a.html.

[bib.bib33] [33] Ilias Diakonikolas, Homin K Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A Servedio, and Andrew Wan. Testing for concise representations. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 549–558. IEEE, 2007. doi:10.1109/FOCS.2007.32.

[bib.bib34] [34] Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54(3):12, June 2007. doi:10.1145/1236457.1236459.

[bib.bib35] [35] Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky. Improved testing algorithms for monotonicity. In International Workshop on Randomization and Approximation Techniques in Computer Science, pages 97–108. Springer, 1999. doi:10.1007/978-3-540-48413-4_10.

[bib.bib36] [36] Regina C. Elandt. The folded normal distribution: Two methods of estimating parameters from moments. Technometrics, 3(4):551–562, 1961. URL: http://www.jstor.org/stable/1266561.

[bib.bib37] [37] Funda Ergün, S Ravi Kumar, and Ronitt Rubinfeld. Checking approximate computations of polynomials and functional equations. SIAM Journal on Computing, 31(2):550–576, 2001. doi:10.1137/S0097539798337613.

[bib.bib38] [38] Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy. Approximating clique is almost np-complete (preliminary version). In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October 1-4, 1991, pages 2–12. IEEE Computer Society, 1991. doi:10.1109/SFCS.1991.185341.

[bib.bib39] [39] Renato Ferreira Pinto Jr. Directed Poincaré Inequalities and L¹ Monotonicity Testing of Lipschitz Functions. In Nicole Megow and Adam Smith, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023), volume 275 of Leibniz International Proceedings in Informatics (LIPIcs), pages 61:1–61:18, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.APPROX/RANDOM.2023.61.

[bib.bib40] [40] Renato Ferreira Pinto Jr. Directed isoperimetry and monotonicity testing: A dynamical approach. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 2295–2305. IEEE, 2024. doi:10.1109/FOCS61266.2024.00134.

[bib.bib41] [41] Eldar Fischer. The art of uninformed decisions. Bull. EATCS, 75:97, 2001.

[bib.bib42] [42] Eldar Fischer. A basic lower bound for property testing, 2024. doi:10.48550/arXiv.2403.04999.

[bib.bib43] [43] Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky. Testing juntas. Journal of Computer and System Sciences, 68(4):753–787, 2004. doi:10.1016/j.jcss.2003.11.004.

[bib.bib44] [44] Noah Fleming and Yuichi Yoshida. Distribution-free testing of linear functions on $\mathbb{R}^{n}$ . In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, Seattle, Washington, USA, January 12-14, 2020, volume 151 of LIPIcs, pages 22:1–22:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.ITCS.2020.22.

[bib.bib45] [45] Katalin Friedl and Madhu Sudan. Some improvements to total degree tests. In Proceedings Third Israel Symposium on the Theory of Computing and Systems, pages 190–198. IEEE, 1995. doi:10.1109/ISTCS.1995.377032.

[bib.bib46] [46] Peter Gemmell, Richard Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson. Self-testing/correcting for polynomials and for approximate functions. In STOC, volume 91, pages 32–42. Citeseer, 1991. doi:10.1145/103418.103429.

[bib.bib47] [47] Itay Glazer and Dan Mikulincer. Anti-concentration of polynomials: Dimension-free covariance bounds and decay of fourier coefficients. Journal of Functional Analysis, 283(9):109639, 2022. doi:10.1016/j.jfa.2022.109639.

[bib.bib48] [48] O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. In Proceedings of 37th Conference on Foundations of Computer Science, pages 339–348, 1996. doi:10.1109/SFCS.1996.548493.

[bib.bib49] [49] Oded Goldreich. On testing computability by small width obdds. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, pages 574–587. Springer, 2010. doi:10.1007/978-3-642-15369-3_43.

[bib.bib50] [50] Oded Goldreich. Introduction to property testing. Cambridge University Press, 2017. doi:10.1017/9781108135252.

[bib.bib51] [51] Parikshit Gopalan, Ryan O’Donnell, Rocco A Servedio, Amir Shpilka, and Karl Wimmer. Testing fourier dimensionality and sparsity. SIAM Journal on Computing, 40(4):1075–1100, 2011. doi:10.1137/100785429.

[bib.bib52] [52] Elena Grigorescu, Kyomin Jung, and Ronitt Rubinfeld. A local decision test for sparse polynomials. Inf. Process. Lett., 110(20):898–901, 2010. doi:10.1016/j.ipl.2010.07.012.

[bib.bib53] [53] Shirley Halevy and Eyal Kushilevitz. Distribution-free property-testing. SIAM Journal on Computing, 37(4):1107–1138, 2007. doi:10.1137/050645804.

[bib.bib54] [54] Johan Håstad and Avi Wigderson. The randomized communication complexity of set disjointness. Theory of Computing, 3(1):211–219, 2007. doi:10.4086/toc.2007.v003a011.

[bib.bib55] [55] Roger A. Horn and Charles R. Johnson. Topics in matrix analysis. Cambridge University Press, 1991. doi:10.1017/CBO9780511840371.

[bib.bib56] [56] Roger A. Horn and Charles R. Johnson. Matrix Analysis, 2nd Ed. Cambridge University Press, 2012. doi:10.1017/CBO9781139020411.

[bib.bib57] [57] Charanjit S Jutla, Anindya C Patthak, Atri Rudra, and David Zuckerman. Testing low-degree polynomials over prime fields. Random Structures & Algorithms, 35(2):163–193, 2009. doi:10.1002/rsa.20262.

[bib.bib58] [58] Tali Kaufman and Dana Ron. Testing polynomials over general fields. SIAM Journal on Computing, 36(3):779–802, 2006. doi:10.1137/S0097539704445615.

[bib.bib59] [59] Pravesh Kothari, Amir Nayyeri, Ryan O’Donnell, and Chenggang Wu. Testing surface area. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1204–1214. SIAM, SIAM, 2014. doi:10.1137/1.9781611973402.89.

[bib.bib60] [60] Marek Kuczma. An Introduction to the Theory of Functional Equations and Inequalities. Birkhäuser Basel, 2009.

[bib.bib61] [61] Kevin Matulef, Ryan O’Donnell, Ronitt Rubinfeld, and Rocco A Servedio. Testing halfspaces. SIAM Journal on Computing, 39(5):2004–2047, 2010. doi:10.1137/070707890.

[bib.bib62] [62] Kevin Matulef, Ryan O’Donnell, Ronitt Rubinfeld, and Rocco Servedio. Testing (subclasses of) halfspaces. In Property testing: current research and surveys, pages 334–340. Springer, 2010. doi:10.1007/978-3-642-16367-8_27.

[bib.bib63] [63] Kevin Matulef, Ryan O’Donnell, Ronitt Rubinfeld, and Rocco A Servedio. Testing $\pm$ 1-weight halfspace. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 646–657. Springer, 2009. doi:10.1007/978-3-642-03685-9_48.

[bib.bib64] [64] Joe Neeman. Testing surface area with arbitrary accuracy. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 393–397. ACM, 2014. doi:10.1145/2591796.2591807.

[bib.bib65] [65] Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. Journal of Computer and System Sciences, 72(6):1012–1042, 2006. doi:10.1016/j.jcss.2006.03.002.

[bib.bib66] [66] Michal Parnas, Dana Ron, and Alex Samorodnitsky. Testing basic boolean formulae. SIAM Journal on Discrete Mathematics, 16(1):20–46, 2002. doi:10.1137/S0895480101407444.

[bib.bib67] [67] Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability pcp characterization of np. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 475–484, 1997. doi:10.1145/258533.258641.

[bib.bib68] [68] Dana Ron. Algorithmic and analysis techniques in property testing. Found. Trends Theor. Comput. Sci., 2009. doi:10.1561/0400000029.

[bib.bib69] [69] Dana Ron et al. Property testing: A learning theory perspective. Foundations and Trends® in Machine Learning, 1(3):307–402, 2008. doi:10.1561/2200000004.

[bib.bib70] [70] Ronitt Rubinfeld and Madhu Sudan. Self-Testing Polynomial Functions Efficiently and Over Rational Domains. In Proceedings of the 3rd Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms (SODA), pages 23–32, 1992. URL: http://dl.acm.org/citation.cfm?id=139404.139410.

[bib.bib71] [71] Ronitt Rubinfeld and Madhu Sudan. Robust Characterizations of Polynomials with Applications to Program Testing. SIAM Journal on Computing, 25(2):252–271, 1996. doi:10.1137/S0097539793255151.

[bib.bib72] [72] Mert Sağlam. Near Log-Convexity of Measured Heat in (Discrete) Time and Consequences. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 967–978. IEEE Computer Society, 2018. doi:10.1109/FOCS.2018.00095.

[bib.bib73] [73] Alex Samorodnitsky. Low-degree tests at large distances. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 506–515, 2007. doi:10.1145/1250790.1250864.

Testing Sparse Functions over the Reals

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Our problem setting.

Definition 1.1 (η-approximate query).

Boundedness.

Choice of Reference Distribution.

2 Our results

2.1 Testing 𝒌-linear functions

Definition 2.1 (k-linearity).

Theorem 2.2 (Informal, see Theorem 5.1).

▶ Remark 2.3.

2.2 Testing 𝒌-sparse low degree polynomials

Definition 2.4 (k-sparsity).

Definition 2.5 (Hankel Matrix for polynomials [52, 11]).

Observation 2.6 (Generalization of [11, Section 4], and [52, Lemma 4]).

Theorem 2.7 (Informal, see Theorem 6.1).

▶ Remark 2.8.

2.3 Testing 𝒌-juntas

Definition 2.9 (k-junta).

Theorem 2.10 (Informal, see Theorem 7.1).

2.4 Lower bounds

Theorem 2.11.

2.5 New Technical Contributions

𝒌-sparsity Tester.

Theorem 2.12 (Probabilistic Upper Bound on σmax).

Proof Sketch.

▶ Remark 2.13.

𝒌-linearity Tester.

𝒌-junta tester.

2.6 Discussion

Organization of the paper

3 Technical Overview

3.1 Testing 𝒌-linearity

3.2 Testing 𝒌-sparsity

3.3 Testing 𝒌-juntas

4 Preliminaries

Notations.

Definition 4.1 (ℓ1-distance).

Definition 4.2 (Concentrated distribution).

Fact 4.3 ([23, Theorem 2.9]).

4.1 Results from Perturbation Theory, and Measure Theory

Theorem 4.4 (Weyl’s Inequality [55]).

Theorem 4.5 ([27, Theorem 8]).

Theorem 4.6 ([47, Corollary 4]).

5 𝒌-linearity Testing

Theorem 5.1 (Generalization of Theorem 2.2).

Definition 5.2 (Additive function).

Fact 5.3 ([60, Section 5.2]).

Theorem 5.4 ([5, Theorem D.1], and [7, Theorem 3.3]).

Lemma 5.5 ([5, Lemma D.3 and D.6]).

Lemma 5.6 ([5, Lemma D.4 and D.5]).

Lemma 5.7 ([5, Lemma 4.19]).

Claim 5.8.

Observation 5.9.

5.1 Analyses of Subroutines

Definition 5.10 (Influential bucket for linear functions).

Claim 5.11 (Correctness of 𝖥𝗂𝗇𝖽𝖨𝗇𝖿𝖡𝗎𝖼𝗄𝖾𝗍).

Claim 5.12 (Correctness of 𝖥𝗂𝗇𝖽𝖨𝗇𝖿𝖡𝗎𝖼𝗄𝖾𝗍𝗌).

5.2 Analysis of the 𝒌-linearity tester (Algorithm 1)

Proof of Theorem 5.1.

Completeness.

Soundness.

Query complexity.

6 𝒌-Sparse Low Degree Testing

Theorem 6.1 (Generalization of Theorem 2.7).

Theorem 6.2 ([7, Theorem 3.6]).

Lemma 6.3 ([5, Lemma 4.4]).

Testing sparsity of polynomials given exact query access.

Lemma 6.4.

Definition 1.1 ( $\eta$ -approximate query).

2.1 Testing $𝒌$ -linear functions

Definition 2.1 ( $k$ -linearity).

$\blacktriangleright$ Remark 2.3.

2.2 Testing $𝒌$ -sparse low degree polynomials

Definition 2.4 ( $k$ -sparsity).

$\blacktriangleright$ Remark 2.8.

2.3 Testing $𝒌$ -juntas

Definition 2.9 ( $k$ -junta).

$𝒌$ -sparsity Tester.

Theorem 2.12 (Probabilistic Upper Bound on $\sigma_{\max}$ ).

$\blacktriangleright$ Remark 2.13.

$𝒌$ -linearity Tester.

$𝒌$ -junta tester.

3.1 Testing $𝒌$ -linearity

3.2 Testing $𝒌$ -sparsity

3.3 Testing $𝒌$ -juntas

Definition 4.1 ( $\ell_{1}$ -distance).

5 $𝒌$ -linearity Testing

Claim 5.11 (Correctness of $\mathsf{FindInfBucket}$ ).

Claim 5.12 (Correctness of $\mathsf{FindInfBuckets}$ ).

5.2 Analysis of the $𝒌$ -linearity tester (Algorithm 1)

6 $𝒌$ -Sparse Low Degree Testing

6.2 Analysis of $𝒌$ -Sparsity Low Degree Tester

7 $𝒌$ -Junta Testing

7.1 Proof of correctness of Test- $k$ -Junta

$\Omega(\frac{1}{\varepsilon})$ queries for linearity.

$\Omega(d)$ queries for degree- $𝒅$ polynomial testing.