Testing Fourier Sparsity via Implicit Sensing
Authors: Arijit Ghosh
Subhamoy Maitra
Manmatha Roy
Venue: ICLR 2026 Poster (2026)
Keywords: Learning Theory
Fourier Analysis
Fourier Sparsity
Sublinear Algorithm
Property Testing
Comprssed Sensing
Primary area: learning theory
TL;DR: We present nearly tight bounds for testing Fourier-sparse Boolean functions, achieving a $\widetilde{O}(s^4)$ tester and an $\Omega(s)$ lower bound via new analytic and structural techniques.

Abstract: Boolean functions constitute a fundamental object of study in machine learning and theoretical computer science. Among their various complexity measures, Fourier sparsity, the number of nonzero coefficients in a function’s Fourier expansion, serves as a natural indicator of structural simplicity. For more than three decades, the problem of learning Boolean functions with sparse Fourier representations has occupied a central place in computational learning theory. A major line of progress has produced algorithms whose complexities depend primarily on the sparsity parameter itself. However, these methods typically assume that this parameter is known in advance.
In this work, we explore the problem of Fourier sparsity testing, which naturally relates to this question. Given query access to a Boolean function $f : \mathbb{F}_2^n \to \{ -1, +1 \}$, we seek to determine whether it is $s$-Fourier sparse or far (under Hamming distance) from every such function.

Our contributions are twofold. On the algorithmic side, we design a new tester with query complexity $\widetilde{O}(s^4)$, independent of the ambient dimension. On the lower bound side, we prove that any tester requires at least $\Omega(s)$ queries. Both bounds improve upon the best known results of Gopalan et al. (SICOMP 2011), who obtained a tester with query complexity $\widetilde{O}(s^{14})$ and a lower bound of $\Omega(\sqrt{s})$. For the upper bound, we introduce a refined notion of a sampler inspired by the junta testing framework and combine it with $\ell_1$-minimization-based compressed sensing techniques. In doing so, we develop a novel method for sampling leaves of parity decision trees associated with Fourier-sparse Boolean functions. The lower bound is obtained via a reduction from communication complexity, leveraging structural properties of Fourier coefficients of a specific class of cryptographically hard functions.

Published as a conference paper at ICLR 2026
TESTING FOURIER SPARSITY VIA IMPLICIT SENSING
Arijit Ghosh Indian Statistical Institute Kolkata 700108, India
Subhamoy Maïtra
Indian Statistical Institute
Kolkata 700108, India
mait raatra. subhamoy8gmail com
Manmatha Roy
Indian Statistical Institute Kolkata 700108, India reach. wwnmatmaangaaaaaaaa.a com
ABSTRACT
Boolean functions constitute a fundamental object of study in machine learning and theoretical computer science. Among their various complexity measures, Fourier sparsity, the number of nonzero coefficients in a function's Fourier ex- pansion, serves natural indicator of structural simplicity. For more than three decades, the problem of learning Boolean functions with sparse Fourier represen- tations has occupied central place in computational learning theory. A major line of progress has produced algorithms whose complexities depend primarily on the sparsity parameter itself. However, these methods typically assume that this parameter is known in advance. In this work, we explore the problem of Fourier sparsity testing, which naturally relates to this question. Given query access to Boolean function f F? + {-1,+1}, we seek to determine whether it is s-Fourier sparse or far (under Hamming distance) from every such function.
Our contributions are twofold. On the algorithmic side, we design a new tester with query complexity Ö(s*), independent of the ambient dimension. On the lower bound side, we prove that any tester requires at least {?(s) queries. Both bounds improve upon the best known results of Gopalan et al. (SICOMP 2011), who obtained tester with query complexity ((s²4) and lower bound of ((V3). For the upper bound, we introduce a refined notion sampler inspired by the junta testing framework and combine it with l imiiimization-baseee compressed sensing techniques. In doing so, we develop novel method for sampling leaves of parity decision trees associated with Fourier-sparse Boolean functions. The lower bound is obtained via a reduction from communication complexity, leveraging structural properties of Fourier coefficients of specific class of cryptographically hard functions.
INTRODUCTION
Boolean functions are fundamental machine learning and theoretical computer science, as they naturally model decision rules in binary classification, logical circuits, and related computational processes. They have been extensively studied in learning theory (Keams & Vazirani] 1994), com- plexity theory (O'Donnell 2014),, and cryptography (Carlet) 2020). Among various structural mea- sures, one that is particularly important in the literature on learning theory is Fourier sparsity, which counts the number of nonzero coefficients in the Fourier expansion over By. Formally, for f: F2 + +1}, its Fourier expansion is given by,
f(x) = (x)=EAi f(a)
(a(x) = (-1)(x,a))
GEFE
The Fourier support of f is defined as the set of nonzero Fourier coefficients, i.e., supp(f) {a f(a) * 0}. We say that f is s-Fourier sparse if (supp(f) S

---

Published as a conference paper at ICLR 2026
Many natural classes of Boolean functions, such hypergraph cut functions and bounded- -deth de- cision trees, are Fourier sparse, and learning such functions has long been central in computational learning theory. The study of learning Fourier-sparse Boolean functions dates back to the pioneering work of Kushilevitz & Mansour (193)). inspired by Goodreich & Levin (1989). Over the past two decades, there has been renewed interest in exact reconstruction with complexity primarily depen- dent on the sparsity parameter. Two main algorithmic paradigms are based on the Sparse Hadamard Transform (Stobbe & Krause 2012; Indyk al., 2014] Hassamich et al. 2012) and compressed sensing techniques Haviv & (20e))(2017) A common assumption in these lines of work is that the sparsity level is known in advance, which may not hold in many practical settings, Moreover, exact reconstruction methods, such as l mi-iimimioaioon based compressed sensing, succeed only when the function exactly, or sufficiently close to, s-Fourier sparse, typically requiring either exact spar- sity or Hamming distance at most o(1 /s) from the nearest s-sparse function. Thus, some form of certification of Fourier sparsity is important for obtaining meaningful recovery guarantees. We study the problem of testing Fourier sparsity under membership query access, for Boolcan functions f: 123 - ([1,,+1 where the tester can query (x) on inputs of its choice but has no access to its internal structure.
Problem Statement: Given parameter c > 0 and black-box query access to a Boolean function f Fž - (-1,+1}, decide whether f is s-Fourier sparse or e-far from every s-Fourier sparse Boolean function, where distance is measured under the Hamming sense:
disto(g. h) Pr [g(x) + h(z)].
#EF2
The efficiency of a Fourier sparsity tester is measured by its query complexity, i.c., the number of queries makes the target function.
Related Work. A related version has been studied for real-valued functions / IF2 >> R, where distance is measured via the Euclidean norm,
distz (ELI(((=
Yaroslavtsev & Zhou (2020) showed that testing closeness to s-Fourier-sparse functions under this metric can be achieved with (ss) queries, and they established an 22 (VV) lower bound. More recently, Ghosh & Roy (2025) presented simpler tester with Ö(s) query complexity together with matching {2(s) { lower bound, thereby nearly closing the gap up to polylogarithmic factors. However, one should note that while closeness in the Hamming sense implies closeness in the Euclidean sense, the converse may not be true. To illustrate, consider two scenarios. In the first case, if f is an exactly Fourier--pprre Boolean function with precisely k nonzero Fourier coefficients, then each of these coefficients must be large in magnitude, i.e., ((1/k). In the second, a Boolean function with k large Fourier coefficients but also tail of many small, nonzero coefficients with small &g norm. A k k-Fourier sparsity tester under the Euclidean distance would accept both types of functions, whereas tester under the Hamming distance should accept only the first type. This makes testing Fourier sparsity in the Hamming sense comparatively harder: one must certify not only the presence of k large Fourier coefficients but also the absence of Fourier tail.
The problem of testing Fourier sparsity under Hamming distance was first studied by Gopalan et al. (2011). who gave a non-adaptive tester with query complexity O(5 log s/e2 log 8) and proved lower bound of Ω( ()v)). Furthermore, Fourier sparsity is affine-invariant, in the sense that it remains unchanged under affine transformations of the domain. Consequently, is, at least in principle, amenable testing via general regularity- Bhattacharyya et al. 2013] Hatami & Lovett, 2013): however, such approaches incur impractical tower-type query complexities.
Tranworks(KKuffaa & Sudan 2008
We close the gap between existing upper and lower bounds for Fourier spar- sity testing. Our main results are follows.
Our Contributions.
Upper bound. We design non-adaptive tester with query complexity Ö(st), substantially improving upon the previous Ö(s14) bound of Gooalan al. (001))
2

---

Published as a conference paper at ICLR 2026
Theorem 1.1. Let 0 Dand O, and let FF2 + (-1,++1) be unknown Boolean function accessible via membership queries. There exists a non-adaptive property testing algorithm that distinguishes whether f is s-Fourier sparse e-far (in Hamming distance) from every function, with success probability least 2/3, using Ö 1//e queries
Lower bound. We prove quadratically stronger lower bound of 12(s), improving upon the previous best (1())) bound of Gopalan al. (011))
Theorem 1.2. Any (possibly adaptive) property testing algorithm that distinguishes whether a Boolean function is s-Fourier sparse or (1/4)-far (in Hamming distance) from every s-Fourier sparse function, with success probability at least 2/3, must make at least [2(s) queries.
For the upper bound, we design a tester that refines the notion of sampler from the junta testing framework of Chakraborty et al. (201T) and combines it with E--minimization based compressed sensing framework. A main ingredient of our algorithm is a new sampling method for parity decision trees, which arises naturally in the analysis of Boolean functions. On the other hand, for the lower bound, we achieve a quadratic improvement by reducing Fourier sparsity testing to certain linear- algebraic problem in communication complexity. Exploiting structural properties the Maiorana- McFarland family (McFarland 1973), ) we show that any tester, adaptive non-adaptive, must make at least (2)) queries. Our techniques are of independent interest and have potential applications in learning theory, property testing, and other algorithmic questions related harmonic analysis.
PRELIMINARIES
We the following notations and background results in the rest of the paper.
By Boolean function mean functions of the form f: F3 (-1,+1}. Given FF R, the expected value Eg [f] is defined as Eg := ExEr; f(x).
For a = (aI....,a., and 3 = (B Bx) in F2, their inner product is 8) =
For f.g: F + I. their inner product is (f.g) = 2 22 f(z)g(z).
Given a E Fg. character function Xa F2 + 1-1,+1} corresponding to a is defined as Xa (2) = (-1) ().a)))) Note that the character functions (Xa a E Fă} are orthogonal, that is,
0 if + B if B,
(Xa Xa)
and character functions also forms a basis for all real-valued functions on Ey.
Fourier transformation of function f F2 + IR is defined as f(a)) = (f.xa) = Ex [f(xx)((x)) , for all a E By. By, Fourier inversion formula, for all x Fy, we have
f(x) Σ fa))x(()) aEFE
For a function f : F3 >> TR, Parseval's identity says that (f.f) Enepz }(a)2. Addi- tionally, if f is also Boolean functions then (f.f)=1. 11
For any two functions h.h. : Fy + R, from Plancherel theorem we have (g. h) =
Enery ((a)
Given Boolean functions f.g F. + (-1,+11), the Hamming distance (fo-distance) is
d(f.g) where d(f.g) := Hx E my f(x) * g(x)}1. defined as ((f,g) g) is 8(f.g) := 2n
For E P Rmxx rank (A) denotes its rank over F2.
Here Ö(-) hides factors polynomial in log
3

---

