Classes Testable with O(1/epsilon) Queries for epsilon Below an n-Independent Threshold

arXiv:2604.05615 · cs.DS · Submitted 2026-04-07 · Read on arXiv

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

Where the paper says it

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.

g., the number of terms, the number of relevant variables, etc. p. 0
Where the paper says it

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.

) 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. p. 3
Where the paper says it

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.

05615#pg4>. In particular, when ϵ ≤ 1/ψ, the query complexity reduces to O(1/ϵ), matching the known tight bound omega(1/ϵ) <ref:2604. p. 0
Where the paper says it

) 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/ϵ).

05615#pg4>. 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. p. 0
Where the paper says it

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.

05615#pg2>.

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

Where the paper says it

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.

Furthermore, they 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 <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

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

Where the paper says it

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.

05615#pg4>. This involves reducing the problem to testing functions with at most k influential variables, along with witnesses for each <ref:2604. p. 2
Where the paper says it

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.

05615#pg4>.

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

Where the paper says it

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.

05615#pg3>. Theorem 1 states that if C is exactly properly learnable with Q(n) queries, there is 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
Where the paper says it

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.

05615#pg4>.

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

Where the paper says it

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.

05615#pg4>. Algorithm 7 constructs a testing algorithm for C using a relevant block verifier and a self-corrector, achieving query complexity Q(n, ϵ/(ck), δ/2) + O(k + log(1/δ)) <ref:2604. p. 3
Where the paper says it

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.

05615#pg4>.

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

Where the paper says it

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.

05615#pg4>. For s-sparse polynomials of degree d, there is a testing algorithm with O(s 2) + O(1/ϵ) queries when ϵ = 1/sβ <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

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

Where the paper says it

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.

05615#pg4>.

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

Where the paper says it

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.

05615#pg4>.

References

[1] Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing lowdegree polynomials over GF(2). p. 0

Where the paper says it

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.

In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems <ref:2604. p. 1
Where the paper says it

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.

05615#pg4>.

[2] Eric Blais. Improved bounds for testing juntas. p. 0

Where the paper says it

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].

In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008 <ref:2604.05615#pg4>.

[3] Eric Blais. Testing juntas nearly optimally. p. 0

Where the paper says it

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].

In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

[4] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. p. 0

Where the paper says it

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].

Self-testing/correcting with applications to numerical problems. p. 3
Where the paper says it

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.

J. Comput. Syst. Sci., 47(3):549–595, 1993 <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

[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

Where the paper says it

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.

05615#pg4>.

[6] Nader H. p. 0

Where the paper says it

Classes Testable with O(1/ϵ) Queries for Small ϵ Independent of the Number of Variables Nader H. Bshouty George Haddad Dept.

Bshouty. Exact learning from an honest teacher that answers membership queries <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

[7] Nader H. p. 0

Where the paper says it

Classes Testable with O(1/ϵ) Queries for Small ϵ Independent of the Number of Variables Nader H. Bshouty George Haddad Dept.

Bshouty. Almost optimal distribution-free junta testing <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

[8] Nader H. p. 0

Where the paper says it

Classes Testable with O(1/ϵ) Queries for Small ϵ Independent of the Number of Variables Nader H. Bshouty George Haddad Dept.

Bshouty. Almost optimal testers for concise representations <ref:2604. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

05615#pg4>.

[9] Nader H. p. 0

Where the paper says it

Classes Testable with O(1/ϵ) Queries for Small ϵ Independent of the Number of Variables Nader H. Bshouty George Haddad Dept.

Bshouty. Almost optimal testers for concise representations <ref:2604.05615#pg4>.

[10] Nader H. p. 0

Where the paper says it

Classes Testable with O(1/ϵ) Queries for Small ϵ Independent of the Number of Variables Nader H. Bshouty George Haddad Dept.

Bshouty. Almost optimal proper learning and testing polynomials <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

[11] Nader H. p. 0

Where the paper says it

Classes Testable with O(1/ϵ) Queries for Small ϵ Independent of the Number of Variables Nader H. Bshouty George Haddad Dept.

Bshouty. An optimal tester for k-linear <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

[12] Nader H. p. 0

Where the paper says it

Classes Testable with O(1/ϵ) Queries for Small ϵ Independent of the Number of Variables Nader H. Bshouty George Haddad Dept.

Bshouty and Oded Goldreich. p. 0
Where the paper says it

Classes Testable with O(1/ϵ) Queries for Small ϵ Independent of the Number of Variables Nader H. Bshouty George Haddad Dept.

On properties that are non-trivial to test <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

[13] Sourav Chakraborty, David Garc´ıa-Soriano, and Arie Matsliah. Efficient sample extractors for juntas with applications <ref:2604. p. 0

Where the paper says it

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.

05615#pg4>.

[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

Where the paper says it

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.

05615#pg4>.

[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

Where the paper says it

) 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/ϵ).

Comb., 40(2):237–244, 2020 <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

[16] Hana Chockler and Dan Gutfreund. A lower bound for testing juntas <ref:2604. p. 0

Where the paper says it

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.

05615#pg4>.

[17] Artur Czumaj and Christian Sohler. Sublinear-time algorithms. p. 1

Where the paper says it

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.

Bull. EATCS, 89:23–47, 2006 <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

[18] Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. p. 0

Where the paper says it

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].

