Price of Parsimony: Complexity of Fourier Sparsity Testing
Authors: Arijit Ghosh
Manmatha Roy
Venue: NeurIPS 2025 poster ()
Keywords: Fourier Sparsity
Boolean Function
Fourier Analysis
Computational Learning Theory
Property Testing
Primary area: theory
TL;DR: The authors design a query-efficient algorithm that, given oracle access to a real valued function over Boolean cube, estimates its $\ell_2^2$ distance to the nearest $k$-Fourier sparse real valued function defined over Boolean Cube.

Abstract: A function \( f : \mathbb{F}_2^n \to \mathbb{R} \) is said to be \( s \)-Fourier sparse if its Fourier expansion contains at most \( s \) nonzero coefficients. In general, the existence of a sparse representation in the Fourier basis serves as a key enabler for the design of efficient learning algorithms. However, most existing techniques assume prior knowledge of the function’s Fourier sparsity, with algorithmic parameters carefully tuned to this value. This motivates the following decision problem: given \( s > 0 \), determine whether a function is \( s \)-Fourier sparse.

In this work, we study the problem of tolerant testing of Fourier Sparsity for real-valued functions over \( \mathbb{F}_2^n \), accessed via oracle queries. The goal is to decide whether a given function is close to being \( s \)-Fourier sparse or far from every \( s \)-Fourier sparse function. Our algorithm provides an estimator that, given oracle access to the function, estimates its distance to the nearest \( s \)-Fourier sparse function with query complexity \( \widetilde{O}(s) \), for constant accuracy and confidence parameters.

A key structural ingredient in our analysis is a new spectral concentration result for real-valued functions over \( \mathbb{F}_2^n \) when restricted to small-dimensional random affine subspaces. We further complement our upper bound with a matching lower bound of \( \Omega(s) \), establishing that our tester is optimal up to logarithmic factors. The lower bound exploits spectral properties of a class of cryptographically hard functions, namely, the Maiorana--McFarland family, in a novel way.

Price of Parsimony: Complexity of Fourier Sparsity Testing
Arijit Ghosh arijitiitn tegpsterrgmaaaaa com Indian Statistical Institute, Kolkata, India
Manmatha Roy
reach wwwmathaanmaaaaaaaammmm 111.111.... com Indian Statistical Institute, Kolkata, India
Abstract
A function S F2 + IR is said to be s-Fourier sparse if its Fourier expansion contains at most 8 nonzero coefficients. In general, the existence representation in the Fourier basis serves key enabler for the design of efficient learning algorithms. However, most existing techniques assume prior knowledge of the function's s Fourier sparsity, with algorithmic parameters carefully tuned to this value. This motivates the following decision problem: given 8 > 0, determine whether function is s-Fourier sparse.
sparse
In this work, study the problem of tolerant testing of Fourier Sparsity for real-valued functions over IPS, accessed via oracle queries. The goal is to decide whether given function is close to being s-Fourier sparse or far from every s- Fourier sparse function. Our algorithm provides an estimator that, given oracle access to the function, estimates its distance to the nearest s-Fourier sparse function with query complexity (s), for constant accuracy and confidence parameters. A key structural ingredient in our amalysis is new spectral concentration result for real-valued functions over 1P when restricted to small-dimensional random affine subspaces. We further complement our upper bound with a matching lower bound of ?(s)), establishing that our tester is optimal up to logarithmic factors. The lower bound exploits spectral properties class cryptographically hard functions, namely, the Maiorana-McFarlan family, in novel way.
Introduction
Sparsity is one of the most powerful ideas connecting modern machine learning and theoretical computer science. It captures the intuition that, even in high-dimensional settings, many natural functions or signals depend only on a small number of relevant components. This assumption underlies algorithms that are both sample- and time-efficient, forming the basis of techniques such as sparse linear regression, decision tree learning. and compressed sensing. Across these frameworks, the common principle is simple yet profound: if a function admits sparse representation suitable basis, such Fourier, wavelet, polynomial, or learned dictionary, then learning and inference can be made dramatically more efficient.
particularly elegant setting where sparsity plays a central role is that of real-valued functions over the Boolean hypercube Ey. Fourier analysis provides a natural orthonormal basis for such functions. Every function f: By + IR can be expressed as
f(x) = Σ (-1)(aa)
DEFR
where f(a) denotes the Fourier coefficient at frequency a. The Fourier sparsity of f. the number of nonzero coefficients in this expansion quantifies how succinetly the function can be represented in the Fourier basis.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Fourier sparsity is recurring theme across many areas of theoretical computer science. In complexity theory, it lies at the heart of problems involving communication complexity and parity decision trees for Boolean functions f F2 + (+1,- ]
In learning theory, it has become central tool for designing algorithms that efficiently learn functions with low-degree or low-support Fourier spectra. Many natural Boolean functions exhibit this property: graph and hypergraph cut functions, as well as decision trees of bounded depth, are inherently Fourier sparse because their spectra are concentrated on low-degree coefficients [28 22]. For example, the cut function of graph corresponds to a degree-2 polynomial in the Fourier basis, while a degree-d hypergraph cut function has degree most d. Similarly, Boolean decision tree of depth d has its spectrum supported entirely on coefficients of degree at most d.
B2
33
29
27
I0
Beyond these classical examples, Fourier-sparse models have found renewed relevance in modern machine learning- They appear in settings such as neural network hyperparameter optimization [20 and the learning of structured set functions 4 The impact of Fourier sparsity extends even further, into cryptography, where the celebrated Goldreich-Leviis theorem
[3] established deep connection between identifying large Fourier coefficients and constructing hardcore predicates for one-way
functions.
Algorithmically, two main approaches have emerged for learning or recovering Fourier-sparse functions: Sparse Hadamard Transform methods [7 25 21 and Compressed Sensing techniques [24 19]. Both families of algorithms, however, rely critically on prior knowledge of the function's 's sparsity level. This partcular gap motivates our work, which focuses on efficiently estimating the Fourier sparsity, up to desired approximation in & distance. Such an estimator can serve as useful preprocessing step in learning pipelines, both for verifying whether sparsity-based assumptions hold and for guiding the initialization of sparsity parameters in downstream algorithms.
To formalize this setting, we first introduce some basic definitions. We measure distances between functions using the squared mn-nr::
dist = |lf 9
-()))
2n
ZEPS
For a function f and a class of functions P, the distance of f from P is defined as
dist P) min |l - gll2.
9EP
We also recall the standard definition of the m--nom. For any function f : + I.
|
Σ f(x).
2
ZER
Let F, denote the class of all s-Fourier sparse functions, that is, functions f + whose Fourier spectrum has at most nonzero coefficients. We are interested in determining how close given function f is to this class.
Problem 1.1. Given query access to a function F - R with |/ = and parameters e E (0, 1}, and E [0, 11. the task is to design a randomized algorithm that distinguishes between the following Iwo cases:
. (Close): There exists E F. such that [|.
_112 < 5.
* (Far): For every E Fs. If - 9 3 2 8 c.
The goal is construct such algorithm using as few queries I possible, while ensuring that distinguishes the two cases with high probability.
Our main contribution in this paper is the design of simple, nonadaptive and almost optimal query algorithm for testing Fourier sparsity.
Theorem 1.2. Let s > E 10, and E [0, 1). Let R R be an unknown function with ||/ 1, accessible only via query access. Then, there exists nonadaptive algorithm that, with success probability at least 2/3, distinguishes between the following two cases:
f is 8-close to being s-Fourier sparse,

---

. f is (6 + f)-far from every s- s-Fourier sparse function,
using at most ((s/²) queries to J. where the Ō(-) notation hides factors polynomial in log s and log(1/5 l/e).
Theorem
1.2 proved in Section 3 Although stated under the assumption that the function has unit
f2-norm, the result extends to any nonzero function f 122 - IR via normalization.
We also show that the query complexity of our algorithm is tight up to logarithmic factors by proving a matching lower bound.
Theorem 1.3. Let > O. Any randomized algorithm that decides whether function f F2 (-1,+13, is s-Fourier sparse or (1/4)-far from every s-Fourier sparse function over E2, must make
(()) queries to f to succeed with probability at least 2/3.
The reader may note that any Boolean function f: FF - {-1, +1} satisfies |l = 1. The proof of
Theorem is3 presented in Section
1.1 Related works
Testing Fourier sparsity was first studied by Gopalan et al. [16], who focused on Boolean functions measure of proximity. (The Hamming distance between two functions f.g : FE -> (0, }} is the fraction of inputs on which they differ.) Their algorithm has query complexity (s)4), which quickly becomes impractical for even moderately large values of Similarly, the regularity framework of Hatami and Lovett (18] provides a general-purpose black-box reduction for testing Fourier sparsity under Hamming distance, but this approach suffers from a query complexity that grows as a tower function in 8.
and used the Hamming distance
In the real-valued setting, Yaroslavtsev and Zhou 31 considered testing Fourier sparsity with respect the squared fz-distance. They designed algorithm with query complexity (ss/e)) and established a lower bound of (s()s). In comparison, our algorithm improves the dependence on the proximity parameter requiring only ((s/²) queries, and is conceptually simpler. We further establish nearly tight lower bound of (s)),, quadratically improving the current state of art [31], showing that our algorithm is optimal up to logarithmic factors.
It is important note that testing Fourier sparsity in the random example model significantly more challenging. As shown in [14], even for linearity testing, where the target functions are 1-Fourier sparse, it not known how to design tester whose sample complexity is independent of the ambient dimension n. In contrast, in the query access model, linearity testing can be performed efficiently using the well-known 3-query BLR test. Our work aims to estimate the Fourier sparsity level of function in way that depends only on the sparsity and the proximity parameter e, while remaining independent of the ambient dimension n.
1.2 Proof Sketch of Theorem
The design of our tester is inspired by the well-established framework for testing hereditary graph properties. A canonical tester for such a property P samples small random subset of vertices, queries all induced edges, and checks whether the resulting subgraph satisfies P. For hereditary properties, those preserved under taking induced subgraphs, this approach guarantees only modest (quadratic) overhead in query complexity [5] I]. Indeed, for several natural properties, such as bipartiteness, the canonical tester achieves optimal performance up constant factors.
A similar idea has been successfully adapted to Boolcan functions, particularly for testing affine- invariant properties [8 6). In this setting, the canonical approach restricts the function to random low-dimensional affine subspaces and tests the property on these restrictions. While this strategy enjoys strong generality and theoretical support, e.g., via regularity-like lemmas, it often suffers from impractical query complexity, including tower-type dependencies [88]. Nonetheless, specialized testers exploiting finer structural properties have been developed for specific cases, such as low algebraic degree 3 and aod-cycle-freeneee M. Surprisingly, despite being a natural and central affine-invariant property, Fourier sparsity has largely resisted similar progress.
Prior works in Fourier sparsity testing typically project the Fourier spectrum into randomly chosen cosets of sufficiently large codimension, process commonly referred to as Fourier hashing, which
3

---

was originally introduced in [T]] Analytical or combinatorial tools are then applied to extract sparsity information. For example, Gopalan et al. []6] presents a granularity theorem for Fourier-sparse functions, showing that individual coefficients cannot be too small and reducing the problem to counting large-weight cosets. Similarly, Yaroslavtsev et of heavy buckets to design their tester.
certain concentration of the f-rnrr
In contrast, our approach analyzes the function restricted to randomly chosen subspace. We approximately recover the Fourier spectrum of this restricted function and use it to infer the sparsity of the original function. A new structural relationship between the Fourier coefficients of the restricted and original functions shows that, under suitable subspace choices, their magnitudes closely match. This relationship central to our analysis. Instead of explicitly defining hashing process, restricting the function to subspace implicitly induces a hashing, allowing us to derive concentration bound in terms of the norrr of bucketed Fourier coefficients, which constitutes our main technical contribution.
1.3 Proof Sketch of Theorem
We prove lower bound for testing Fourier sparsity via reduction from randomized communication complexity, following the approach introduced by Blais, Brody, and Matulef [9]. Our reduction builds on the structure of Maiorana-McFarrladd functions and their connection to the Approximate Matrix Rank problem. Maiorana-McFarland functions are widely used in theoretical computer science, especially for circuit lower bounds and structural analysis of Boolean functions. They also play central role in symmetric-key cryptography, thanks to their spectral properties that support strong confusion and diffusion.
Consider a communication problem where Alice and Bob receive matrices A, B Fy F and their goal is to determine whether the sum C A + B has rank at least R, most cR, for some fixed constant c < 1. We encode this instance into the Fourier domain by composing functions with linear transformations derived from the input matrices. A central property of this construction is that the Fourier sparsity of the resulting function is closely tied to the rank of the matrix C. Thus, distinguishing high-rank from low-rank instances in the matrix problem reduces to distinguishing functions that are close to being Fourier sparse from those that are far.
-arorann-McFaraanddd
To complete the reduction, randomized protocol for the Approximate Matrix Rank problem must communicate at least Ot ((T))) bits. Since our reduction incurs only constant overhead, we conclude that any nonadaptive algorithm for testing Fourier sparsity must make Q2 S?R²) queries the worst case. This matches our upper bound up logarithmic factors and establishes the optimality of our tester.
result of Sherstov and Storozhenko (26), which shows that any
2 Background
Any function /FF >> can be uniquely expressed as
f(x)
Σ (()) aEFS
where (x) = (-1)(a.a) and A(a) = Ex [(x)(x)) The quantity Ma)² denotes the Fourier weight a, and the collection {f(a)) } is the Fourier spectrum of f. We use the following standard facts:
Parseval's identity: 1 = Σ, fla)²
Plancherel's theorem: (f.g) = -. faa)((a).
Character multiplication: Xat$ = XaX..
Poisson summation: For any subspace H C F2, we have
Xx. H a a H-.
otherwise.
ZEH
For our lower bound theorem, we will require the following definitions and results from communica- tion complexity.

---

In the randomized communication model, Alice and Bob compute function x (0,1) using shared randomness. The randomized communication complexity R the minimum number of bits exchanged to compute fz, y) correctly with probability least 2/3.
In the Approximate Malrix Rank problem, Alice holds A E F2x" and Bob holds B e F5x"; they must distinguish whether rank (A + B) = r or 4. The following lower bound is known 126 Theorem 1.1]:
R1/3 [RANK T: Pair.)
=
3 Improved upper bound for testing Fourier sparsity
Our analysis centers on restricting the function f to random affine subspaces of Fý. We study how the individual Fourier coefficients behave under such restrictions, comparing it to that of the original function. Table[[[mmmariss the notations used this section.
3.1 Fourier analysis under affine restrictions
We consider a function f: F2 + R. Let H C F2 be subspace and a E F2. Define the restricted function fA R by
e H.
We will briefly recall some standard facts about the Fourier spectrum fa. Let H C F2 be the annihilator (see [ of H, that is, the set of vectors orthogonal to every element of H, and let W C L be complementary subspace to H so that
F2 = W e H and W n H = {(0}.
The Fourier coefficients of fA are naturally indexed by y W, and the Fourier expansion of fa is
fa(Ø) Σ (z))) E H,
7EW
where
fa(t)= = Σ F(B) xa()),
BEY+HL
and f(B) are the Fourier coefficients of f on Fz. Observe that there is another way to write the
Fourier expansion of fA in the following way:
fA(x)
Σ
(a())),()), HE
/ER
where
-a = F(3))((()))
BEB
Recall that 3 is coset of H and therefore subset of F2z.
Remark 3.1. By abuse of notation, for Y Fž, Fa(r) denotes the Fourier coefficient fA(T) corresponding to the coset 7 = -1 of 11 containing 7.
The following identities will be used by our tester, given Section 3.3 for estimating Fourier coefficients of functions restricted to affine subspace.
Theorem 3.2. Let A H a, where H be a subspace F2 and a Fz.
(a) For all in the complementary subspace W of H we have
1 Σ fA(x)x,(x).
Fa(7)
[AXi1
ZEH
H
(b) Define [[ll == [M] EVEH fa(x)² We have
1
|| = Sa()
JEW
5

---

Table of Notation
Notation
Meaning
(),
Inner product of a, 8 E F2 defined as (a, (] == Eist a, (over F2).
ExeRy [f]
Expectation of f F2 + R. Erery [f] 2ेh ExeRy f(x).
(f.g)
Inner product of f.g : Fy + R. (f.g) = Exery [f())g()) = Exery ((x)g(x))
A (randomly chosen) linear subspace of F2.
H
Given subspace H S F2 H denotes the annihilator of H, that is, H- = {x 12 (x, h), h E H}.
A
An affine subspace of the form a + H, where a E R22 Restriction of f to the affine subspace A.
SA
fA(T)
Fourier coefficient of FA at y E H. Element 7" := arg max [f(3))
3.2 Concentration of the Fourier spectrum under random affine restrictions
In Algorithm|] I the function f is restricted uniformly random affine subspace a H. This affine subspace is constructed as follows: we first select t vectors h1, ..,....,h he independently and uniformly random from F2, and define the linear subspace
H span h1, h2...., h.)
Next, introduce random shift H, we choose a E F3 uniformly at random and independently of H. and define the affine subspace as
A a + H.
Observe that the collection of cosets {r + H E H} forms a partition of the space Fz. Interestingly, the following lemma shows that this random coset partition behaves like pairwise independent hash family over F7.
Lemma 3.3 (Coset Hashing via Random Subspaces). Let H C F3 be a uniformlyy random linear subspace constructed by taking span of random vectors from Fy sampled independently and uniformly from Fy. Then the following hold:
1. For any distinct a. F2.
Pr [a. lie in the same coset of H Pri
-- 2-
H
2. For any subset S C F with |S| S s. if 2 2 log 100, then
Pr all elements of S lie in distinct cosets of H 0.99.
H
This lemma is slight restatement of Proposition 3 from 16, modified to suit the specific needs of our proof. While the full proof is deferred to the appendix, we will assume it for the time being. We now show that, for a uniform random choice of affine subspace A, the magnitude of the Fourier coefficients of the restricted function fa(7) is tightly concentrated around the magnitude of the largest Fourier coefficient of f within the coset 7 + H Specifically, we define the leader of the coset 7" arg max max 3 (f())) From this point on, refer to 7" the leader of the coset. We now formally state the following concentration result.
Lemma 3.4. Let A a H be random affine subspace of F2z where H obtained as the span of t vectors sampled independently and uniformly from F2, and a: E F7 is independent uniformly

---

random shift. Consider fuuuntiinn F: - R with fl = 1ft 2 log , then for every H and every > 0,
Pr - > マ
ạ 72
Proof. Fix 7 E F2. Recall, from Section 3.1
the Fourier coefficients of the restriction Sa satisfies
fa(r)
Σ f(3)xola).
BE7+HL
Consider the following random variable:
X = fa(7) - f())x;(aa== = Σ
RB)xs(a),
SE
and let Y [X] All probabiliieeseexpecattins below over the joint randomness of H and for fixed H we write E.I. H].
First moment bound.
For fixed H, using linearity of expectation, we have
E = Σ
R())xoco)
Σ f(3) Eixo(a)].
BE 87y
BE7+H* $#4
Now, observe that Ea [xx(aa]] for all B + 0 and equals for 3 = 0. Therefore,
f(0).
i H- and y +
B [X]] H
0,
otherwise
This implies that the expression of E. [X]
H] can be rewritten in the following form:
Eg E,[X [ H f(0)1 (UEy+H- and "003"
Using the fact that En R.,
XX|
H] = EH,,a we get
RH,a [X] f(0) Pr [ H and y # 0]
Using the fact that Pr# [0 E + H and + 0] < Prи 0 E H+], we get
EH = [(()) [r[0 - H and + 0] $ If(0)) pr[0 E E HH
Observe that
D+ Prh
#
The last inequality follows from the fact that / 2 log(1/1²*). Using the above bound on Pru ( E + [+] and the fact that [f(0) < 1 (from Parseval identity), get
EH [x,aXX]| S n" Sn.
Second moment bound.
Observe that
x
Σ
x(()x(=))((
Σ
7(8)
+
B B,8' 47
8,8
since X Xs+.*.
Taking expectation over a uniformly from Fž, we use
Ex(x((a)] 11 i = 0,
if + 0.

---

Hence, only terms with B + 3' 0 contribute. Over F22 this means 3 = B, so we obtain
[x H]
(()) ( (x))+ 8
Σ
Σ
f(8)2.
8,8 A/y
P#7
Like in the with "first moment calculation", need rewrite the expression of E, [X² H] in terms of indicator random variables:
[x2
HJ Σ
T(3)
(05y+H and ($r)
BEFS
Taking expectation over H, we get
EHa [X3] 5
Σ
A(B)2 P H+).
H
DEFS
For any fixed B, PrHI8 E 11-1 P [3 + E H-1 = 2- By Parseval Eg }(32² so
EH,a < 2 1n
Thus Varn, (X) S 1/2
Applying Chebyshev inequality. EH [X] > 7}. Hence
Since EH, [X] S 17, the event {|X] 17 + 7) implies f|x
Pr H1a
[ > +
5 Pr X
[x][ >
VarH (X)
n
72
7
Since X fa(()) f())xs(a), this proves the theorem.
Algorithm 1: FOURIER SEARRERR-SAARITY--EESSSS
Input:
Tolerance parameter ō 2 O, proximity parameter > O, sparsity parameter s, and oracle
access a function f Fy > satisfying [|fll2
Output: YES if dist? (J,F,) F,) I 6, and NO if dist (f,F.) +
Procedure:
1: Choose random affine subspace A
H F2 with dim(H) θ (log (s²/e))
2: Let fa denote the restriction of f to A, and compute an estimate ç of the sum of squares of top Fourier coefficients of fA in terms of their absolute values
3: If 1 (8 e/2) then YES, else NO.
3.3 Proof Theorem 1.2
In this section, we present the algorithm and its analysis, completing the proof of Theorem 1.2
structural characterization. We begin with simple observation that reduces testing Fourier sparsity to estimating spectral mass.
Lemma 3.5 (Structural observation). Let f F7 + E with ||lll 1. Then dist? (f.
1 maxTgr9-ITiss Σper f(3)2.
The algorithm. Algorithm I (FOURIER-SPARSITY-TI
selects random affine subspace A = a + C F2 of dimension θ (log (s² (2/22) restricts the function to A, and estimates the
Fourier coefficients of the restricted function /A. It then computes the of squares of the largest estimated coefficients and compares this quantity to the threshold 1 - (5 + </2).
Since |A| 2", the overall query complexity depends only and and is independent of n.

---

Correctness with exact restricted coefficients. We first analyze the tester assuming exact access to the Fourier coefficients of fA. Using the concentration Fourier spectrum under random restrictions (Lemmas 3.3 and 3.4). we show that the sum of the squares of the top Fourier coefficients (in terms of their absolute values) of fa approximates from that f by an additive error c/4.
If is 8-close to F.. Lemma 3.5 implies that the top Fourier coefficients of f carry mass at least 1- 6, and hence the same holds for fA up to an additive error R e/4. Conversely, if f is (ò e)-far from Fs, then every set of Fourier coefficients of fA has total squared mass at most 1 - (6 + e/2). Thus, the tester correctly distinguishes the two cases under exact Fourier access to fA-
Working with the estimates of the Fourier coefficients of SA- We first estimate the Fourier brief introduction to
coefficients of fA from oracle access f. We refer the reader to Section the Fourier coefficients of the restricted function fA. For each 7y E W, where W is the complementary subspace of H (see Table I we have
fa(7) EREn (1)(=)
Using median-of of-means technique (3) Exercise 2.2.9], obtain the following.
Lemma 3.6 (Fourier estimation on a subspace). There exists nonadaptive estimator that, using δ (s/e²) queries to f, produces estimates { (Fa(t)) PEW
such that
Fa(7) [a(t) 1000
max 7EW
with probability at least 0.99. Note that W denotes the complementary subspace H
Hence, the sum of squares of the top estimated coefficients is within c/50 of the true value and does not affect the tester's decision.
Completing the proof. Combining the above arguments, Algorithm I distinguishes functions that are d-close to being s-Fourier sparse from those that are (6 + e)-far using ((s/e²) nonadaptive
queries, with success probability at least 2/3. This completes the proof of Theorem 1.2
Remark. Complete proofs and technical details for this section appear in the full version 12
Improved lower bound for testing Fourier sparsity
In this section, we prove Theorem I.3 We begin by reviewing Maiorana-MoFarland functions and the key properties required for the proof.
4.1 Spectral structure of Maiorana-MeFarlame functions
Variants of Maiorana- Maralladd functions have found widespread in theoretical computer science, particularly in proving circuit lower bounds and studying structural properties of Boolean functions relevant to complexity theory. They also play an important role in symmetric-key cryptography, especially in the design of stream ciphers. We now define them in their most general form.
Given positive integers n and with r < n, the Maiorana-McFarrand family MM, n-variable Boolean functions f : F2 + F2 of the form:
23 consists of
f(x,y) (a, p(v)), A (x. E E FR-
where s0: FP- - F. is an arbitrary function. Here, for a, b E F . b denotes the standard inner product over F75 In this work, we focus on signed variants of Mhiorana-MeParkee functions, that is, functions of the form
g(x) = (x)) for some f E MM
We now describe the spectral structure of these functions.
Lemma 4.1 (Proof in the full version [2].. Let n = log r, and suppose yp is a mapping whose image has cardinality r and whose elements are linearly independent in F7. Let
(1, v) = (-1)(La:p(u)
be a function, where I. E F2X" is a linear transformation. Then, the Fourier sparsity of gr. is at most rank(L). L) -r

---

4.2 Proof of Theorem 1.3
We prove the lower bound in Theorem via a reduction from a variant of the Approximate Matrix Rank problem in randomized communication complexity. In this problem, Alice and Bob each hold a matrix in F2 denoted by A and B, respectively. They are promised that the matrix C A + B has rank either r or ÿ. and their task is to determine the correct case while minimizing communication. Both parties have access to a public random string.
Suppose, for the sake of contradiction, that there exists a tester T which, for any function f {-1,1}, distinguishes whether f is s-Fourier sparse e-far from every such function using only ((s,e) queries. We show that such a tester can be used to solve the matrix rank problem with low communication.
Alice and Bob independently construct Boolean functions 9A. 9B
F2 + (-1,+1] from their matrices A and B using the construction in Lemma 4.1 Define the target function gc' F2 - {-1.1} in similar way. By Lemma the Fourier sparsity of 9c depends on the rank of C = A B. Specifically, if CCn
r, then the Fourier sparsity of gC is exactly r². If rank(C) = 7 the
Fourier sparsity is at most - Now we show that, in the full-rank case, gc is 4 far from any Boolean function with Fourier sparsity at most 4.
Lemma 4.2 (Proof in the full version (). Ife matrix C E F2 has rank v, then the function gc defined in Corollary 4.1 is at least f-far from any Boolean function with Fourier sparsity at most &
To simulate the tester T for 9C+ Alice and Bob evaluate any query (z. Fž as follows: Alice computes 9.A (z. y). Bob computes gæ y), and they exchange their values. They then compute go (z, y) 94 (z, v) 9D (2, Since
gc(2, y) (-1) ()))(((+))).)()))) = ( ga v) (D(
Each query requires 2 bits of communication. Consequently, i uses q (s, 1/4) queries, Alice and Bob can simulate it using at most 2g(s, 1/4) bits of communication. Setting
= and recalling that distinguishing whether rank(C) = r or & requires (2(=2) bits of communication (Theorem 1.1 from 26 deduce 2q (r2 1/4) 2) Therefore, 9 (r2/4,1/4) = 12(r2).
Thus, any tester distinguishing s-Fourier sparse functions from those } ffr from such functions must make at least (()) queries, establishing the lower bound.
Conclusion
An intriguing direction is whether similar dimension-indepeedeee testers can be obtained for other bases, such as wavelets. While sparsity testing in general bases has been studied before [5], existing algorithms have query complexity that depends on the ambient dimension, making them unsuitable for very high-dimensional settings. contrast, our work focuses on testers whose query complexity is completely independent of the dimension. Characterizing the classes of functions and bases that admit such testers remains a fundamental open question.
We also highlight a subtle gap between our upper and lower bounds. The upper bound is proved in the tolerant setting, distinguishing functions that are ô-close to being s-Fourier sparse from those that are (ō + e -ffar, whereas the lower bound applies to the non-toleran setting, where functions are either exactly s-Fourier sparse or least 1/4-far. Since tolerant testing is strictly stronger, and since our algorithm is non-adaptive while the lower bound holds even for adaptive testers, we match the bounds up to logarithmic factor. Bridging these gaps more fully is an interesting direction for future work.
Finally, our lower bound currently applies only for e = 1/4. Extending it to arbitrary nonzero é remains an important open problem.
Acknowledgement. Arijit Ghosh acknowledges partial support from the MATRICS grant MTR/2023/001527 and the DST grant TPN-104427. A part of this work was carried out dur- ing Manmatha Roy's visit to the Selmer Center for Secure Communication at the University of Bergen, hosted by Lilya Budaghyan and partially supported by the Norwegian Research Council. The authors also thank Swagatam Das and Sourav Chakraborty for valuable discussions during the course of this work.
10

---

References
[1] Noga Alon. Testing Subgraphs in Large Graphs. Random Structures & Algorithms, 21(3- 4):359-370, 2002. A preliminary version of this paper appeared as extended abstract in the proceedings of FOCS 2001.
[2] Noga Alon, Eldar Fischer, Iln Newman, and Asaf Shapira. A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity. SIAM Journal Computing, 39(1):143-167, 2009. A preliminary version of this paper appeared as an extended abstract in the proceedings of STOC 2006.
[3] Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing Low- Degree Polynomials over GF(2). In Proceedings of the 7th International Workshop on Ran- domization and Approximation Techniques in Computer Science (RANDOM), pages 188-199, 2003.
[4] Andisheh Amrollahi, Amir Zandieh, Michael Kapralov, and Andreas Krause. Efficiently Learning Fourier Sparse Set Functions. In Proceedings of the 33rd Anmual Conference on Neural Information Processing Systems (NeurIPS), volume 32, pages 15094-15103, 2019.
[5] Siddharth Barman, Arnab Bhattacharyya, and Suprovat Ghoshal. Testing Sparsity over Known and Unknown Bases. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80, pages 491-500, 2018.
[6] Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie. Testing Non-linear Properties: Short Report, pages 260-268. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010.
[7] Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, and Asaf Shapira. Testing Odd--ycle-Freeeness in Boolean Functions. Combinatorics, Probability and Computing, 2 21(6))835-855, 2012. A preliminary version of this paper appeared extended abstract in the proceedings of SODA 2012.
[8] Arnab Bhattacharyya, Elena Grigorescu, and Asaf Shapira. A Unified Framework for Testing Linear-Invarian Properties. Random Structures & Algorithms, 46(2):232-266 2015. A preliminary version of this paper appeared as an extended abstract in the proceedings of FOCS 2010.
[9] Eric Blais, Joshua Brody, and Kevin Matulef. Property Testing Lower Bounds via Communica- tion Complexity. Computational Complexity, (1(2):1113355 2012. Preliminary version of this paper appeared as extended abstract in the proceedings of CCC 2011.
[10] Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, and Swagato Sanyal. Tight Chang's- s-mema-Type Bounds for Boolean Functions. In Proceedings of the 41st IARCS Annual Conference Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 213, pages 10:1-10:22, 2021.
[11] Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. New Results for Learnnng Noisy Parities and Halfspaces. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 563-574, 2006.
[12] Arijit Ghosh and Manmatha Roy. Price of Parsimony: Complexity of Fourier Sparsity Testing. arXiv, 2026.
[13] Oded Goldreich and Leonid A Levin. A Hard-Core Predicate for all One- One-Way Functions. In Proceedings of the 2 st Annual ACM Symposium on Theory of Computing (STOC), pages 25 32, 1989.
[14] Oded Goldreich and Dana Ron. Sample-Based Testers. ACM Transactions on Computation Theory, 8(2):1-54, 2016.
[15] Oded Goldreich and Luca Trevisan. Three Theorems Regarding Testing Graph Properties. Random Structures & Algorithms, 23(1):23-57, 2003. preliminary version of this paper appeared as extended abstract in the proceedings of FOCS 2001.
11

---

[16] 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. A preliminary version of this paper appeared as an extended abstract in the proceedings of ICALPP 2009.
[17] Haitham Hassanich, Piotr Indyk, Dina Katabi, and Eric Price. Nearly Optimal Sparse Fourier Transform. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pages 563-578, 2012.
[18] Hamed Hatami and Shachar Lovett. Estimating the Distance from Testable Invariann Properties. In Proceedings of the 54th Anmual IEEE Symposium on Foundations of Computer Science (FOCS), pages 237 242, 2013.
[19] Ishay Haviv and Oded Regev. The Restricted Isometry Property of Subsampled Fourier Matrices, pages 163-179. Springer International Publishing, Cham, 2017.
[20] Elad Hazan, Adam R. Klivans, and Yang Yuan. Hyperparameter Optimization: Spectral Approach. In Proceedings of the 6th International Conference on Learning Representations (ICLR). OpenReview.net, 2018.
[21] Piotr Indyk, Michael Kapralov, and Eric Price. (Nearly) Sample-Optimal Sparse Fourier Transform. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 36-55, 2014.
[22] Nathan Linial, Yishay Mansour, and Noam Nisan. Constant Depth Circuits, Fourier Transform, and Learnability. Journal of the ACM, 40(3):607-62) 1993. A preliminary version of this paper appeared as an extended abstract in the proceedings of FOCS 1989.
[23] Robert L. McFarland. A Family of Noncyelic Difference Sets, Journal of Combinatorial Theory, Series A, 15:1-10, 1973.
[24] Mark Rudelson and Roman Vershynin. On Sparse Reconstruction from Fourier and Gaussian Measurements. Communications on Pure and Applied Mathematics, 6158):0055 2008
[25] Robin Scheibler, Sacid Haghighatshoar, and Martin Vetterli. A Fast Hadamard Transform for Signals With Sublinear Sparsity in the Transform Domain. IEEE Transactions on Information T'heory, (14:211155221
2015.
[26] Alexander A. Sherstov and Andrey A. Storozhenko. The Communication Complexity of Ap- proximating Matrix Rank. In Proceedings of the IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 433 462, 2024.
[27] Amir Shpilka, Avishay Tal, and Ben lee Volk. On the Structure of Boolean Functions with Small Spectral Norm. Computational Complexity, 26(1):229-22) 273, 2017. A preliminary version of this paper appeared as an extended abstract in the proceedings of ITCS 2014.
[28] Peter Stobbe and Andreas Krause. Learning Fourier Sparse Set Functions. In Proceedings of the 15th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 22, pages 1125 1722--113,, 1133, 2012.
[29] Hing Yin Tsang, Chung Hoi Wong, Ning Xie, and Shengyu Zhang. Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 658-667, 2013.
[30] Roman Vershynin. High-Dimen -igeesiimmsi Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018
[31] Grigory Yaroslavtsev and Samson Zhou. Fast Fourier Sparsity Testing, In Proceedings of the 3rd Symposium on Simplicity in Algorithms (SOSA), pages 57-68, 2020.
[32] Zhiqiang Zhang and Yaoyun Shi. Communication complexities of symmetric XOR functions. Quantum Information & Computation, 93)):555 2009.
[33] Zhiqiang Zhang and Yaoyun Shi. On the parity complexity measures of Boolean functions. Theoretical Computer Science, 41 222222299)261222266 221122 2010.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes. Theorem 1.1 and 1.2 constitute the main contributions of the paper and have been rigorously proved in Sections 2 and 3.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [No]
Justification: Although we did include a dedicated limitations section, the scope for further improvement is minimal provide both algorithm and a lower bound that are optimal up logarithmic factors for the considered class of functions, significant result in computational learning theory.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Yes, each theorem and lemma is accompanied by complete set of assumptions and detailed, correct proofs.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: No experimental results were included in the paper; hence, this question is not applicable.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: Our work does not involve data collection code exccution; hence, this question is not applicable.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
No experimental setup used in this work; therefore, this item is not applicable.
Justification:
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: As no experiments were conducted, questions statistical significance or enror bars do not arise.
8. Experiments compute resources
13

---

Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [NA]
Justification: This work does not involve any experiments requiring computational resources; thus, the question is not applicable.
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We have reviewed the NeurlPS Code of Ethies and confirm that our work conforms to it in all respects, wherever applicable.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical paper, and the best of understanding, does have direct societal implications.
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: As no data or models were released in this work, this question does not apply.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Although no experimental assets were used, all prior work has been appropri- ately cited to the best of our ability.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [NA]
Justification: While our work does not introduce experimental assets, we have clearly defined the theoretical model proposed.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: No experiments involving human subjects crowdsourcing were conducted; thus, this question not applicable.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
14

---

Answer: [NA]
Justification: No human subjects were involved in this study; therefore, IRB approval was not required.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration not required.
Answer: [NA]
Justification: We have used large language models solely for editorial purposes and not in any aspect of the methodology or technical contribution.
15


Reviews:
[{"review_id": "AM9OFUtBMA", "reviewer": "Reviewer_qkU2", "summary": "This paper studies testing the sparsity of the Fourier coefficients of real-valued functions over $F_2^n$. The authors show that $\\tilde{O}(s)$ queries to the function is necessary and sufficient to determine whether the Fourier coefficients are approximately $s$-sparse.", "questions": "1. It is interesting that the query complexity does not depend on $\\delta$. Could the authors provide an intuitive explanation?\n2. What is the main difficulty in proving an adaptive lower bound?\n3. It has been shown for other problems that under sparsity assumptions, adaptivity could help to achieve better complexity. Could adaptive algorithms close the logarithmic gap?", "limitations": "The limitations can be found in the theorem statements. Since it is a theoretical paper, there are no immediate social concerns.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. Fourier coefficients of functions and property testing are very fundamental problems in theoretical computer science. The authors make important progress in these problems by closing the gap for testing sparsity of Fourier coefficients using non-adaptive algorithms.\n2. The paper is clearly written and easy to follow.\n\nWeakness:\n1. The author does not prove a lower bound with respect to $\\epsilon$. Also, from the end of section 1 it seems that the lower bound only holds for non-adaptive algorithms. Therefore, there is still a gap in the results.\n2. My main concern is that functions with real domains are more common in machine learning, which have a very different geometric and algebraic structure than $F_2^n$. It is not immediately clear from the paper how $F_2^n$-domain functions and their Fourier coefficients would be useful in applications such as regression. It would be great if the authors could provide examples of $F_2^n$-domain functions and applications of their Fourier coefficients in machine learning.\n\nOverall, this paper presents strong results for a fundamental theoretical problem; however, the relevance to machine learning is not immediately clear.", "was_revised": true, "final_justification": "This paper makes progress in testing sparsity of Fourier coefficientsof boolean functions, which is a fundamental problem in theoretical computer science. The authors addressed my concerns about the lower bound for adaptive algorithms and applications of boolean functions in machine learning. Therefore, my final evaluation is acceptance.", "rebuttal": "Reviewer's Question - 1: It is interesting that the query complexity does not depend on $\\delta$. Could the authors provide an intuitive explanation?\n\nOur Response: Below, we provide an intuitive explanation of our reasoning regarding the independence of $\\delta$ in the query complexity.\n\nThe central idea is that our algorithm estimates the squared sum of the top $s$ Fourier coefficients of the given function up to an additive error, such as $\\epsilon/8$. This level of approximation is sufficient to distinguish whether the function is $\\delta$-close or $(\\delta + \\epsilon)$-far from being $s$-Fourier sparse in Euclidean distance. To see why, recall that, by Parseval’s identity,\n$\\mathbb{E}[(f(x) - g(x))^2] = \\sum_\\alpha (\\hat{f}(\\alpha) - \\hat{g}(\\alpha))^2$, so an additive approximation to the Fourier weight of the top $s$ Fourier coefficients suffices for this decision. \n\nIn our tester, this estimation is made possible by a concentration phenomenon of the Fourier coefficients under random restriction of the function. Specifically, in Lemma~2.2, we show that when the function is restricted to a random affine subspace, each Fourier coefficient of the restricted function approximates its counterpart in the original function up to an additive error. Leveraging this, and with our choice of parameters, we show that each of the top $s$ coefficients is preserved within an additive error of $O(\\sqrt{\\epsilon/s})$, and consequently, their squared sum is preserved up to $O(\\epsilon)$.\n\nFinally, we would like to draw the reader’s attention to the fact that the query complexity of our tester is determined by the dimension of the random affine subspace used in the restriction. Notably, this dimension, and hence the overall query complexity, depends only on the approximation parameter $\\epsilon$ and the sparsity parameter $s$.\n\nReviewer's Question - 2: What is the main difficulty in proving an adaptive lower bound?\n\nOur Response: Indeed, proving lower bounds for adaptive algorithms is considerably more challenging than for non-adaptive ones. This is because adaptive algorithms can adjust their subsequent queries based on the outcomes of earlier ones, resulting in a significantly larger and more intricate space of strategies that must be ruled out in any lower bound argument. \n\nHowever, we would like to emphasize that our work actually establishes an adaptive lower bound. This is achieved via a reduction from a suitable two-party communication complexity problem. Such reductions are well-suited for proving adaptive lower bounds, as communication protocols are inherently adaptive, each message may depend on the prior communication. Consequently, the hardness of the communication problem carries over to our model, even when adaptive query strategies are allowed.\n\nImportantly, our upper bound is achieved by a non-adaptive algorithm, while the lower bound applies even to adaptive algorithms. This represents the best of both worlds: the algorithm operates in a weaker (non-adaptive) setting, yet the lower bound holds in a stronger (adaptive) setting. This is one of those interesting cases where adaptivity offers no advantage over non-adaptivity. We will revise the exposition in the final version to highlight and clarify this more explicitly.\n  \nReviewer's Question - 3: It has been shown for other problems that under sparsity assumptions, adaptivity could help to achieve better complexity. Could adaptive algorithms close the logarithmic gap?\n\nOur Response: In addition to the issue of adaptivity versus non-adaptivity, we would like to draw attention to another subtle aspect of our work. Specifically, our upper bound is established in the tolerant setting, where the goal is to distinguish functions that are $\\delta$-close to being $s$-Fourier sparse from those that are $(\\delta + \\epsilon)$-far from every $s$-Fourier sparse function. In contrast, our lower bound is proved in the non-tolerant setting, where the function is either exactly $s$-Fourier sparse or at least $1/4$-far from every such function. Clearly, the tolerant model is slightly stronger, as it requires accepting all functions that are close to being $s$-Fourier sparse, not just those that are exactly $s$-Fourier sparse. On the other hand, by definition, a non-tolerant tester is not required to behave in any particular way on such close to being $s$-Fourier sparse functions. It is worth noting that in the property testing literature, logarithmic or even larger gaps between tolerant and non-tolerant complexities have been observed in several problems. \n\nReturning to our discussion, we would like to highlight that our contribution consists of a non-adaptive tolerant tester and an adaptive lower bound in the non-tolerant setting. \n\nFrankly speaking, at this point, we do not know which of our bounds are tight. However, we view this as an interesting and open question, and we are actively working to better understand the complexity of Fourier sparsity testing across all possible settings.\n\nReviewer's Remark - 1: The author does not prove a lower bound with respect to $\\epsilon$. Also, from the end of section 1 it seems that the lower bound only holds for non-adaptive algorithms. Therefore, there is still a gap in the results.\n    \nOur Response: Our lower bound argument can be adapted to get $\\Omega(s/\\epsilon)$ lower bound. Note that our lower bound is for adaptive algorithms. \n\nReviewer's Remark - 2: My main concern is that functions with real domains are more common in machine learning, which have a very different geometric and algebraic structure than $F_2^n$. It is not immediately clear from the paper how $F_2^n$-domain functions and their Fourier coefficients would be useful in applications such as regression. It would be great if the authors could provide examples of $F_2^n$-domain functions and applications of their Fourier coefficients in machine learning.\n    \nOur Response: Indeed, functions over real domains are common in many classical machine learning tasks. However, we want to emphasize that the problem of learning Fourier sparse functions defined over the Boolean hypercube $F_2^n$ has been a central theme in computational learning theory and has found important applications across various machine learning settings. Notable examples include learning cut functions of graphs and hypergraphs (which are closely related to hypergraph sketching), as well as evaluating decision trees of bounded depth.\n\nTo illustrate further, the cut function of a graph corresponds to a polynomial of degree at most $2$ in the Fourier basis, while the cut function of a degree $d$ hypergraph corresponds to a polynomial of degree at most $d$ (see Stobbe and Krause, 2012). Similarly, a Boolean decision tree of depth $d$ has a Fourier spectrum supported on coefficients of degree at most $d$ (see Mansour, 1994). Hence, these functions are naturally Fourier sparse, i.e., their Fourier spectrum is concentrated on low-degree terms. More recently, Fourier sparse functions have appeared in applications such as neural network hyperparameter optimization (see Hazan et al., 2018). Due to these, there has also been growing interest in learning Fourier sparse Boolean functions, also known as Fourier sparse set functions (see Amrollahi et al., 2019).\n\nIn addition to machine learning, learning Fourier sparse Boolean functions also plays a central role in cryptography. For example, the Goldreich-Levin theorem (Goldreich and Levin, 1989) shows how to construct hardcore predicates from any one-way function using a procedure that relies on learning large Fourier coefficients of certain Boolean functions.\n\nFinally, we comment that learning Fourier sparse functions falls into two broad categories of methods: Sparse Hadamard Transform (see Hassanieh et al., 2012; Indyk et al., 2014; Scheibler et al., 2015) and Compressed Sensing techniques (see Rudelson and Vershynin, 2008). However, both these lines of work assume prior knowledge of the sparsity level in the Fourier domain. Our work can thus serve as an important preprocessing step to efficiently estimate this sparsity level, up to desired approximation level in terms of Euclidean distance, which is also the natural distance measure for both of these approaches. We will revise the manuscript to better highlight the relevance of our results to the different areas of machine learning.\n\nReference:\n\n  1. Amrollahi, A., Zandieh, A., Kapralov, M., & Krause, A.: Efficiently learning Fourier sparse set functions. NeurIPS, 2019.\n  \n  2.  Hassanieh, H., Indyk, P., Katabi, D., & Price, E.: Nearly optimal sparse Fourier transform. STOC, 2012.\n  \n  3.  Hazan, E., Klivans, A., & Yuan, Y.: Hyperparameter optimization: a spectral approach. ICLR, 2018.\n  \n  4.  Indyk, P., Kapralov, M., & Price, E.: (Nearly) sample-optimal sparse Fourier transform. SODA, 2014.\n  \n  5. Kushilevitz, E., & Mansour, Y.: Learning decision trees using the Fourier spectrum. SICOMP, 1993.\n  \n  6.  Mansour, Y.: Learning Boolean functions via the Fourier transform. 1994\n  \n  7.  Rudelson, M., & Vershynin, R.: On sparse reconstruction from Fourier and Gaussian measurements. Commun. on Pure & App. Math., 2008.\n  \n  8.  Scheibler, R., Haghighatshoar, S., & Vetterli, M.: A fast Hadamard transform for signals with sublinear sparsity in the transform domain. IEEE IT, 2015.\n  \n  9. Stobbe, P., & Krause, A.: Learning Fourier sparse set functions. AISTATS, 2012.\n\n  10. Goldreich, O., &  Levin, L.: A hard-core predicate for all one-way functions. STOC, 1989.\n\n\nWe sincerely thank the reviewer for their careful reading of our work and for pointing out gaps in the presentation. We believe that incorporating these thoughtful concerns  will greatly enhance the clarity and overall quality of the paper. We would be glad to address any further comments or concerns the reviewer may have. We would be truly grateful if the reviewer would kindly consider revising their score in light of our responses."}, {"review_id": "oTDddOS3WZ", "reviewer": "Reviewer_S1nq", "summary": "This paper studies the tolerant property testing question of distinguishing functions over $\\mathbb{F}_2^n$ whose Fourier representations are close to being $s$-sparse, from those that are far from any such function in $\\ell_2$-distance, using black-box query access to the function. Such a function is $s$-sparse if it has at most $s$ non-zero Fourier coefficients. The goal is to minimize the number of queries. Previously, the state of the art bounds for this question were $\\widetilde{O}(s/\\epsilon^4)$ and $\\Omega(\\sqrt{s})$. This paper improves on both fronts, obtaining nearly tight bounds of $\\widetilde{O}(s/\\epsilon)$ and $\\Omega(s)$, thus essentially closing the book on this very natural problem.\n\nTheir algorithm works by testing sparsity of the function restricted to a random low-dimensional subspace. Their analysis relies on new Fourier-analytic results regarding the behavior of sparseness under random restrictions. \n\nTheir lower bound uses a reduction to the communication complexity problem of determining the rank of the sum of two matrices A,B held by two parties.  Their proof relies on a recent result on this problem due to Sherstov-Storozhenko from FOCS 2024.", "questions": "Main questions:\n\nIn the proof of Theorem 1.1, you say $\\zeta$ is an “estimate” of the distance of the restriction $f_A$ to being $s$-sparse (line 226-227), but then immediately in the next equation you seem to be defining it to be the exact distance (not an estimate). My confusion is also present in line (2) of the algorithm. Is $\\zeta$ an estimate or the exact distance? In either case, how are you computing $\\zeta$? This is very unclear to me. I also see how in the last paragraph of section 2 you mention that the proof assumes exact values for the Fourier coefficients of the restriction, but approximations suffice which can be computed using the appropriate number of queries. Even though this may be a simple technicality, I think it's important to have a complete rigorous proof by including these details.\n\nMinor typos:\n\nTypo in line 265: “where $f \\in MM_{r,n}$ function”\n\nTypo in line 269: “atmost”", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths: This paper obtains essentially tight bounds for what I consider a very natural problem in property testing, which may have nice applications for learning. The proofs are also elegant, and make use of sophisticated results in another area (communication complexity) in a nicely presented, modular way. I think the paper is also well organized and nicely written. \n\nI don’t see any real weaknesses with this work. I do have a question below, which I imagine the authors will be able to address. Conditioned on a satisfactory answer, I believe this paper should absolutely be accepted.", "was_revised": true, "final_justification": "This paper obtains a near-optimal algorithm for a very natural testing question. I also think the paper is well-written overall and the authors have addressed the concerns I had raised. Therefore, I think this paper is a clear accept and I am keeping my score a 5.", "rebuttal": "Reviewer's Question - 1: In the proof of Theorem 1.1, you say is an “estimate” of the distance of the restriction to being sparse (line 226-227), but then immediately in the next equation you seem to be defining it to be the exact distance (not an estimate). My confusion is also present in line (2) of the algorithm. Is an estimate or the exact distance? In either case, how are you computing? This is very unclear to me. I also see how in the last paragraph of section 2 you mention that the proof assumes exact values for the Fourier coefficients of the restriction, but approximations suffice which can be computed using the appropriate number of queries. Even though this may be a simple technicality, I think it's important to have a complete rigorous proof by including these details.\n\nOur Response: We are really thankful to the reviewer for pointing out the inconsistency. Indeed, the word ``estimate'' in line 226 is incorrect; it should refer to the exact distance, as the analysis in this part assumes access to exact Fourier coefficients. However, the algorithm, as presented in Algorithm~1, uses approximate values of the Fourier coefficients of the restricted function $f_A$. This transition is enabled in the later part of the analysis, in the last paragraph, as pointed out by the reviewer. Below, we provide a detailed explanation which we hope will clarify the apparent gap in the proof.\n\nSince the restriction $f_A$ is over an affine subspace $A \\subseteq F_2^n$ of dimension $k = dim(H) = \\log \\frac{4096s^2}{\\epsilon^2}$, one can compute the Fourier coefficients of $f_A$ exactly by querying all points in $A$, which leads to a query complexity of $\\widetilde{O}(s^2/\\epsilon)$. However, for query efficiency, the algorithm estimates the Fourier coefficients up to the desired accuracy $o(\\sqrt{\\epsilon/s})$. For each $\\alpha \\in F_2^k$, the Fourier coefficient is given by $\\widehat{f_A}(\\alpha) = E_{x \\in A} \\left[ f_A(x) \\cdot \\chi_\\alpha(x) \\right]$, where $\\chi_\\alpha(x) = (-1)^{\\langle \\alpha, x \\rangle}$. We estimate this by taking $m$ uniform random samples $x^{(1)}, \\dots, x^{(m)}$ from $A$ and computing the empirical average: $\\widetilde{f_A}(\\alpha) := \\frac{1}{m} \\sum_{i=1}^m f_A(x^{(i)}) \\cdot \\chi_\\alpha(x^{(i)})$. This is an unbiased estimator. Since each term lies in $\\lbrace -1, 1\\rbrace$, we can apply Hoeffding's inequality to bound the error:\n$Pr\\left[ \\left| \\widetilde{f_A}(\\alpha) - \\widehat{f_A}(\\alpha) \\right| > \\eta \\right] \\leq 2\\exp(-2m\\eta^2)$.\nTo ensure additive error at most $\\eta = \\sqrt{\\epsilon/64s}$ with confidence at least $1 - \\delta = 1 - \\frac{\\epsilon^2}{2^{16}s^2}$, it suffices to take\n$m = O\\left( \\frac{1}{\\eta^2} \\cdot \\log \\frac{1}{\\delta} \\right) = O\\left( \\frac{s}{\\epsilon} \\cdot \\log  \\frac{s}{\\epsilon}  \\right)$. Applying a union bound over the top $s$ coefficients ensures that all of them are estimated within the desired error with high probability. The total squared error across these coefficients is at most $s \\cdot \\left( \\frac{\\epsilon}{64s} \\right) = \\frac{\\epsilon}{64}$, which suffices for the algorithm's decision criterion.\n\nTherefore, the overall query complexity is $\\widetilde{O}(s/\\epsilon)$. \n\nWe thank the reviewer once again for pointing out this inconsistency. We will revise the final version to include the relevant details and ensure that the distinction between the exact analysis and the approximate implementation is made fully rigorous and transparent.\n\nWe appreciate all the reviewer’s editorial suggestions/questions and assure them that we will carefully address and incorporate all such comments in the final version of the paper. We truly appreciate the time and care taken in reviewing our work. We believe that incorporating these suggestions will significantly enhance the presentation of the technical content. We remain very happy to address any further questions or suggestions the reviewer may have."}, {"review_id": "5ln8nFHjml", "reviewer": "Reviewer_tqTn", "summary": "This paper studies the problem of testing if a boolean function is close to an $s$-sparse function (in the fourier domain) or far from it. \nThey study a simple algorithm which checks if the restriction of the target function $f$ to a random affine subspace is close to being $s$-sparse or far from it. This is a simple non adaptive algorithm that succeeds at testing with probability $2/3$ using $\\tilde O(s)$ queries.\n\nThey also demonstrate a lower bound of $\\Omega(s)$ queries, showing their algorithm is tight up to log factors. \n\nThis work improves upon prior work on Boolean functions which solves the same problem with a significantly larger number of queries. Prior work also had a lower bounds of $\\Omega(\\sqrt{s})$ on the problem, which is quadratically worse than the results of this paper. \n\nI view their main contribution as providing new structural lemmas that describe how Fourier-sparsity operates under restrictions to random subspaces, leading to an improved analysis of a simple algorithm.", "questions": "1. Can these techniques be extended to fields beyond $F_2$?\n2. For the case of Boolean functions, what is the main reason this algorithm and analysis overcomes prior work? \nIn this setting aren’t the Hamming and squared 2-norm distances related?\n3. This paper required oracle access, is there any reason to expect that random access would result in much worse guarantees? I.e. is there a stronger lower bounds assuming the access to the function is different?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. The algorithm is quite simple and the analysis is pretty concise.\n2. It improves significantly upon the current state of the art to essentially near-optimal. \n\nI think this paper is quite nice and uses a small insight to demonstrate that a simple algorithm is near-optimal. \n\nWeakness:\n1. This paper only focuses on the case where the underlying field is $F_2$.\n2. I think since the algorithm is extremely simple, it would be good to spend some more time explaining what prior work did and what exactly the main difference is that leads to them having much worse guarantees and this paper having near-optimal guarantees. I think the authors could have perhaps spent some time explaining this contribution a little better.", "was_revised": true, "final_justification": "I think this is an interesting paper and vote to accept it.", "rebuttal": "Reviewer's Question - 1: Can these techniques be extended to fields beyond $F_{2}^{n}$ \n\nOur Response: We would like to emphasize that our technique naturally extends to functions $f : F_q^n \\to \n\\mathbb{R}$ with bounded $\\ell_2$ norm, with only a mild increase in complexity, specifically, up to a multiplicative $\\log q$ factor. We chose to present our analysis primarily for functions over $F_2^n$ since such functions are more commonly studied in computational learning theory. Moreover, to better highlight our central idea—that a simple algorithm can yield near-optimal bounds.\n\nWe also believe that similar testing algorithms may extend to the most general setting of Fourier analysis on finite Abelian groups $G$, with functions $f : G \\to \\mathbb{C}$. However, many of the techniques developed in our work do not extend directly to this broader setting. For instance, the notion of a subspace, which plays a key role in our analysis, does not naturally generalize to arbitrary Abelian groups. One would need to identify suitable structural analogues, such as Bohr neighborhoods, to overcome this challenge. We are actively exploring this direction as part of our ongoing work.\n\nReviewer's Question - 2: For the case of Boolean functions, what is the main reason this algorithm and analysis overcomes prior work? In this setting aren’t the Hamming and squared 2-norm distances related?\n\nOur Response: First, we emphasize that our setting involves real-valued functions of the form $f : F_2^n \\to \\mathbb{R}$ with bounded Euclidean norm, which is the most commonly considered setting in machine learning. Functions of the form $g : F_2^n \\to F_2$ form a special subset of this broader class. The reviewer is indeed correct in noting that for Boolean-valued functions, Euclidean distance and Hamming distance are equivalent up to a constant factor. However, for real-valued functions, such as the ones we study, the Hamming distance is not a meaningful notion. In the computational learning theory literature, particularly in problems involving the sparse Hadamard transform and sparse recovery, approximation is typically studied in terms of Euclidean ($\\ell_2$) distance. This motivates our focus on functions $f : F_2^n \\to \\mathbb{R}$ and analysis in the Euclidean setting.\n\nWe believe that a key technical contribution of our work is the analysis of the Fourier structure of the restriction of a function to a small subspace, which underpins the efficiency of our algorithm. Specifically, we show that when the goal is to estimate the total squared weight of the top $s$ Fourier coefficients, it suffices to analyze the restriction of the function to a suitably chosen low-dimensional subspace. Such low-dimensional projections are a standard technique in the sublinear algorithms literature, particularly in numerical linear algebra, where problems such as matrix-vector multiplication or eigenvalue approximation are addressed by constructing low-dimensional sketches and operating on these reduced representations.\n\nBeyond this projection-based approximation, our work introduces a second important ingredient: a refined analysis of the concentration behavior of the restricted Fourier coefficients. In particular, we derive a novel $\\ell_1$ concentration bound for the \"bucketed\" Fourier coefficients obtained through a Fourier hashing technique. While previous work has primarily focused on $\\ell_2$ concentration of such \"bucketed\" coefficients, typically via techniques analogous to the Count-Min Sketch, our analysis is inspired by the Count Sketch method used for heavy hitter detection in data streams. We believe that this refined concentration analysis is crucial in giving us our near-optimal and conceptually simple algorithm.\n\nReviewer's Question-3: This paper required oracle access, is there any reason to expect that random access would result in much worse guarantees? I.e. is there a stronger lower bounds assuming the access to the function is different?\n\nOur Response: Testing in random example models is significantly more challenging. To the best of our knowledge, even for the case of linearity testing, where the target functions are $1$-Fourier sparse, it is not known how to design a tester with sample complexity independent of the ambient dimension $n$. In contrast, in the query access model, linearity testing can be performed efficiently using the well-known $3$-query BLR test. The main goal of our work is to estimate the Fourier sparsity level of a function with the number of queries depending only on the sparsity parameter and the proximity parameter, while remaining independent of the ambient dimension $n$.\n\nFinally, we would like to sincerely thank the reviewer once again for their thoughtful and encouraging comments. We appreciate the time and care taken in reviewing our work. We remain very happy to address any further questions or suggestions the reviewer may have."}, {"review_id": "wQITrwui9p", "reviewer": "Reviewer_XNx6", "summary": "The paper focuses on the problem of distance estimation of a function $f$ to the closest function which is $s$-sparse in the Fourier basis. To elaborate:\n- The function $f$ maps each $x$ in $\\\\{\\pm 1\\\\}^n$ to a real number $f(x)$. The algorithm can query the value of $f$ on inputs of its choice.\n- A function $f’$ over $\\\\{\\pm 1\\\\}^n$ has Fourier sparsity $s$ if it equals to a linear combination of $s$ functions of the form $\\prod_{i \\in S} x_i$. For example, the function $f’(x)=x_1+0.1\\cdot x_2x_3x_4+5 \\cdot x_2x_3$ has Fourier sparsity $3$.\n- When speaking of a distance between a pair of functions, the paper considers the $L_2^2$ distance between a pair of functions $f$ and $f’$, which is defined as the average of $(f(x)-f’(x))^2$ over all $x$ in $\\\\{\\pm 1\\\\}^n$. \n- The goal of the algorithm is to approximate, up to an additive error $\\epsilon$, the smallest distance of the function $f$ to an $s$-sparse function $f’$. \n\nMotivation for this work: in many settings in machine learning data is approximately sparse in some basis, such as the Fourier basis. This type of tester would allow one to very quickly check whether the data is indeed Fourier-sparse without having to compute all the Foureir coefficients.\n\nThis work shows how to accomplish this task using $\\tilde{O}(s/\\epsilon)$ queries. The work also gives a hardness resulting showing that $\\Omega(s)$ queries are necessary.\n\nThis and closely related problems have been the focus of multiple previous papers. The most relevant one is [Yaroslavtsev and Zhou 2020] which studied the exact same problem studied here and gave an algorithm that uses $\\tilde{O}(s/\\epsilon^4)$ queries. [Yaroslavtsev and Zhou 2020]  also showed that $\\Omega(\\sqrt{s})$ queries are necessary. Thus, when compared with [Yaroslavtsev and Zhou 2020], this work:\n- improves the $\\epsilon$-dependence for number of queries used by the algorithm from $\\tilde{O}(s/\\epsilon^4)$ to $\\tilde{O}(s/\\epsilon)$\n- improves the hardness result from $\\Omega(\\sqrt{s})$ query lower bound to $\\Omega(s)$.\n\nThe algorithm in this work works by considering a restriction of the function $f$ to a random small-dimensional affine subspace of $\\\\{\\pm 1\\\\}^n$. The algorithm estimates the distance of the resulting restriction to the closest s-sparse function. It is shown via Fourier-analytic argument that, with high probability, the resulting estimate will be a good approximation to the distance of the original function $f$ to the closest s-sparse function. \n\nThe hardness result is shown by a reduction to a problem in communication complexity. In the communication problem, two parties have a matrices A and B respectively, and the goal of the two parties is to approximate the rank of the matrix A+B. It is shown that a $o(s)$-query algorithm for the original task would imply a low-communication protocol for this task, contradicting known communication lower bounds.", "questions": "- Judging by the citation record of [Yaroslavtsev and Zhou 2020], their algorithm has not found wide application. Do you think this was only due to the $\\epsilon$-dependence of their query complexity, or are there other reasons?\n\n- What is the run-time of the algorithm? Theorem 1.1 only lists the query complexity. How does the run-time compare to that of [Yaroslavtsev and Zhou 2020]?\n\n- In the introduction, you mention sparsity in other bases such as general Fourier basis, wavelet basis and learned dictionaries. What are some obstacles for extending your algorithm to work in these more general settings?", "limitations": "Yes. Answers to the questions above could potentially help the readers further contextualize some of the limitations of this work.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n- The problem is quite natural and was studied in multiple papers prior to this work.\n\n- This work gives optimal query bounds up to logarithmic factors.\n\n- The algorithm is quite simple and natural.\n\nWeaknesses\n\n- One could argue that the algorithmic improvement – from $\\tilde{O}(s/\\epsilon^4)$ to $\\tilde{O}(s/\\epsilon)$ – over previous work is quite incremental.\n\nMisc comment:\n\n- Given that the improvement over previous work is in $\\epsilon$-dependence of the query complexity, I think the $\\epsilon$-dependence should be included in the abstract.", "was_revised": true, "final_justification": "Raising my score to 5 (Accept), based on clarifications given in the rebuttal regarding run-time of the algorithm and potential extensions to wider settings.", "rebuttal": "Reviewer's Question-1:  Judging by the citation record of [Yaroslavtsev and Zhou 2020], their algorithm has not found wide application. Do you think this was only due to the dependence of their query complexity, or are there other reasons?\n \nOur Response: Frankly speaking, we believe that the work of Yaroslavtsev and Zhou (2020) may have missed the attention of its intended audience, possibly due in part to its publication in a theoretical computer science venue.\n\nThat said, we would like to emphasize the relevance of their work, and our own, in the broader context of computational learning theory and machine learning. Over the past two decades, there has been sustained interest in the sparse Hadamard transform and compressed sensing-based sparse recovery techniques for learning Fourier-sparse Boolean functions, as such models naturally arise in various machine learning applications. Examples include learning cut functions of graphs and hypergraphs (closely related to hypergraph sketching), as well as evaluating decision trees of bounded depth.\n\nTo elaborate, the cut function of a graph corresponds to a polynomial of degree at most $2$ in the Fourier basis, while the cut function of a degree-$d$ hypergraph corresponds to a polynomial of degree at most $d$ (see Stobbe and Krause, 2012). Likewise, a Boolean decision tree of depth $d$ has its Fourier spectrum supported on coefficients of degree at most $d$ (see Mansour, 1994). These functions are therefore naturally Fourier sparse, meaning their Fourier mass is concentrated on low-degree terms. More recently, such Fourier-sparse models have also appeared in applications like neural network hyperparameter optimization (see Hazan et al., 2018). This has led to increased interest in the learning of Fourier-sparse Boolean functions, often referred to as Fourier-sparse set functions (see Amrollahi et al., 2019).\n\nHowever, both sparse Hadamard transform and compressed sensing-based recovery methods typically require prior knowledge of the sparsity level (and in some cases, the approximation accuracy in the Euclidean setting) to properly configure algorithmic parameters. We strongly believe that our sparsity tester can serve as a valuable preprocessing step in such contexts, by providing reliable estimates of the Fourier sparsity level before applying these recovery techniques.\n\n\nReference\n\n1. Indyk, P., Kapralov, M., \\& Price, E.: (Nearly) sample-optimal sparse Fourier transform. SODA, 2014.\n  \n2. Kushilevitz, E., \\& Mansour, Y.: Learning decision trees using the Fourier spectrum. SIAM Journal on Computing, 1993.\n\n3. Mansour, Y. (1994). Learning Boolean functions via the Fourier transform. In Theoretical Advances in Neural Computation and Learning, 391–424. Springer.\n\n4. Rudelson, M., \\& Vershynin, R.: On sparse reconstruction from Fourier and Gaussian measurements. Communications on Pure and Applied Mathematics, 2008.\n\n5. Scheibler, R., Haghighatshoar, S., \\& Vetterli, M.: A fast Hadamard transform for signals with sublinear sparsity in the transform domain. IEEE IT, 2015.\n\n6. Stobbe, P., \\& Krause, A.: Learning Fourier sparse set functions. AISTATS, 2012.\n\n7. Hassanieh, H., Indyk, P., Katabi, D., \\& Price, E.: Nearly optimal sparse Fourier transform. STOC, 2012.\n\n8. Hazan, E., Klivans, A., \\& Yuan, Y.: Hyperparameter optimization: a spectral approach. ICLR, 2018.\n    \n\nReviewer's Question-2: What is the run-time of the algorithm? Theorem 1.1 only lists the query complexity. How does the run-time compare to that of [Yaroslavtsev and Zhou 2020]?\n\nOur Response: We regret overlooking this point in our original submission. In fact, our algorithm also improves upon the runtime of [Yaroslavtsev and Zhou, 2020], which is $\\tilde{O}(s/\\epsilon^4)$, whereas our runtime is $\\tilde{O}(s/\\epsilon)$. We are truly grateful to the reviewer for bringing this to our attention.\n\nReviewer's Question - 3: In the introduction, you mention sparsity in other bases such as general Fourier basis, wavelet basis and learned dictionaries. What are some obstacles for extending your algorithm to work in these more general settings?\n\nOur Response: We thank the reviewer for raising this important and insightful question. Our goal is to design sparsity testing algorithms whose query complexity depends only on the sparsity parameter $s$ and the approximation parameter $\\epsilon$, and is independent of the ambient dimension $n$. We demonstrate that such dimension-independent testing is indeed possible for functions over $F_2^n$ with bounded $\\ell_2$ norm. Functions of this kind arise naturally in machine learning applications, including junta learning, decision tree learning, and hypergraph sketching. We believe the techniques introduced in our work could be extended to other domains where Fourier analysis is applicable.\n\nIn particular, our methods naturally generalize to functions $f : F_q^n \\to \\mathbb{R}$ with bounded $\\ell_2$ norm, incurring only a mild $\\log q$ multiplicative overhead in complexity. We have chosen to focus on the $F_2^n$ setting in our presentation because such functions are more commonly studied in the computational learning theory literature, and this setting allows our central ideas—particularly the simplicity and near-optimality of our algorithm—to be presented more clearly.\n\nWe also believe that similar testing algorithms may be extendable to more general settings, such as functions $f : G \\to \\mathbb{C}$, where $G$ is a finite Abelian group and Fourier analysis still applies. However, many of our techniques do not directly carry over to this setting. Notably, the notion of a subspace—which is central to our analysis—does not have a straightforward analogue in general finite Abelian groups. Extending our framework would likely require using suitable structural surrogates, such as Bohr neighborhoods. We view this as an exciting direction and are actively exploring it as part of our ongoing research.\n\nWe would also like to reiterate that sparsity testing in more general bases has been considered in prior work. In particular, Barman et al. (2018) study related problems where the goal is to test whether a vector (or a collection of vectors) can be expressed as sparse linear combinations over known or unknown bases, using random projections and tools from high-dimensional geometry. However, the query complexity of their algorithms depends on the ambient dimension, making them less suitable for very high-dimensional regimes.\n\nIn contrast, our focus is on testing problems where the query complexity is completely independent of the ambient dimension. Understanding precisely which classes of functions and bases allow for such dimension-independent testing is an intriguing and fundamental question.\n\nReference\n\n1. Barman, S., Bhattacharyya, A., and Ghoshal, S.: Testing sparsity over known and unknown bases. ICML, 2018.\n\nFinally, we thank the reviewer for their careful reading of our work, for identifying gaps in the presentation, and for suggesting insightful directions for further research. We believe that incorporating these thoughtful suggestions will significantly improve the clarity and overall quality of the paper. We would be happy to address any additional comments or concerns the reviewer may have. We would be truly grateful if the reviewer would kindly consider revising their score in light of our responses."}, {"review_id": "yYjgG4ssvd", "reviewer": "Reviewer_r9gD", "summary": "This paper studies the property testing problem of Fourier sparsity: It tests whether a given unknown function $f: \\mathbb{F}^n_2 \\rightarrow \\mathbb{R}$ is close to or far from being $s$-Fourier sparse in the $\\ell_2$ distance, using a limited number of queries to $f$. This paper shows a (nearly) matching upper and lower bound on the query complexity. The upper bound is shown by testing the function under the restriction to a random affine subspace. By considering a random affine subspace, the tester induces a partition of the spectrum into cosets (viewed as hash buckets), isolating ''heavy'' Fourier coefficients of the function in expectation. Then with a small number of queries, the tester can approximate the contribution from each coset and thus certify whether only few ''heavy'' buckets exist, i.e. the function is sparse. The lower bound is shown via a reduction from the matrix rank problem in the communication complexity. The authors draw a connection between the matrix rank and the Fourier sparsity via a family of functions called Maiorana–McFarland functions.", "questions": "1. Could the authors add an explicit comparison between their proof and that of [Gopalan et al. 2011], clearly highlighting which aspects are novel?\n\n2. The reduction connecting matrix rank to Fourier sparsity via a Maiorana–McFarland function seems to be potentially useful beyond the setting in this paper. Have similar connections been observed or applied previously for other purposes?", "limitations": "See comments in the **Strengths And Weaknesses** section.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strength**:\n\n\n1. The problem definition, the contribution, and the ideas of the proofs are clearly outlined at the beginning of the paper. Therefore, the main body of the paper feels very easy to follow.\n\n2. Testing the Fourier sparsity of a function via queries feels like a natural and important problem. One can easily imagine its usefulness in many downstream applications in the area of property testing, where one might need to assume the Fourier sparsity of a given function. This paper essentially settles this problem under the $\\ell_2$ distance, by showing a matching upper ($\\tilde{O}(s/\\epsilon)$) and lower bound ($\\Omega(s)$) of the query complexity. While an upper bound linear in $s$ has already been shown in [Yaroslavtsev and Zhou. 2020], this paper reduces the dependency on $\\epsilon$ from $1/\\epsilon^4$ to $1/\\epsilon$. On the other hand, the improvement over the lower bound, from $\\Omega(\\sqrt{s})$ to $\\Omega(s)$, nicely complements the upper bound.\n\n**Weakness**:\n\nI am concerned that although the upper-bound proof largely builds on the approach of [Gopalan et al. 2011], this connection is never acknowledged. The only mention of [Gopalan et al. 2011] in the $\\textbf{Related Work}$ paragraph is that they study a different (Hamming‐distance) version and achieve poly($s$) queries. In my opinion, it would be appropriate to summarize and compare their proof ideas in the subsequent paragraph $\\textbf{Regarding the proof of Theorem 1.1}$.\n\nFrom my understanding, both papers hash the Fourier spectrum via a random subspace restriction to isolate heavy coefficients into separate buckets, and then use concentration‐of‐measure to argue that if too many coefficients collide, then the test will reject. Concretely, both papers hash the Fourier coeffcients into random cosets. After that, both estimate the weight in each bucket by sampling. Finally, both paper argue by pairwise‐independence and Chebyshev/Chernoff‐type bounds that, if the function were far from sparse, then either too many coefficients would collide in the same bucket, or too much Fourier mass would leak into many buckets—so the tester rejects with high probability. \n\nI understand that solving this problem under the $\\ell_2$ distance might require new analytic ingredients. But without an explicit comparison to [Gopalan et al. 2011], it is difficult to tell which parts of the proof are novel. Moreover, statements like  \n> \"Surprisingly, despite being a central and natural affine-invariant property, Fourier sparsity has largely resisted similar progress through this lens\" (restricting the function to random low-dimensional affine subspaces and tests the property on these restriction),\n\n> \"Crucially, we establish new Fourier analytic results that describe how sparsity behaves under such restrictions\". \n\ncan give the impression that the proof strategy of this paper is entire original, when in fact it closely parallels prior work.\n\nIn general, I think adapting the proof from the Hamming distance case to the $\\ell_2$ setting can be valid contribution -- indeed, it leads to an improved  $\\tilde{O}(s/\\epsilon)$ upper bound, which nearly match the new lower bound. However, given the current presentation of this paper, I cannot recommend acceptance.", "was_revised": true, "final_justification": "In the rebuttal, the authors discuss the novelty and similarity in techniques compared to previous works with more details and highlights their contribution. These resolve my initial concerns. Condition on this discussion being incorporated in the paper, I am willing to change my rating upward.", "rebuttal": "Reviewer's Question-1: Could the authors add an explicit comparison between their proof and that of [Gopalan et al. 2011], clearly highlighting which aspects are novel?\n\nOur Response: We briefly compare our setting and techniques with the work of Gopalan et al. Their goal is to test whether a Boolean function $f: F_2^n \\to \\lbrace +1, -1 \\rbrace $ is $s$-Fourier sparse or at least $\\epsilon$-far from every $s$-sparse Boolean function, under the Hamming distance model. In contrast, our setting involves real-valued functions $f: F_2^n \\to \n\\mathbb{R}$. We aim to distinguish whether there exists an $s$-Fourier sparse function $g: F_2^n \\to \\mathbb{R}$\nsuch that $\\mid \\mid f - g \\mid\\mid_2 \\leq \\delta$, or whether $f$ is $(\\delta + \\epsilon)$-far from every such function in terms of $\\ell_{2}$-distance. \n\nTo clarify, the Hamming distance between two Boolean functions $f,g: F_2^n \\to  \\lbrace +1, -1 \\rbrace$ is defined as:\n$\\mid\\mid f - g \\mid\\mid_0 := Pr_{x \\in F_2^n} [ f(x) \\neq g(x) ]$,\nwhile the Euclidean distance between two real-valued functions $f,g: F_2^n \\to \\mathbb{R}$ is:\n$\\mid\\mid f - g \\mid\\mid_2 := \\left( E_{x \\in F_2^n}[(f(x) - g(x))^2] \\right)^{1/2}$.\n\nThus, both the problem formulation and the nature of the object of interest in this work differ significantly from the Boolean setting of Gopalan et al. Nevertheless, we acknowledge their work as a foundational milestone in the study of Fourier sparsity testing.\n\nAs for techniques, the two works also diverge significantly. Gopalan et al. work with the Fourier coefficients of the original Boolean function directly. Their method involves hashing the Fourier spectrum via coset hashing and then estimating the collective weight of the Fourier coefficients falling into a single bucket. To the best of our understanding, their main contribution is to show that for Fourier-sparse Boolean functions, the magnitude of individual Fourier coefficients cannot be too small. Their tester ultimately reduces the problem to counting large-magnitude coefficients. \n \n\nIn contrast, our method analyzes the function restricted to a randomly chosen subspace. We approximately (in Euclidean sense)  recover the Fourier spectrum of this restricted function and infer the Fourier sparsity of the original function from it. We derive a new structural relationship between the Fourier coefficients of the restricted function and those of the original function, and show that under a suitable choice of subspace, the magnitudes of these coefficients closely approximate those of the original function. This relationship plays a central role in our analysis.\nWe highlight that Gopalan et al.'s hashing of the Fourier spectrum of the original function to a coset still yields a function defined over the full domain $F_2^n$. As we have already discussed, we restrict the original function to a random subspace of the full domain $F_{2}^{n}$.\n\nFinally, we would like to add that our algorithm is extremely simple and lightweight, and we wanted to complete the writing of the paper within the suggested page limit. Therefore, we could not elaborate on all these aspects in the current version. We will definitely expand on these details and provide a more thorough discussion in the final version of the paper.\n\nReviewer's Question - 2: The reduction connecting matrix rank to Fourier sparsity via a Maiorana–McFarland function seems to be potentially useful beyond the setting in this paper. Have similar connections been observed or applied previously for other purposes?\n\nOur Response: The reduction connecting matrix rank to Fourier sparsity via a Maiorana–McFarland function appears to be potentially useful beyond the setting of this paper. Similar kinds of reductions have been used in the work of Grigorescu, Wimmer, and Xie. In their paper ``Tight Lower Bounds for Testing Linear Isomorphism\", they used similar reductions to establish lower bounds for linear isomorphism testing. However, we emphasize that translating their reduction to our context would only yield a lower bound that is logarithmic in the sparsity parameter. Our main contribution lies in refining this framework by invoking a more general version of the rank estimation problem and constructing a specific class of functions that exhibit a controllable trade-off between Fourier dimension and sparsity. We believe that this reduction technique may be of independent interest in other contexts where such dimensionality versus sparsity trade-offs play a central role.\n\nFinally, we sincerely thank the reviewer once again for their valuable time and constructive feedback. We believe that incorporating these suggestions will significantly improve the presentation of the paper. We have made every effort to address each of the comments and concerns to the best of our ability, and we would be happy to engage further should any additional questions arise. We would be truly grateful if the reviewer would kindly reconsider their score for this submission in light of our responses."}]

Author rebuttal:

Meta-review: This paper studies testing the sparsity of the Fourier coefficients of real-valued functions over the boolean hypercube. The authors give an algorithm that uses $\tilde{O}(s/\varepsilon)$ queries to determine whether the Fourier coefficients are $s$-sparse or at least $\varepsilon$-far from $s$-sparse in squared $L_2$ distance. They also achieve a lower bound of $\Omega(s)$. By comparison, the previous upper and lower bounds were $\tilde{O}(s/\varepsilon^4)$ and $\Omega(\sqrt{s})$. All reviewers agree that these improvements are quantitatively valuable, the algorithm is quite simple, and the manuscript is generally accessible. 

During the rebuttal phase, the authors suggested a number of actionable items in direct response to the initial reviews. I believe these changes could strengthen the overall impact of the work and thus I encourage the authors to take these points into consideration.
Decision: Accept (poster)