Published as a conference paper at ICLR 2026
3 IMPROVED UPPER BOUND FOR TESTING FOURIER SPARSITY
3.1 PROOF OUTLINE OF THEOREM
The approach of employing learning algorithms for property testing, introduced by Goldreich al. (1998). is founded on the principle that any proper learning algorithm for a function class C' can be converted into a property tester for C. Nevertheless, while proper learning for most Boolean function classes requires at least 22(log n.) queries, property testing typically targets sublogarithmic or even constant query complexity. independent of the ambient dimension n. A significant advancement in this context was made by DDiakonikolas et al. (2007), who introduced the paradigm of testing via implicit learning. The key insight underlying this framework is that many natural classes of Boolean functions, such as monotone DNFs, decision lists, decision trees, branching programs, Boolean formulas, sparse polynomials over I 2. and Boolean circuits admit succinet representations and are well -el--apprxiimtee by junta functions. For instance, every s-term DNF is e-close to another s-term DNF depending on only Olog & + log(1/c)) variables. The saatin-via-imlliit---ee framework (Diakonikolas et al., 2007) exploits structural approximation along with the invariance of junta functions under permutations of input variables. Building on this principle, [Cakraborty et al. sample extractor that, given query access a function promised to be close to a junta, simulates access to the underlying junta up to a permutation of variables. This approach yields improved and in some cases optimal query bounds for testing various subclasses of juntas.
(201T) proposed
Returning to the problem of testing Fourier sparsity, we recall that Gopalan et al. (011T) designed their tester by exploiting certain locally testable structural properties of Fourier-sparse functions. In particular, they leveraged the granularity of nonzero Fourier coefficients, namely, that each nonzero coefficient must have sufficiently large magnitude and used a bashing-based technique to efficiently identify these large coefficients. In contrast, our approach based on the paradigm of testing via implicit learning. However, a central challenge in our setting is that existing techniques for testing membership in subclasses of junta functions are insufficient for handling Fourier-sparse functions. The reason is that the class of Fourier-sparse functions is strictly more general than the class of juntas. For example, a linear function depending on (nn) variables is 1-Fourier sparse, since it has exactly one nonzero Fourier coefficient. Yet such funetion is not junta, as its output depends on linear number of input variables. Thus, Fourier sparsity does not imply low variable depen- dence. Another fundamental distinction is structural: Fourier sparsity is invariant under invertible linear transformations of the domain, whereas the junta property is not preserved under such trans- formations. Consequently, testing Fourier sparsity via the -aatinggb--mmliit---lle necessitates new techniques that go beyond the existing junta-testing framework. More specifically, given query access to an unknown Fourier-sparse function, we develop a procedure that extracts uniformly distributed samples from certain low-dimensional Fourier-sparse function. The latter can be viewed as a low-dimensional sketch of the original function, capturing its essential spectral structure in reduced space.
paradigm
At the core of our approach is an exact learning procedure for s-Fourier sparse Boolean functions (see Algorithm 2p. It combines l 1-minimizatiinn techniques from compressed sensing (see Chap- ter 4 Moitri (0188) with the RIP result of Haviv & Regev (2017). The key implication is that any s-Fourier sparse function f F2 + (-1,+1} can be recovered exactly from O(s log² s n) uni- formly random samples by solving an appropriate fy-minimization program. However, this sample complexity scales linearly with the ambient dimension n, which is prohibitively large for our testing framework. To remove this dependence, which shows that the linear span of the nonzero Fourier coefficients of an s-Fourier sparse function has dimension at most O (v)). Consequently, every s-Fourier sparse function f FF2 + +1} admits oin-dimesiional representation
invoke structural theorem of Sanyal [Sanyal (2019),
f=f" T.,
where L : F2 + 1% is linear transformation and O(Vs). Combining this reduction with the RIP guarantee of Haviv & Regev (011)) we obtain that the reduced function f F7 + (-1,+11 can be reconstructed exactly using 3 log" s) random samples, now independent of n. Mo- tivated by this observation, our tester reduces Fourier sparsity testing to reconstructing priately compressed version of the target function. Concretely, we reconstruct a composition of the form foU R, where U : FF > FY is unknown invertible linear transformation and R: F3 - F7
appro-
4

---

Published as a conference paper at ICLR 2026
a known linear map. The main technical ingredient enabling this reduction is Algorithm sam- pler in the spirit of the extractor of Chakraborty et al. (2011) from the junta-testing framework. Our sampler substantially generalizes that approach and generates uniform random samples from the composed function f o U o R using only a small number of queries to f. At its core lies a local list-correction procedure for the Hadamard code, inspired by DDttaa al. (026), who studied the problem of testing linear isomorphism.
3.2 PROOF OF THEOREM 1.1
We begin by introducing the notion of coset sampling, which plays a key role in generating samples for the exact learning machinery, albeit in a low-dimensional space. Let O denote the sampling procedure with respect subspace H, given query access the function f. as described in Algo- rithm [] Throughout this work, we refer to the samples produced by this procedure coset samples of f with respect the subspace H.
Algorithm 1: SubsppceespplccccssseSaaaa
Input: Subspace H with basis B : ( f2.......... 3, and query access to ʃ Output: An uniform random sample of the function / restricted to random coset of H
1. Sample b uniformly random from Fž and define the coset C(b)
C(b) {a E F (a, B.) b:}.
2. Select uniformly random element p from C(b).
3. Return the pair (b, (p)).
Let Sy denote the subspace spanned by the vectors corresponding to the nonzero Fourier coefficients
of f. Observe that the coset samples generated by O'S, can be interpreted as uniform samples drawn from the set of leaves of the non-adaptive parity decision tree representation of f. For a parameter
0 > 0, the f-restricted Fourier span (O) is defined as the subspace spanned by those vectors
F2 for which [[(a) 2 8. In this work, build query-efficient implementation of O (,) given query access to and the threshold 0 > 0, where g f for some unknown invertible linear transformation A F2 + F3z
(Algorithm 3) that given query access to a Boolean function f F + {-1,+1}, threshold 0 O. and a parameter X E N, generates a set of X-many uniform coset samples &, with respect to the subspace S for a function f c where is some non-singule singulaa (and possibly unknown) linear transformation of Fy. The query complexity of the algorithm is O ( + .max { (z,,1) A} tz2) and the failure probability of the algorithm is at most IO
Lemma 3.1. There exists an algorithu SubspuceempiccicCosSSSaaaa
While the proof of Lemma 3.1 is deferred the later part of this section, we assume its validity for now and proceed to demonstrate how it can be used to establish Theorem 1.I
Proof of Theorem 1.1 In Algorithm 2 the subroutine SubspaceImpliciCCostSSaag
(Algo-
rithm B is invoked with parameters and X. By Lemma 3.1 this procedure produces À uniformly random coset samples (as described in Algorithm [ with respect to the subspace (f). Using these coset samples, we define a low-dimensional Boolean function f 135 - {-1,1}. where f = fo To A, and T F3 F is linear transformation mapping the standard basis vectors ep of 172 to the corresponding standard basis vectors ef of F7, for i E 21, The transforma- tion T also maps each of the 2" cosets of Syoa(0) (0) (the orthogonal subspace of (f)) to unique elements of F-z-
The next step is to determine whether the function f" is s-Fourier sparse. It is kind of folklore (see Chapter of Moitra (2018) that for any Boolean function h F5 {11,+1] with at most
5

---

Published as a conference paper at ICLR 2026
nonzero Fourier coefficients, if there exists x 2" subsampled Walsh- Walsh-Hadamard Hadamard matrix M satisfying the Restricted Isometry Property (RIP) of order with constant 6ạ < (and 62x + d3k- < 1), then the Fourier spectrum of h can be recovered exactly with high probability. This recovery achieved by solving the following & miminimmiaaiion problem using m uniformly random labeled examples (2r, y h())):
ì = arg min |Aلl subject to Mî = y.
A bound on m determines the number of required random examples and, consequently, the number of coset samples needed from f o A. To establish this bound, we recall the result of |Sanyal (2019) which states that for any Fourier sparse function fA, the dimension of the subspace spanned by its nonzero Fourier coefficients at most O(vR). Following result Haviv & Regev (2017), says that
m O (sa/2 / poly (log s)) random samples suffice for exact recovery of f"
Lemma 3.2 (Haviv & Regev 2017)). Let M E CN*N be a unitary matrix satisfying || S O(1/VN), and let 0 sufficiently small. Construct a measurement matrix B E CYxN by selecting rows uniformly and independently from M, each scaled by vN/g. !f
q O (log" (1/8) 8-2 2. k logo (k/0) log N)
then, with probability at least 1 2 Ailog N (log(k/6)), the matrix B satisfies the Restricted Isometry Property of order with isometry constant 5.
Algorithm 2: EnfecientFourierSSparttttytee Testrr
Input:
Fourier sparsity and query access to f. Output: Whether f has fourier sparsity or e far from every such function
Cs² Initialization: 0 = i > max Cs² poly(log 8)} where C is some large constant
1. (S.r) + SubbpacclmppicccCCreeaaaappe
2. Initialize & such that for each (I, v) Ç and for each E F2z set
2
[-||=>]
F (-1)a²2.
3. Solve the following optimization problem:
min
|b]l subject
($/>||*] h) y, for all (z. v) E Ç.
4. If h corresponds to the Fourier spectrum of some s- s-Fourier sparse Boolean function, accept; otherwise, reject.
We now show that if the input function f is s-Fourier sparse, then the algorithm always accepts. Lemma 3.3 (Completeness). If the function f is s-Fourier sparse, then Algorithm accepts.
Proof. We begin by recalling a result from Gopalan et al. (201T), which states that if function is 3-Fourier sparse, then all of its nonzero Fourier coefficients integer multiples of π- More- over, Fourier sparsity invariant under nonsingular linear transformations. When the subroutine SubsppaelmpliciCCoeSSSaapa
(Algorithm 3) is invoked with the threshold parameter 0 Lemma 3.1 guarantees that it indeed discovers the Fourier span of f o A, for some unknown in- vertible linear transformation A. Additionally, the algorithm produces À uniform coset samples, where
{
= max
O poly(log s))
By the guarantees of the sparse recovery algorithm discussed previously, these samples suffice to exactly reconstruct the Fourier spectrum of the projected function f" = f o T A. Hence, the algorithm accepts.
n

---

Published as a conference paper at ICLR 2026
Lemma 3.4 (Soundness). the function f is from every s-Fourier sparse Boolean function, then Algorithm Sennihmm@ejeeee rejects.
Proof. We argue by contraposition. Suppose Algorithm 2 accepts. Then there exists function f. obtained via composition with appropriate linear transformations, such that agrees with f on all uniform samples collected during Step Algorithm 3 and moreover f is s- s-Fourier sparse. Let us define the set GOOD as the set of inputs where f and f agree, and BAD as the complement. The [BAD] If this probability is
probability that all X samples fall within the GOOD set is (1- (1-)) least a constant, say (2(1), then by standard union bound and Markov's inequality, must have which implies that f is o(x) -close to some s-Fourier sparse function f.
2
BADI 2
O(Aj
We now analyze the query complexity of Algorithm 2 The algorithm initializes with parameters 0 O(1/s) and x max { (({)) The only queries made are via calls to Algorithm According to Lemma 3.1 the total number of queries made within that algorithm is bounded
by Ô (#tt + max { 03 } कz) Substituting 0 = O(1ss). obtain the final query complexity:
Ô (s+ + max {s², ! s²).
One may verify that Algorithm 2 fails with probability at most To + o(1) < 1
3.3 PROOF OF LEMMA
We prove this lemma by showing that Algorithm Aggorithmsssttsffee satisfies the theoretical guarantees of Lemma
Algorithm 3: Subspace cubspacclmppicciCootttaaaa
Input:
Threshold 6, Number of samples X, Distance
Output:
Coset samples of f o A with respect to subspace (o)
Parameters: + maxx20002, A), + log(100x)
Step 1: Run SCEE with parameters 0, À and oracle access F.
Step 2: Relabel the columns of Q as
B2} such that
B eT. B, =,
and for all E (r 1,...,,,, k}. B, is a linear combination of [B,.... Br}.
Step 3: foreach x E (01,222,
Fx do
Compute b FF'S where
by - Q/
2
Update < (((,)(())))
end
Step 4: Construct matrix H E R whose rows are Bi...., Br.
Step 5: return (H,
We use the following local list correction framework from Datta et al. (026). which plays crucial role in our Algorithm.
Lemma 3.5 (Datta al. (0266). There exists an algorithm, Economical Sieve, that takes param- eters and as input, makes Ô (max f 2)) queries the truth table of a Boolean function f: F2g + (-1,1} 1}, and, with probability at least Io. outputs:
A matrix Q +11 where the (i.j)-th entry is Xay (rs):
A column vector F Fe (-1,11 13A, where F(i) (x::) for each i [A],

---

Published as a conference paper at ICLR 2026
where each E F2 is drawn independently and uniformly random, and each oj E2 belongs to a set = {a1...., oue satisfying:
* For every a E F2 such that [f(a)) 2 6. we have a E S;
. For all E S, it holds that [(a)] 2 0/2.
In this work, we assume Lemma 3.5 and proceed with the proof of Lemma 3.1 The proof of Lemma can be found in Datta al. (2026).
Proof. Observe that the matrix Q yields the heavy Fourier coefficients of f evaluated uniformly random points These coefficients, however, are not available in explicit form; rather, they are represented implicitly as dominant elements within their respective cosets. Nevertheless, evalua- tions of the corresponding characters at uniformly random points enable to uncover the linear relationships among them.
To why, let T be subset of S. the set of Fourier Coefficients corresponding columns of Q such that Ea,eT a₁ = 0", Then for all x E F2.
II (x) = II ((-) a1.)) =1 0TET
0,ET
Thus, the product of the corresponding columns of Q, denoted II,, always equals 1 On the other hand, if B C S consists of linearly independent vectors, then the probability that II, (x) 1 for all x is small.
Claim 3.6. The probability that all entries of II, Xa, (2ş) are equal to is at most 2 A More- over, for any fixed B, the probability that this product equals for any subset of B is at most 1/100.
Proof. Since the vectors a are linearly independent and the points 21...., Iy are sampled uni- formly at random from F2 we have PrlIIo.es Xa,, (z,) = 1] = 1/2 for each independent sample Tz. Hence, the probability that this holds across all independent trials is at most 2 2- Furthermore, the number possible subsets of B is at most 2/ = 2011/0"), By applying the union bound, the probability that II,,ED Xax (z²)) = 1 occurs for any subset D C B is at most 2011/00 < o(1), provided that À = (0((10)) log(1/0)).
Using this insight, in Step of the algorithm we extract a basis size r for the span of the heavy Fourier coefficients. Without loss of generality, after appropriate change of coordinates, we relabel these basis vectors as the first standard basis vectors .i....,,,, in 17z. Let H denote the subspace spanned by these vectors. We define a matrix M E F whose rows are precisely ef. .......cc e. For each {zi,.....a xx the coset of H containing x uniquely determined by the linear constraint Mæ = b, where b E P7 is computed in Step 3 of the algorithm. Finally, observe that if is chosen uniformly at random from Fž, then the induced distribution over the cosets of H given by the mapping + Ma, is uniform over F Consequently, each coset of H is sampled with equal probability.
Lemma 3.7. Given any C F2, the distribution of cosets induced by uniform random selection of F2 is uniform over the cosets of the subspace G.
Proof. Let C Fy be a subspace of dimension k. The cosets of G in F? are of the form C2 = z G+G for E F7, and there are exactly 2 distinct cosets. Each coset has size |C2| = 2* while FF = 2". Now choose x E F3 uniformly at random and consider the coset containing r. For any fixed coset C., the probability that x C2 equals |/ 24 /2" independent of 2. Hence, every coset is selected with the same probability, and therefore the induced distribution over the cosets of G is uniform.
n-2 This value is
8

---

Published as a conference paper at ICLR 2026
By the theoretical guarantees of the Economical Sieve, the query complexity of the algorithm is O gr max {2 2z). Consequently, the overall failure probability is bounded by o( 10'
IMPROVED LOWER BOUND FOR TESTING FOURIER SPARSITY
We begin by defining class of Boolean functions known as the Maiorana McFalland functions. These functions have a long history in theoretical computer science, including applications in circuit
lower bounds and studies of Boolean function structure (Paul 1977, Blum 1984] Nisan Szegedy
1992 Sanyal 2019). They are also widely used in symmetric-ker cryptography, particularly in stream cipher design, where they provide desirable Fourier and autocorrelation properties (Sarkar & Maitra 2000).
Definition 4.1. Given positive integers and with S n, the family of Maiorana Maranaand
functions, denoted MM (McFarland 1973). consists of functions j F2 + {-1,+1} of the form
g(x, y) = (-1) (-1)(xxp(0) (I, E F RP-T
where xp :FF F2-" - 1222 is an arbitrary mapping.
key property of these functions that, when composed with linear transformations, their Fourier sparsity is governed by the rank of the transformation. It was proved in Datta et al. (2026). We refer the reader to Datta et al. (2026) for the full argument: in this work, we assume this result starting point for our proof.
Lemma 4.2. Let r logr, let v F
F2 have linearly independent outputs, and let
L 12X be linear. Define
gL y) = (-1)(ta.((v)))
Then the Fourier sparsity of 9L satisfies (supp(gZ)) |= S rank(L) rr
Our proof proceeds via a reduction from randomized communication complexity. We briefly recall the relevant notions. Randomized communication complexity studies the minimum number of bits that two parties must exchange in order to compute function, using either shared randomness, while producing the correct output with high probability. In this work, we focus on the following problem. Alice and Bob are given matrices A, B E FXxr respectively, and are promised that rank(A+ B) E (r, r/4]. Their goal to determine which of the two cases holds while minimizing the amount of communication, using public randomness. We denote by Ri r../) the public-coin randomized communication complexity of this problem with error probability at most 1/3.
Theorem 4.3 (Sherstov & Storozhenko 2024
RG /3 (RANK, (((3))
Equipped with these definitions, now establish Fourier sparsity testing lower bound that is quadratically stronger than the previously known result (Gopalan et al. 2011I)
4.1 PROOF OF THEOREM
We prove the theorem via a reduction from the Approximate Matrix Rank problem. Alice has A,
Bob has B, and = + B satisfies rank(C)) E (r,r/4). Alice constructs fA, Bob constructs fB.
and together they define f = fc = fA+B. B. By Lemma 4.2 if rank(C') = then (supp(f) = 2 and if rank(C) r/4, then |supp(f)] < r² 2// The following lemma from Datta et al. (0026) quantifies the distance between the two cases; we refer to that work for the full proof.
Lemma 4.4 Datta et al. (2026)). If rank(C)) = r, then f is at least (1/4)-far from any function with Fourier sparsity most /²/4.

---

Published as a conference paper at ICLR 2026
Using this result, we complete the reduction. Suppose there exists tester T for Fourier sparsity with parameter 8 and query complexity q(s, 1/4), where s = r /4. We show how such a tester yields a communication protocol for the approximate rank problem.
To simulate a query at a point x, Alice evaluates fa(z) using her input matrix A, and Bob evaluates fa()) using his input matrix B. They then exchange their one-bit outputs. Since the target function satisfies fa( = (x()) both parties can compute fc(Ø) after exchanging these two bits. Thus, each simulated query requires exactly two bits of communication. Consequently, the total communication cost of the induced protocol is 2 (s,, 1/4) bits. However, by Theorem 4.3 any public-coin protocol that solves the approximate rank problem with constant error requires (2(r") bits of communication. Therefore, 2 2g(s, 1/4) = 2,r"). which implies q 1/4) = (2())). Since 8 / /4, we obtain q(8, 1/4) (s)), establishing the claimed lower bound.
5 CONCLUSION
Our algorithm can be adapted to obtain tolerant tester as well. The key observation is that the subroutine SUnSETTMPLCCTCCOOSSSAW
draws Oss²) uniform random examples and checks whether there exists an s-Fourier-sparse Boolean function supported on subspace of dimension about (vs)) that agrees with all sampled points. This step can be made robust to achieve tolerance. Specifically, in distinguishing whether a function is s-close to some s-sparse function 2s-far from every such function, we may allow up to an e-fraction of the sampled labels to be flipped, and run the reconstruction procedure repeatedly on these perturbed batches of samples. With mild degradation in complexity parameters, this yields an E-versus-2e tolerant tester.
However, in this work, we focus on the exact (non-tolerant) setting. More broadly, when a tester is used as a preprocessing step for exact learning of Fourier-sparse Boolean functions, it naturally cor- responds to a non-tolerant formulation; exact recovery is meaningful only when the target function itself (or is extremely close to) an s-sparse Boolean function. If the function is far from this class in Hamming distance, an exactly sparse representation cannot reliably recovered.
contrast, PAC learning of Fourier-sparse Boolean functions operates under Euclidean (f2) notion of distance and in a tolerant regime. It suffices that most of the & Fourier weight is concentrated on a few coefficients, and the objective is merely to output hypothesis with small additive & error (and hence small prediction error), rather than to recover an exactly sparse representation.
ACKNOWLEDDGENT
Arijit Ghosh acknowledges partial support from the Science and Engineering Research Board (SERB), Government of India, through the MATRICS grant MTR/2023/001527 and from the De- partment of Science and Technology (DST), Govermment of India, through grant hamoy Maitra and Manmatha Roy acknowledges support from the ISEA Phase-III initiative of the Ministry of Electronics and Information Technology (MeitY), Govt of India, through Grant No L- 14017/1/2022-HRDD
Sub-
REFERENCES
Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett. Every locally characterized affine-invariant property is testable. In Proceedings of the 45th ACM Sym- posium Theory of Computing (STOC), pp. 429-436, 2013.
Norbert Blum. A Boolean function requiring 3n network size. Theoretical Computer Science, 28:
337-345, 1984.
Claude Carlet. Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, 2020.
Sourav Chakraborty, David Gareía-Soriano, and Arie Matsliah. Efficient sample extractors for juntas with applications. In Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), pp. 545-556, 2011.
10

---

Published as a conference paper at ICLR 2026
Swamnalia Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy. Spec- tral norm, economical sieve, and linear invariance testing of Boolean functions. In Proceedings of the 43rd International Symposium on Theoretical Aspects of Computer Science (STACS), 2026.
Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Serve- dio, and Andrew Wan. Testing for concise representations. In Proceedings of the 48th Anmual IEEE Symposium on Foundations of Computer Science (FOCS). pp. 549-558, 2007.
Arijit Ghosh and Manmatha Roy. Price of Parsimony: Complexity of Fourier Sparsity Testing. In Advances in Neural Information Processing Systems (NeurIPS), 2025.
Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In Proceed- ings of the st ACM Symposium on Theory of Computing (STOC), pp. 25-32, 1989.
Oded Goldreich, Shaf Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM, 45(4):653 750, 1998.
Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, and Karl Wimmer. Testing Fourier dimensionality and sparsity. SIAM Journal Computing, 10(4):1075-1100, 2011.
Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price. Nearly optimal sparse Fourier trans- form. In Proceedings of the 44th ACM Symposium on Theory Computing (STOC), pp. 563-578, 2012.
Hamed Hatami and Shachar Lovett. Estimating the distance from testable affine-invariant proper- ties. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 237-242, 2013.
Ishay Haviv and Oded Regev. The restricted isometry property of subsampled Fourier matrices. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pp. (69,179.0 2017.
Piotr Indyk, Michael Kapralov, and Eric Price. (nearly) sample-optimal sparse Fourier transform. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithmss (SODA), pp- 480-499. 2014.
Tali Kaufman and Madhu Sudan. Algebraic property testing: the role of invariance. Proceedings of the 40th ACM Symposium on Theory of Computing (STOC), 2008
Michael Kearns and Umesh Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994.
Eyal Kushilevitz and Yishay Mansour. Learning decision using the Fourier spectrum. SIAM Journal on Computing, 22(6):1331-1348 1993.
R. L. McFarland. A family of noneyelic difference sets. Journal of Combinatorial Theory, Series A, 15:1-10, 1973.
Ankur Moitra. Algorithmic Aspects of Machine Learning. Cambridge University Press, 2018.
Noam Nisan and Mario Szegedy. On the degree of Boolean functions as real polynomials. In Proceedings of the 24th ACM Symposiun Theory of Computing (STOC), pp. 462-467, 1992.
Ryan O'Donnell Analysis of Boolean Functions. Cambridge University Press, 2014.
Wolfgang J. Paul. A lowe-lower bound on the combinational complexity of Boolean functions. SIAM
Journal on Computing, 6(3):427-443, 1977.
Swagato Sanyal. Fourier sparsity and dimension. Theory of Computing, 15(11):1-133 2019.
Palash Sarkar and Subhamoy Maitra. Construction of nonlinear Boolean functions with impor- tant cryptographic properties. In Advances in Cryptology EUROCRYPT 2000, pp. 485-506. Springer, 2000.
11

---

Published as a conference paper at ICLR 2026
Alexander A. Sherstov and Andrey A. Storozhenko. The communication complexity of approximat- ing matrix rank. In Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 433-462, 2024.
Peter Stobbe and Andreas Krause. Learning Fourier sparse set functions. In Proceedings of the 15th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1125-1133, 2012.
Grigory Yaroslavtsev and Samson Zhou. Fast Fourier Sparsity Testing. In Proceedings of the Sym- posium Simplicity in Algorithms (SOSA), pp. 57-68, 2020.
12


Reviews:
[{"review_id": "EtRdk3atqn", "reviewer": "Reviewer_Dn21", "summary": "The paper presents new algorithms for testing Fourier sparsity of a boolean function given query access to that function. A boolean function is $s$-Fourier sparse if it's Fourier representation has at most $s$ nonzero components. This assumption is satisfied by classes of simple functions such as low-depth decision trees. Fourier-sparse family of functions that has received extensive theoretical investigation because of connections to a wide range of combinatorial and algorithmic questions. \n\nThe main results improve the known upper and lower bounds for the query complexity of testing Fourier-sparseness: the upper bound drops from about $s^{10}$ to about $s^4$. The lower bound jumps from about $\\sqrt{s}$ to about $s$.\n\nThe paper achieves these results by refining existing approaches and developing new ones based on the structure of Fourier-sparse functions.", "questions": "I would like to see the authors make a clear and hones) case for the significance of their work to the ICLR community. Why is this the right paper for the venue and the right venue for the paper? Of the many possible lines of basic theory work that are adjacent to ML, which ones fit ICLR? (I guess \"all of them\" is a fine answer, but maybe not one that would see wide support.)\n\nOn a more technical level: what are the implications of this work for tolerant testing, if any? For what settings of parameters do these algorithms improve on those that actually learn a nearby s-Fourier sparse function? (What are specific settings where these algorithms would be useful for parameter selection?) Note that even query-based learning of s-Fourier sparse functions is already a fairly stylized theory question, albeit a fundamental and beautiful one.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* This paper provides significant improvements on a clean algorithmic problem. \n\n* The techniques seem like a nice contribution to the literature. I did not check the proofs, but the overall writing and presentation seem like a good fit for a specialist audience. It was nice to see many recent insights from the complexity/learning literature applied to this problem (which hadn't been directly attacked since 2011 or so).\n\n* Applications of this result are not discussed in detail, but the authors point out that testers for Fourier-sparseness could, in principle, be used to help select the parameters of a learning algorithm that is to be run on a dataset. \n\n* Section 3.1 does a nice issue of explaining the basic outline of the algorithm.", "weaknesses": "* My main hesitations about the paper have to do with significance and fit for ICLR. Specifically: \n\n   * Exact vs tolerant testing: the authors suggest in the abstract that their algorithm could be used to select the parameter $s$ for a downstream learning algorithm that learns s-Fourier sparse functions. However, such an application would presumably require a tolerant tester, and would only be useful when the additional powers of $s$ in the testing results are dominated by the dimension-dependent factors required for learning. It would be good, for an ICLR audience, see this path spelled out—or at least a clear-eyed case be made for why this line of theoretical work should interest the ICLR audience. \n\n   * Hamming versus Euclidean distance (similar to the tolerant testing issue above): The paper explains why testing for Hamming distance may be harder than testing for Euclidean distance, but not why that difference really matters for downstream use. \n\n* The presentation is really tailored towards experts. Section 3.1 was pretty readable (modulo some notational issues), but Section 3.2 delved into specific jargon (e.g. \"nonadaptive parity decision trees\") pretty quickly. \n\n* Minor issue: the dimensions and notation for the discussion of $f$, $f^*$, $L$, $U$, and $R$ (lines 200–206) was confusing. I guess you meant that $f = f^* \\circ L$? and $R$ goes from $r$ to $n$ dimensions, not the other way around? In any case, a bit more explanation ehre would help, as would explicitly matching the notation with that of Section 3.2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AM1adRqrZC", "reviewer": "Reviewer_YARm", "summary": "This paper studies testing the sparsity of Fourier coefficients of boolean functions under Hamming distance. The authors proves an upper bound of $\\tilde{O}(s^{4})$ and a lower bound of $\\Omega{s}$, significantly improving previous bounds.", "questions": "My main questions are related to the recent work [1]\n1. What are the key distinctions with the algorithm used in [1]? \n2. Does the lower bound in [1] imply a meaningfule lower bound for the Hamming distance?\n\n[1] Arijit Ghosh, Manmatha Roy, Price of Parsimony: Complexity of Fourier Sparsity Testing, to appear in NeurIPS 2025, https://openreview.net/forum?id=7bCPXHq8xV", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Testing Fourier coefficients of boolean functions is a fundamental problem in theretical compter science. The authors significantly improve existing upper and lower bounds on testing sparsity under Hamming distance.\n2. The techniques are interesting. It is inspired by prior works on testing junta functions, but requires non-trivial and novel design in the algorithms to work for testing sparsity in Fourier coefficients.", "weaknesses": "1. A recent work [1] obtain nearly tight bound for testing sparsity of Fourier coeficients under L2/Euclidean distance. While the distance metric is different, it is necessary to discuss differences in the technical ideas. The authors mention that closesness in Hamming distance implies closeness in Euclidean distance, and therefore it is more difficult to design algorithm for the former case, but this also means that lower bound for Euclidean distance could imply a lower bound for Hamming distance.\n\n[1] Arijit Ghosh, Manmatha Roy, Price of Parsimony: Complexity of Fourier Sparsity Testing, to appear in NeurIPS 2025, https://openreview.net/forum?id=7bCPXHq8xV", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Go9tml6zO9", "reviewer": "Reviewer_x8Ha", "summary": "The paper proposes a tester for determining whether a given Boolean function is $s$-Fourier sparse or $\\epsilon$-far from every $s$-Fourier sparse function, using only $O(s^4)$ queries (ignoring polylogarithmic factors) under the Hamming distance. A Boolean function is $s$-Fourier sparse if it has at most $s$ nonzero Fourier coefficients. Furthermore, the paper complements this result by providing an $\\Omega(s)$ lower bound on the query complexity of the problem. The authors claim that both these results improve upon the previously best-known bounds of $O(s^{14})$ and $\\Omega(\\sqrt{s})$, respectively.\n\nUnfortunately, due to time constraints and limited expertise in this specific subarea, I am unable to verify the technical details.", "questions": "see above (weakness).", "limitations": "", "rating": 2, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "The results appear to significantly advance the state-of-the-art bounds for the problem (although I have some strong reservations about this claim; see Weakness). The techniques also seem novel and potentially interesting.", "weaknesses": "Theoretically, the upper bound result is very interesting given the claimed improvement over existing bounds. However, I am not convinced that the improvement is correctly compared to the existing results. This is partly because the paper does a poor job at comparing their work with prior works.\nFor instance, the paper refers to the work of Yaroslavtsev–Zhou (SOSA’20), who study the same problem under the $\\ell_2^2$ distance instead of the Hamming ($\\ell_1$) distance considered here, and propose a tester using only $O(s)$ queries. However, it seems to me that their result can be extended to the $\\ell_1$ setting with only constant-factor loss in accuracy. Indeed, for any two Boolean functions $f, g$, we have\n$||f-g||_2^2 = E_x[(f(x)-g(x))^2] = 4 \\cdot Pr_x[f(x)\\neq g(x)] = 4 \\cdot ||f-g||_1$\n\nwhere $||f - g||_1$ denotes the Hamming distance between $f$ and $g$. Let $F_s$ be the set of s-Fourier sparse functions.\n\nTherefore, the learner of Yaroslavtsev–Zhou, which estimates $||f - F_s||_2^2$ with additive error $\\delta$ using $O(s)$ queries, can be used to distinguish whether the Hamming distance of $f$ to the set $F_s$, of $s$-Fourier sparse functions is at most $\\delta$ or at least $4\\epsilon - \\delta$,  ($\\delta$ set to $\\epsilon / 1000$ to create a suitable gap). This formulation exactly matches the testing problem studied in the present paper. Moreover, the prior tester achieves this with only $O(s)$ queries, whereas the current paper’s tester requires $O(s^4)$ queries (ignoring polylogarithmic factors). Thus, unless I am missing a critical technical distinction, I do not see how the upper bound in this paper improves upon existing results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6hj2ErH6WX", "reviewer": "Reviewer_xU3b", "summary": "This paper studies property testing of the Fourier sparsity of a Boolean function. Specifically, for a parameter s, we want to perform few queries and distinguish between the cases where the Fourier sparsity is at most s, or the function is eps-far in Hamming distance fomr any function of Fourier sparsity at most s. This is a standard setup in property testing, and the problem here is particularly important: many learning/testing/etc algorithms in the literature assume one knows the Fourier sparsity of the function, so to apply these to functions where the Fourier sparsity is unknown and only query access is available, this type of algorithm is needed.", "questions": "- It seems misleading to say there's a \"gap in the literature\" (in the abstract) or a \"critical gap\" (page 2) about assuming you know the Fourier sparsity when Gopalan et al. already studied this question, and here the bounds are being improved but not completely new. Could you comment on this; is there some aspect that you address that was missing in the prior work? \n- I was expecting the problem to test whether the Fourier sparsity is at most s or at least s + g for some parameter g, rather than using Hamming distance of f to an s-Fourier-sparse function. Wouldn't this more accurately test for whether the function can be used in learning algorithms that need small Fourier sparsity?\n- Could you highlight which of the algorithmic techniques are most novel/intereting in this context?\n- In applications to learning (i.e., other learning algorithms where it is assumed you know the Fourier sparsity), I would imagine that a powering approach might work where you guess the Fourier sparsity is 1, then 2, then 4, then 8, and so on, until the algorithm succeeds, and only lose a poly factor. Are there any important applications where this type of approach doesn't work, and testing the Fourier sparsity like this is important?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- This is a very natural problem in computational learning theory. The setup and sdetting are very clean and general.\n- The paper improves the state-of-the-art for both upper and lower bounds. It's nice that the new insights here are able to make progress in both directions.\n- The paper is written well and easy to follow for the most part.", "weaknesses": "The main weakness is just that the results seem somewhat incremental. I also think the intro/abstract overstate how important the results are; see questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "paVnduh75Z", "reviewer": "Reviewer_jtCc", "summary": "This paper studies the property testing problem of Fourier sparsity under Hamming distance. The goal is to decide, given query access to $f :\\mathbb{F}^n_2 \\rightarrow \\{ \\pm1 \\}$, whether $f$ is $s$-Fourier-sparse or $\\epsilon$-far from every such function, with query complexity independent of $n$. The authors give a non-adaptive tester with complexity $\\tilde{O}(s^2 \\cdot \\max(s^2, 1/\\epsilon))$, improving the prior bound of $\\tilde{O}(s^{14})$. In addition, this paper shows an $\\Omega(s)$ lower bound , improving the prior $\\Omega(\\sqrt{s})$. \n\nFor the upper bound, the tester combines a \"implicit sensing\" sampler (built in the spirit of junta testing) with an $\\ell_1$-minimization step over a low-dimensional projection of $f$. The sampler produces uniform coset samples corresponding to leaves of an appropriate parity decision tree; from these, the analysis identifies the span of heavy Fourier characters (up to a linear change of variables), and reduces the task to recovering a sparse spectrum in dimension $O(\\sqrt{s})$. This is done via compressed sensing on random Walsh–Hadamard rows. For the lower bound, the authors reduce testing to a linear-algebraic communication problem instantiated with Maiorana–McFarland functions.", "questions": "See the above section.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The quantitative improvement is significant: although the new upper bound $\\tilde{O}(s^4)$ is still a large polynomial, comparing with the previous bound of $O(s^{14})$, cutting the exponent from 14 to 4 indeed materially advances the state of the art.\n\n- The recovery step leverages robust, well-understood RIP machinery for subsampled Hadamard matrices. I appreciate that the paper plugs into a mature toolbox, which increases credibility and portability. The pipeline of (1) isolating a low-dimensional structure via coset sampling, then (2) running a standard compressed-sensing recovery in that reduced space feels neat and intuitive. Conceptually, the RIP lens clarifies why the query complexity loses all dependence on $n$: after the dimension to $O(\\sqrt{n})$, the complexity of compressed sensing scales with the sparsity and the log of the reduced dimension, hence becomes independent of the ambient $n$. This aligns with the property-testing goal and makes the result feel principled rather than ad hoc.", "weaknesses": "I think the presentation of the paper could be significantly improved. The paper is understandably notation heavy, but this is exacerbated by the fact that a major part of both the algorithm and the upper-bound proof is deferred to the appendix, which makes cross-referencing difficult. It seems the authors intend to use Algorithm 1 as an \"oracle\" interface for Algorithm 3 to aid exposition; however, Algorithms 1 and 3 have quite different specifications (inputs/outputs, etc.), which limits the usefulness of this design. I suspect this formatting is driven by ICLR’s tight page limits. Rather than splitting essential descriptions and proofs between the main body and the appendix, it might be better to submit to a TCS venue with a more permissive page limit so the proof can be presented in a self-contained manner. I have not checked all proofs in detail, but even at a semantic level there appear to be some inconsistencies:\n\n1. Lemma 4.2 gives only an upper bound on the support size, whereas the proof of Lemma 4.4 refers to it giving an exact equivalence (i.e., both upper and lower bounds).\n\n2. In Algorithm 3, Step 6 constructs b from the signs $Q[x][B_j]$, thus $b$ seems to correspond to $Ux$, where $U$’s rows are the (unknown) $\\alpha$'s. However, on Lines 918-933 it is asserted that $Mx = b$ with $M$’s rows being the standard unit vectors. I am not sure how these two statements are reconciled?\n\n3. In the proof of Lemma A.5, when bounding the expectation $E[|\\mathcal{P}_C(z)  - \\mathcal{P}_C^*(z) |]$, why is it legitimate to drop the absolute value inside the expectation?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)