Servedio, and Andrew Wan. Testing for concise representations <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

[19] Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, and Andrew Wan. Efficiently testing sparse GF(2) polynomials <ref:2604. p. 0

Where the paper says it

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.

05615#pg4>.

[20] Eldar Fischer. A basic lower bound for property testing <ref:2604. p. 0

Where the paper says it

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.

05615#pg4>.

[21] Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky. Testing juntas <ref:2604. p. 0

Where the paper says it

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.

05615#pg4>.

[22] Oded Goldreich, editor. Property Testing - Current Research and Surveys, volume 6390 of Lecture Notes in Computer Science <ref:2604. p. 0

Where the paper says it

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].

05615#pg4>.

[23] Oded Goldreich. Introduction to Property Testing <ref:2604. p. 0

Where the paper says it

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].

05615#pg4>.

[24] Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. p. 0

Where the paper says it

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].

J. ACM, 45(4):653–750, 1998 <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

[25] Shirley Halevy and Eyal Kushilevitz. Distribution-free property-testing. p. 0

Where the paper says it

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].

SIAM J. Comput., 37(4):1107–1138, 2007 <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

[26] Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, and Jinyu Xie. Distribution-free junta testing <ref:2604. p. 0

Where the paper says it

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.

05615#pg4>.

[27] Dana Ron. Property testing: A learning theory perspective. p. 0

Where the paper says it

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].

Foundations and Trends in Machine Learning, 1(3):307–402, 2008 <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

[28] Dana Ron. Algorithmic and analysis techniques in property testing. p. 0

Where the paper says it

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].

Foundations and Trends in Theoretical Computer Science, 5(2):73–205, 2009 <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

[29] Ronitt Rubinfeld and Madhu Sudan. p. 0

Where the paper says it

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].

Robust characterizations of polynomials with applications to program testing. p. 0
Where the paper says it

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.

SIAM J. Comput., 25(2):252–271, 1996 <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

[30] Mert Saglam. Near log-convexity of measured heat in (discrete) time and consequences. p. 1

Where the paper says it

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.

In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018 <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

[31] Jake Wellens. A tighter bound on the number of relevant variables in a bounded degree boolean function. p. 0

Where the paper says it

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.

CoRR, abs/1903.08214, 2019 <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>.

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

Where the paper says it

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.

05615#pg4>. The final query complexity is derived by analyzing the reduction, showing that it is independent of n <ref:2604. p. 3
Where the paper says it

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.

05615#pg4>.

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

Where the paper says it

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.

05615#pg4>. The algorithm RC-Verify makes O(log n) queries, and the total number of queries made by Binary-Search is at most k log n <ref:2604. p. 4
Where the paper says it

, a (i) τm for all i ∈ [t]. This reduces the number of queries to O(log(1/ϵ)m+1/ϵ).

05615#pg4>.

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

Where the paper says it

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.

05615#pg4>. Furthermore, Theorem 2 gives a bound of q = Q(k) + O(kµ(C)) + O(k log squared k log log k) + O(1/ϵ) queries <ref:2604. p. 9
Where the paper says it

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.

05615#pg4>. The paper concludes that for s-Sparse Polynomials, there is a testing algorithm with O˜(s 2)ϵ! p. 0
Where the paper says it

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.

γ(β)+os(1) + O˜s 2ϵ! 1/β+1 + O˜s) queries <ref:2604. p. 0
Where the paper says it

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.

05615#pg4>. The overall contribution is the demonstration that classes of Boolean functions can be tested efficiently, often achieving query complexities independent of n <ref:2604. p. 2
Where the paper says it

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.

05615#pg4>.

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

  1. 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.

  2. 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.

  3. 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).

  4. 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.

  5. 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

Related papers