Classes Testable with O(1/epsilon) Queries for epsilon Below an n-Independent Threshold
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Classes Testable with O(1/epsilon) Queries for epsilon Below an n-Independent Threshold".
Jane: Here's the gist of the paper. Classes of Boolean functions that are testable with O(ψ + 1/ϵ) queries, where ψ depends on the parameters of the class (e.g., the number of terms, the number of relevant variables, etc.) but not on the total number of variables n, is a significant result in property testing because it establishes a query complexity that is independent of the total number of variables n <ref:2604.05615#pg4>.
Tom: In particular, when ϵ ≤ 1/ψ, the query complexity reduces to O(1/ϵ), matching the known tight bound omega(1/ϵ) <ref:2604.05615#pg4>.
Jane: This paper extends this result to include classes such as k-junta, functions with Fourier degree at most d, s-sparse polynomials of degree at most d, and s-sparse polynomials <ref:2604.05615#pg2>.
Tom: Extension of Known Results The authors demonstrate that the property holds for several classes beyond those previously studied <ref:2604.05615#pg2>.
Title and authors: Tom: So, we're looking at this paper now. It’s called "Classes Testable with O(one/epsilon) Queries for epsilon Below an n-Independent Threshold <ref:2604.05615#pg1,Classes Testable with O(1>." And the authors are Nader H. Bshouty and George Haddad from Technion in Haifa. The title suggests something really interesting about how hard it is to test these functions, and specifically, that the required number of queries doesn't depend on the total number of variables, which we call n.
Jane: That’s a big deal because usually when you talk about testing something in computer science or statistics, you expect the complexity to scale with how much data or input you have. If it doesn't depend on n, that means we can test these classes efficiently even if they have a massive number of variables.
Lu: Exactly. The core idea is that the complexity depends only on the intrinsic properties of the function class, like how many terms it has or how many important variables are involved, and not on n itself. That shifts the entire focus from scaling with input size to scaling with problem structure.
Meng: From an engineering standpoint, that’s huge for us because we deal with models that can have millions of parameters. If the test complexity doesn't explode just because we add more features, it makes deployment way more predictable.
Lalam: I see this paper is extending what was already known about testing things like k-junta and s-sparse polynomials to even broader classes of functions, which is exactly what we need for real-world applications where the input size can be huge.
The paper's summary: Tom: So, what’s the main point here? The authors show that for several important function classes—like k-junta, functions with Fourier degree at most d, and s-sparse polynomials—we can test them with a query complexity that is O(psi plus one over epsilon), where psi is just some property of the class parameters <ref:2604.05615#pg1,k-junta, functions with Fourier degree at most d>.
Jane: So they are showing that we can get down to a complexity of O(one over epsilon) when epsilon is small enough, which matches the best possible bound we already knew for many of these specific classes <ref:2604.05615#pg1>. It’s like finding the tightest possible measure for how much information you need to get a reliable answer.
Lu: The paper points out that this result holds even in a more general sense, showing that if you have any class C of functions that only depend on at most k variables, and if it’s properly exactly learnable, then we can test it with O(one over epsilon) queries when epsilon is below some threshold psi that depends only on k <ref:2604.05615#pg1,depend on at most k variables>.
Meng: But they also introduce a clever way to do this. They reduce the problem of testing these functions over n variables down to testing them over a smaller set of variables, say m, where m only depends on the class parameters and not on n. That’s how they keep the complexity independent of n.
Lalam: And they use this reduction by substituting fully independent random assignments with pairwise independent ones when simulating tests over that reduced function; that's a key technical innovation for getting those query complexity improvements while keeping the test correct.
The paper's improvements: Tom: Let’s talk about the specific results they found. For k-Junta, they show a query complexity of O(k log k plus one over epsilon) when epsilon is less than or equal to one over k log k <ref:2604.05615#pg1>. That’s a concrete number we can use for setting our expectations on how many queries we need.
Jane: And for s-sparse polynomials, they find something pretty strong. When epsilon equals one over s beta, the complexity drops down to O(s squared) queries, which is better than some previous results that might have been worse than that. It shows a real improvement in the scaling here.
Lu: The paper also gives us bounds for Fourier degree d functions, showing a query complexity of O(22d plus one over epsilon) when epsilon is less than or equal to one over two to the d times two times d <ref:2604.05615#pg2>. That’s much better than exponential time methods that we were seeing before.
Meng: From a deployment perspective, if we're dealing with functions whose Fourier degree is bounded by d, knowing that the testing complexity scales linearly with 22d means we can actually handle moderately complex models without needing an exponential number of tests just to verify their properties <ref:2604.05615#pg2>.
Lalam: And they have these more general results too, like Theorem one and Theorem two which give us bounds involving Q of k, which is the query complexity for exact learning with n variables <ref:2604.05615#pg2>. It essentially shows that the testing algorithm can leverage what we already know about how hard it is to learn the class.
Conclusion: Tom: So, wrapping up this paper "Classes Testable with O(one/epsilon) Queries for epsilon Below an n-Independent Threshold," the main thing is that we have established query complexities that are independent of the total number of variables n for several important function classes <ref:2604.05615#pg1,independent of the total number of variables n>.
Jane: That means whether you have a function with a few hundred variables or a million, the fundamental test complexity based on its structure stays manageable, which is a significant finding for property testing in general.
Lu: The implication is that we can build more robust methods to verify the properties of complex systems without getting bogged down by how many inputs are involved. We’re moving towards algorithms where the cost is tied to the inherent complexity of the function itself, not just its size.
Meng: For production, this means testing models with a large number of parameters becomes much more feasible because we don't have to worry about a sudden jump in query requirements when we scale up our input size.
Lalam: This paper gives us concrete results for k-junta, s-sparse polynomials, and Fourier degree functions that show how to test them efficiently with query complexities like O(one/epsilon) under certain conditions <ref:2604.05615#pg1>. It’s a lot of practical stuff for applied machine learning research.
Technion, Haifa
cs.DS
Submitted: 2026-04-07
Updated: 2026-11-12
Comments: Appears in the Proceedings of the 52nd International Conference on Current Trends in Theory and Practice of Computer Science (Sofsem 2027)
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 89/100
The gist: Classes of Boolean functions that are testable with O(ψ + 1/ϵ) queries, where ψ depends on the parameters of the class (e.g., the number of terms, the number of relevant variables…
Key concepts
- Property Testing
- This is a method to determine if a large collection of functions possesses a certain property by querying the functions only a few times. The goal is to find an efficient way to check complex properties without examining every single function.
- k-Junta
- A k-junta is a Boolean function that depends on at most k specific input variables, regardless of how many total variables are in the system. Testing these functions efficiently is a key focus, as it allows for complexity independent of the total variable count n.
- Query Complexity Independent of n
- This means the number of queries needed to test a function class does not grow with the total number of input variables (n). Instead, the query count depends only on parameters like k or d, making testing scalable for very large problems.
Terminology
Summary
Classes of Boolean functions that are testable with O(ψ + 1/ϵ) queries, where ψ depends on the parameters of the class (e. p. 0 Bshouty George Haddad
Dept. of Computer Science
Technion, Haifa
April 8, 2026
Abstract
In this paper, we study classes of Boolean functions that are testable with O(ψ + 1/ϵ)
queries, where ψ depends on the parameters of the class (e. of Computer Science
Technion, Haifa
April 8, 2026
Abstract
In this paper, we study classes of Boolean functions that are testable with O(ψ + 1/ϵ)
queries, where ψ depends on the parameters of the class (e. , the number of terms, the number
of relevant variables, etc. Then, in Section 8, we present the reduction from property testing C to property testing C[m],
where m is the number of blocks. Since the number of blocks is determined by the parameters of
the class being tested and is independent of the total number of variables n, the query complexity
of property testing C[m] is also independent of n. ) but not on the total number of variables n. In particular, when
ϵ ≤ 1/ψ, the query complexity is O(1/ϵ), matching the known tight bound Ω(1/ϵ). This result was previously known for classes of terms of size at most k and exclusive OR
functions of at most k variables. In this paper, we extend this list to include the classes: k-junta,
functions with Fourier degree at most d, s-sparse polynomials of degree at most d, and s-sparse
polynomials.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Extension of Known Results
The authors demonstrate that the property holds for several classes beyond those previously studied <ref:2604.05615#pg2>. Specifically, they show this for k-junta when ϵ < 1/(k 2/k), functions with Fourier degree at most d when ϵ < 1/Θ(2 2d), s-sparse polynomials of degree at most d when ϵ. p. 0 In this paper, we extend this list to include the classes: k-junta,
functions with Fourier degree at most d, s-sparse polynomials of degree at most d, and s-sparse
polynomials. Additionally, we show that for any class C of Boolean functions that depend on at most k
variables, if C is properly exactly learnable, then it is testable with O(1/ϵ) queries for ϵ < 1/ψ,
where ψ depends on k and independent of the total number of variables n. In this paper, we extend this list to include the classes: k-junta,
functions with Fourier degree at most d, s-sparse polynomials of degree at most d, and s-sparse
polynomials. Additionally, we show that for any class C of Boolean functions that depend on at most k
variables, if C is properly exactly learnable, then it is testable with O(1/ϵ) queries for ϵ < 1/ψ,
where ψ depends on k and independent of the total number of variables n.Where the paper says it
Where the paper says it
Technique for Variable Reduction
The core technique involves reducing property testing of a class C with n variables to property testing the class C[m] with m variables, where m depends on the parameters of the class but not on n <ref:2604.05615#pg4>. A key technical innovation is substituting fully independent random assignments with pairwise independent ones in simulating tests over the reduced function, which results in a significant improvement in query complexity while preserving correctness guarantees <ref:2604. p. 2 A key technical innovation lies in substituting fully independent
random assignments with pairwise independent ones in simulating tests over the reduced function. This results in a significant improvement in query complexity while preserving the correctness
guarantees of the testing procedure. Additionally, for each influential variable, the algorithm
provides a witness demonstrating its relevance – an assignment where altering the variable’s value
changes the function’s output. This reduces the problem of testing any Boolean functions to testing
functions with at most k influential variables, along with witnesses for each.Where the paper says it
Where the paper says it
Query Complexity Bounds
The paper presents several results summarizing query complexity for various classes <ref:2604.05615#pg3>. For example, the query complexity for k-Junta is O(k log k + 1/ϵ) when ϵ ≤ 1/(k log k), and the authors show that for s-sparse polynomials, there is a result with O(s 2) queries when ϵ = 1/sβ <ref:2604. p. 1 The table in
Figure 1 summarizes these results alongside previously known results. Class of Functions Query Complexity = O(1/ϵ) for Reference
k-Junta O
k log k +
k
ϵ
[3]
O
k2
k +
1
ϵ
ϵ ≤
1
k2
k This Paper
Functions with O˜
2
2d +
2
d
ϵ
[9]
Fourier Degree ≤ d O˜(22d
) + O
1
ϵ
ϵ ≤
1
Θ(2 ˜ 2d)
This Paper
s-Sparse Polynomial O˜
s
ϵ
[9]
of Constant Degree O˜ (s) + O
1
ϵ
ϵ ≤
1
Θ( ˜ s)
This Paper
s-Sparse Polynomial s
ϵ
log β
β +O(1/β) + O˜
s
ϵ
[10]
ϵ = 1/sβ
O˜(s
2
)
ϵ
log β
β +O(1/β)
+ O˜(s) + O
1
ϵ
ϵ < 1
s
8. Let C ⊆ k-Junta be a class that is closed under variable permutations1 and zero-one
projections2
. If C is exactly properly learnable3 with Q(n) queries, then there is a property testing
algorithm for C with
q := Q(O(k
2
)) + O
k log2
k
log log k
+ O
1
ϵ
queries.Where the paper says it
Where the paper says it
Verification and Block Testing
The paper introduces mechanisms to identify influential variables and blocks of variables, which are crucial for the testing algorithms <ref:2604.05615#pg4>. Lemma 18 shows that if C is k-relevant coordinates verifiable with q(n, ϵ) queries, it is (k, α)-relevant blocks verifiable with q(O(K 2), O(ϵ)) + O(1/ϵ + k/α) queries <ref:2604. p. 9 Now, Lemma 10 follows from Lemma 11 and 12. 5 Relevant Coordinates Verifiers
In this section, we present algorithms that, given a function f ∈ C accessible via a black box,
return a small set of relevant variables such that ignoring the other variables results in a function
close to f. To do so, we use the witness for the jth block to find (using f
′
) a function gj that can be queried
and is close to xj . Then, by applying the self-corrector technique, aj can be identified with high
probability using O(1) queries.Where the paper says it
Where the paper says it
Results for Specific Function Classes
The paper provides specific results for Fourier degree at most d functions and s-sparse polynomials <ref:2604.05615#pg4>. For functions with Fourier degree at most d, there is a poly(2d, n)-time testing algorithm with O(22d) + O(1/ϵ) queries <ref:2604. p. 0 We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
Where the paper says it
General Testing Framework
The paper formalizes the relationship between property testing and learning, establishing reductions like Lemma 13 and Lemma 14 <ref:2604.05615#pg4>. These lemmas allow for the construction of testing algorithms based on exact learning or membership testing, leading to bounds such as Theorem 2, which states that if C is exactly learnable with Q(n) queries, there is a property testing algorithm for C with q:= Q(k) + O(kµ(C)) + O(k log squared k log log k) + O(1/ϵ) queries <ref:2604. p. 2 Let C ⊆ k-Junta be a class that is closed under variable permutations and zero-one
projections. If C is exactly learnable with Q(n) queries, then there is a property testing algorithm
for C with
q := Q(k) + O
k
µ(C)
+
k log2
k
log log k
+ O
1
ϵ
queries.Where the paper says it
Lower Bounds
The paper reviews lower bounds for testing k-Junta in the uniform distribution framework, noting that adaptive algorithms make at least omega(k log k) queries, and non-adaptive algorithms make at least omega(k 2)/ϵ queries <ref:2604.05615#pg4>.
Conclusion on Complexity
The final results show that for k-Junta, there is a testing algorithm with O(k squared + 1/ϵ) queries <ref:2604.05615#pg4>. The overall findings establish that classes of Boolean functions can be tested efficiently, often achieving query complexities independent of n <ref:2604. p. 2 Furthermore, this paper
introduces an important advancement by identifying classes that can be tested with O(ψ + 1/ϵ)
queries, where ψ is independent of the number of variables n. Let C be a class of Boolean functions f : {0, 1}
n → {0, 1} that is closed under variable permutations and zero-one projections.Where the paper says it
References
[1] Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing lowdegree polynomials over GF(2). p. 0 This result was previously known for classes of terms of size at most k and exclusive OR
functions of at most k variables. In this paper, we extend this list to include the classes: k-junta,
functions with Fourier degree at most d, s-sparse polynomials of degree at most d, and s-sparse
polynomials. Unless otherwise specified, all the algorithms presented in this paper run in linear time with
respect to the number of variables n and polynomial time in the number of queries. The table in
Figure 1 summarizes these results alongside previously known results.Where the paper says it
Where the paper says it
[2] Eric Blais. Improved bounds for testing juntas. p. 0 Additionally, we show that for any class C of Boolean functions that depend on at most k
variables, if C is properly exactly learnable, then it is testable with O(1/ϵ) queries for ϵ < 1/ψ,
where ψ depends on k and independent of the total number of variables n. 1 Introduction
Property testing of sets of objects was first introduced in the seminal works of Blum, Luby, and
Rubinfeld [4] and Rubinfeld and Sudan [29].Where the paper says it
[3] Eric Blais. Testing juntas nearly optimally. p. 0 Additionally, we show that for any class C of Boolean functions that depend on at most k
variables, if C is properly exactly learnable, then it is testable with O(1/ϵ) queries for ϵ < 1/ψ,
where ψ depends on k and independent of the total number of variables n. 1 Introduction
Property testing of sets of objects was first introduced in the seminal works of Blum, Luby, and
Rubinfeld [4] and Rubinfeld and Sudan [29]. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
Where the paper says it
[4] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. p. 0 Additionally, we show that for any class C of Boolean functions that depend on at most k
variables, if C is properly exactly learnable, then it is testable with O(1/ϵ) queries for ϵ < 1/ψ,
where ψ depends on k and independent of the total number of variables n. 1 Introduction
Property testing of sets of objects was first introduced in the seminal works of Blum, Luby, and
Rubinfeld [4] and Rubinfeld and Sudan [29]. Then, by applying the self-corrector technique, aj can be identified with high
probability using O(1) queries. Then, in Section 8, we present the reduction from property testing C to property testing C[m],
where m is the number of blocks. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
Where the paper says it
Where the paper says it
[5] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Occam’s razor. Inf. Process. Lett., 24(6):377–380, 1987 <ref:2604. p. 0 We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
[6] Nader H. p. 0 Classes Testable with O(1/ϵ) Queries for Small ϵ
Independent of the Number of Variables
Nader H. Bshouty George Haddad
Dept. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
Where the paper says it
[7] Nader H. p. 0 Classes Testable with O(1/ϵ) Queries for Small ϵ
Independent of the Number of Variables
Nader H. Bshouty George Haddad
Dept. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
Where the paper says it
[8] Nader H. p. 0 Classes Testable with O(1/ϵ) Queries for Small ϵ
Independent of the Number of Variables
Nader H. Bshouty George Haddad
Dept. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
Where the paper says it
Where the paper says it
[9] Nader H. p. 0 Classes Testable with O(1/ϵ) Queries for Small ϵ
Independent of the Number of Variables
Nader H. Bshouty George Haddad
Dept.Where the paper says it
[10] Nader H. p. 0 Classes Testable with O(1/ϵ) Queries for Small ϵ
Independent of the Number of Variables
Nader H. Bshouty George Haddad
Dept. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
Where the paper says it
[11] Nader H. p. 0 Classes Testable with O(1/ϵ) Queries for Small ϵ
Independent of the Number of Variables
Nader H. Bshouty George Haddad
Dept. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
Where the paper says it
[12] Nader H. p. 0 Classes Testable with O(1/ϵ) Queries for Small ϵ
Independent of the Number of Variables
Nader H. Bshouty George Haddad
Dept. Classes Testable with O(1/ϵ) Queries for Small ϵ
Independent of the Number of Variables
Nader H. Bshouty George Haddad
Dept. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
Where the paper says it
Where the paper says it
[13] Sourav Chakraborty, David Garc´ıa-Soriano, and Arie Matsliah. Efficient sample extractors for juntas with applications <ref:2604. p. 0 We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
[14] Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie. Settling the query complexity of non-adaptive junta testing <ref:2604. p. 2 However, the algorithms presented in
this paper are significantly simpler and achieve better query complexity. Additionally, the other
5By randomly uniformly substituting 0 and 1 with equal probability in each non-influential variable.Where the paper says it
[15] John Chiarelli, Pooya Hatami, and Michael E. Saks. An asymptotically tight bound on the number of relevant variables in a bounded degree boolean function. p. 0 ) but not on the total number of variables n. In particular, when
ϵ ≤ 1/ψ, the query complexity is O(1/ϵ), matching the known tight bound Ω(1/ϵ). We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
Where the paper says it
[16] Hana Chockler and Dan Gutfreund. A lower bound for testing juntas <ref:2604. p. 0 Specifically, when ϵ ≤ 1/ψ, the query complexity reduces
to O(1/ϵ) which matches the lower bound Ω(1/ϵ) [12, 20]. For instance, in [11], Bshouty presented a
property testing algorithm for the class of functions that can be expressed as an exclusive OR of at
most k variables.Where the paper says it
[17] Artur Czumaj and Christian Sohler. Sublinear-time algorithms. p. 1 Unless otherwise specified, all the algorithms presented in this paper run in linear time with
respect to the number of variables n and polynomial time in the number of queries. The table in
Figure 1 summarizes these results alongside previously known results. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
Where the paper says it
[18] Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. p. 0 Additionally, we show that for any class C of Boolean functions that depend on at most k
variables, if C is properly exactly learnable, then it is testable with O(1/ϵ) queries for ϵ < 1/ψ,
where ψ depends on k and independent of the total number of variables n. 1 Introduction
Property testing of sets of objects was first introduced in the seminal works of Blum, Luby, and
Rubinfeld [4] and Rubinfeld and Sudan [29]. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
Where the paper says it
[19] Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, and Andrew Wan. Efficiently testing sparse GF(2) polynomials <ref:2604. p. 0 We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
[20] Eldar Fischer. A basic lower bound for property testing <ref:2604. p. 0 Specifically, when ϵ ≤ 1/ψ, the query complexity reduces
to O(1/ϵ) which matches the lower bound Ω(1/ϵ) [12, 20]. For instance, in [11], Bshouty presented a
property testing algorithm for the class of functions that can be expressed as an exclusive OR of at
most k variables.Where the paper says it
[21] Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky. Testing juntas <ref:2604. p. 0 We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
[22] Oded Goldreich, editor. Property Testing - Current Research and Surveys, volume 6390 of Lecture Notes in Computer Science <ref:2604. p. 0 1 Introduction
Property testing of sets of objects was first introduced in the seminal works of Blum, Luby, and
Rubinfeld [4] and Rubinfeld and Sudan [29]. Since then, it has evolved into a highly active area of
research; see, for instance, the surveys and books [17, 22, 23, 27, 28].Where the paper says it
[23] Oded Goldreich. Introduction to Property Testing <ref:2604. p. 0 Additionally, we show that for any class C of Boolean functions that depend on at most k
variables, if C is properly exactly learnable, then it is testable with O(1/ϵ) queries for ϵ < 1/ψ,
where ψ depends on k and independent of the total number of variables n. 1 Introduction
Property testing of sets of objects was first introduced in the seminal works of Blum, Luby, and
Rubinfeld [4] and Rubinfeld and Sudan [29].Where the paper says it
[24] Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. p. 0 Additionally, we show that for any class C of Boolean functions that depend on at most k
variables, if C is properly exactly learnable, then it is testable with O(1/ϵ) queries for ϵ < 1/ψ,
where ψ depends on k and independent of the total number of variables n. 1 Introduction
Property testing of sets of objects was first introduced in the seminal works of Blum, Luby, and
Rubinfeld [4] and Rubinfeld and Sudan [29]. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
Where the paper says it
[25] Shirley Halevy and Eyal Kushilevitz. Distribution-free property-testing. p. 0 Additionally, we show that for any class C of Boolean functions that depend on at most k
variables, if C is properly exactly learnable, then it is testable with O(1/ϵ) queries for ϵ < 1/ψ,
where ψ depends on k and independent of the total number of variables n. 1 Introduction
Property testing of sets of objects was first introduced in the seminal works of Blum, Luby, and
Rubinfeld [4] and Rubinfeld and Sudan [29]. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
Where the paper says it
[26] Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, and Jinyu Xie. Distribution-free junta testing <ref:2604. p. 0 We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
[27] Dana Ron. Property testing: A learning theory perspective. p. 0 Additionally, we show that for any class C of Boolean functions that depend on at most k
variables, if C is properly exactly learnable, then it is testable with O(1/ϵ) queries for ϵ < 1/ψ,
where ψ depends on k and independent of the total number of variables n. 1 Introduction
Property testing of sets of objects was first introduced in the seminal works of Blum, Luby, and
Rubinfeld [4] and Rubinfeld and Sudan [29]. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
Where the paper says it
[28] Dana Ron. Algorithmic and analysis techniques in property testing. p. 0 Additionally, we show that for any class C of Boolean functions that depend on at most k
variables, if C is properly exactly learnable, then it is testable with O(1/ϵ) queries for ϵ < 1/ψ,
where ψ depends on k and independent of the total number of variables n. 1 Introduction
Property testing of sets of objects was first introduced in the seminal works of Blum, Luby, and
Rubinfeld [4] and Rubinfeld and Sudan [29]. Bshouty George Haddad
Dept. of Computer Science
Technion, Haifa
April 8, 2026
Abstract
In this paper, we study classes of Boolean functions that are testable with O(ψ + 1/ϵ)
queries, where ψ depends on the parameters of the class (e.Where the paper says it
Where the paper says it
[29] Ronitt Rubinfeld and Madhu Sudan. p. 0 Additionally, we show that for any class C of Boolean functions that depend on at most k
variables, if C is properly exactly learnable, then it is testable with O(1/ϵ) queries for ϵ < 1/ψ,
where ψ depends on k and independent of the total number of variables n. 1 Introduction
Property testing of sets of objects was first introduced in the seminal works of Blum, Luby, and
Rubinfeld [4] and Rubinfeld and Sudan [29]. This result was previously known for classes of terms of size at most k and exclusive OR
functions of at most k variables. In this paper, we extend this list to include the classes: k-junta,
functions with Fourier degree at most d, s-sparse polynomials of degree at most d, and s-sparse
polynomials. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
Where the paper says it
Where the paper says it
[30] Mert Saglam. Near log-convexity of measured heat in (discrete) time and consequences. p. 1 Unless otherwise specified, all the algorithms presented in this paper run in linear time with
respect to the number of variables n and polynomial time in the number of queries. The table in
Figure 1 summarizes these results alongside previously known results. Bshouty George Haddad
Dept. of Computer Science
Technion, Haifa
April 8, 2026
Abstract
In this paper, we study classes of Boolean functions that are testable with O(ψ + 1/ϵ)
queries, where ψ depends on the parameters of the class (e.Where the paper says it
Where the paper says it
[31] Jake Wellens. A tighter bound on the number of relevant variables in a bounded degree boolean function. p. 0 In this paper, we extend this list to include the classes: k-junta,
functions with Fourier degree at most d, s-sparse polynomials of degree at most d, and s-sparse
polynomials. Additionally, we show that for any class C of Boolean functions that depend on at most k
variables, if C is properly exactly learnable, then it is testable with O(1/ϵ) queries for ϵ < 1/ψ,
where ψ depends on k and independent of the total number of variables n. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604.Where the paper says it
Where the paper says it
How the gains come from
The gains in query complexity stem from the technique of reducing property testing to testing functions with a small number of influential variables and their witnesses <ref:2604.05615#pg4>. The authors achieve this by randomly partitioning variables into blocks, where each block is chosen large enough to ensure that if f' ∈ C, then with high probability, each block contains at most one influential variable <ref:2604.05615#pg4>. This procedure reduces the problem to testing functions with at most k influential variables and their corresponding witnesses <ref:2604. p. 2 Additionally, for each influential variable, the algorithm
provides a witness demonstrating its relevance – an assignment where altering the variable’s value
changes the function’s output. This reduces the problem of testing any Boolean functions to testing
functions with at most k influential variables, along with witnesses for each. Then, in Section 8, we present the reduction from property testing C to property testing C[m],
where m is the number of blocks. Since the number of blocks is determined by the parameters of
the class being tested and is independent of the total number of variables n, the query complexity
of property testing C[m] is also independent of n.Where the paper says it
Where the paper says it
Relevant Coordinate Verifiers
The paper introduces the relevant coordinate verifier problem (RCV problem), which requires finding a small set of relevant variables and witnesses <ref:2604.05615#pg4>. Lemma 17 shows that for any class C ⊆ k-Junta, C is k-relevant coordinates verifiable with O(k/µ(C) + k log n) queries <ref:2604. p. 1 Let C ⊆ k-Junta be a class that is closed under variable permutations1 and zero-one
projections2
. If C is exactly properly learnable3 with Q(n) queries, then there is a property testing
algorithm for C with
q := Q(O(k
2
)) + O
k log2
k
log log k
+ O
1
ϵ
queries. , a
(i)
τm for all i ∈ [t]. This reduces the number of queries to O(log(1/ϵ)m+1/ϵ).Where the paper says it
Where the paper says it
Summary of Findings
The paper establishes several tight bounds for various function classes <ref:2604.05615#pg4>. Key results include Theorem 1, which provides a testing algorithm for C with q:= Q(O(k 2)) + O(k log squared k log log k) + O(1/ϵ) queries <ref:2604. p. 1 Let C ⊆ k-Junta be a class that is closed under variable permutations1 and zero-one
projections2
. If C is exactly properly learnable3 with Q(n) queries, then there is a property testing
algorithm for C with
q := Q(O(k
2
)) + O
k log2
k
log log k
+ O
1
ϵ
queries. Since, for x > 2, x/2
x
is a monotone decreasing function, for |T| >
log(s/ϵ), we have
Er[Prx[R
r
p
(T)(x) ̸= T(x)]] ≤
|T|
2
|T|
p ≤
log(s/ϵ)
s/ϵ
η
s log(s/ϵ)
=
ϵη
s
2
. By Markov’s bound, with probability at least 1 − η/s, we have Prx[Rr
p
(T)(x) ̸= T(x)] ≤ ϵ/s. This result was previously known for classes of terms of size at most k and exclusive OR
functions of at most k variables. In this paper, we extend this list to include the classes: k-junta,
functions with Fourier degree at most d, s-sparse polynomials of degree at most d, and s-sparse
polynomials. We demonstrate this for k-junta when ϵ < 1/(k2
k
), functions with Fourier degree at most d when ϵ <
1/Θ(2 ˜ 2d
), s-sparse polynomials of degree at most d when ϵ < 1/Θ(2 ˜ d
s), and s-sparse polynomials
when ϵ < 1/s8. 1
arXiv:2604. Furthermore, this paper
introduces an important advancement by identifying classes that can be tested with O(ψ + 1/ϵ)
queries, where ψ is independent of the number of variables n. Let C be a class of Boolean functions f : {0, 1}
n → {0, 1} that is closed under variable permutations and zero-one projections.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved property testing algorithms for k-junta functions can achieve query complexities of O(1/epsilon) when epsilon is small enough, matching known tight bounds. This allows testing classes like exclusive OR functions of at most k variables with O(k log k + 1/epsilon) queries.
-
The paper introduces a technique to reduce property testing of a class C over n variables to property testing of C[m] where m depends only on the class parameters, allowing query complexity to be independent of the total number of variables n.
-
Algorithms for s-sparse polynomials can be improved, achieving query complexities such as O(s/epsilon) when epsilon is sufficiently small, which is better than previous results like O(s 2/epsilon).
-
For classes of functions with Fourier degree at most d, a polynomial time testing algorithm can be achieved with query complexity of O(22d + 1/epsilon), which is an improvement over the exponential time algorithms previously known.
-
The paper establishes that for any class C of Boolean functions depending on at most k variables, if it is properly exactly learnable, it is testable with O(1/epsilon) queries for epsilon less than 1/psi, where psi depends on k and not n.
Abstract
In this paper, we study classes of Boolean functions that are testable with O(ψ+1/ε) queries, where ψ depends on the parameters of the class (e.g., the number of terms, the number of relevant variables, etc.), is independent of (or sublinear in) 1/ε, and is independent of the total number of variables n. In particular, when ε is sufficiently small so that ε=O(1/ψ), the query complexity is O(1/ε), matching the known tight lower bound Ω(1/ε). In particular, if the structural parameters of the class are fixed and ε=1/ω n(1) (e.g., 1/ n), then the asymptotic query complexity is O(1/ε). This result was previously known for classes of terms of size at most k and exclusive OR functions of at most k variables. In this paper, we extend this list to include the classes: k-junta, functions with Fourier degree at most d, s-sparse polynomials of degree at most d, and s-sparse polynomials. Additionally, we show that for any class C of Boolean functions that depend on at most k variables, if C is properly exactly learnable, then it is testable with O(1/ε) queries for ε<1/ψ, where ψ depends on k and independent of the total number of variables n.
Sources
- A basic lower bound for property testing
- A tighter bound on the number of relevant variables in a bounded degree Boolean function
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles