CS代考计算机代写 data structure scheme algorithm chain AI decision tree PROPERTY TESTING LOWER BOUNDS VIA COMMUNICATION COMPLEXITY

PROPERTY TESTING LOWER BOUNDS VIA COMMUNICATION COMPLEXITY
Eric Blais, Joshua Brody, and Kevin Matulef
February 21, 2012
Abstract. We develop a new technique for proving lower bounds in property testing, by showing a strong connection between testing and communication complexity. We give a simple scheme for reducing com- munication problems to testing problems, thus allowing us to use known lower bounds in communication complexity to prove lower bounds in testing. This scheme is general and implies a number of new testing bounds, as well as simpler proofs of several known bounds.
For the problem of testing whether a boolean function is k-linear (a par- ity function on k variables), we achieve a lower bound of Ω(k) queries, even for adaptive algorithms with two-sided error, thus confirming a conjecture of Goldreich (2010a). The same argument behind this lower bound also implies a new proof of known lower bounds for testing re- lated classes such as k-juntas. For some classes, such as the class of monotone functions and the class of s-sparse GF(2) polynomials, we significantly strengthen the best known bounds.
Keywords. Property testing, Communication complexity, Lower bounds.
Subject classification. 68Q17
1. Introduction
The field of property testing seeks to formalize the question: what can we determine about a large object, with limited access to the object itself? In general the large object may be anything—for

2 Blais, Brody & Matulef
instance a graph on n nodes, or a function on n variables. In a typical property testing setup, a tester who has unbounded com- putational power is given query access to the large object. The tester’s goal is to accept the object if it has some property P, and reject it if it is “far” from having property P.
In this paper we will primarily concern ourselves with the case when the large object is a boolean function f on n bits. In this case, the tester’s goal is to accept f with probability at least 2/3 if f has property P, and reject with probability at least 2/3 if f must be modified on an ε fraction of the 2n possible inputs in order to have property P. The query complexity (i.e. the number of times the testing algorithm must query f) should hopefully be a small function of ε and n.
The notion of testing boolean functions in this framework goes back to the seminal work of Rubinfeld & Sudan (1996) and has several connections to complexity theory (in particular PCPs and hardness of approximation), as well as computational learning the- ory (Ron 2008). Over the last two decades, researchers have ex- erted a considerable amount of effort to determine the query com- plexity for testing properties of a function f, such as whether f is a linear function (Blum et al. 1993), whether f is isomorphic to a given function (Alon & Blais 2010; Blais & O’Donnell 2010; Chakraborty et al. 2011b), whether f is a k-junta (Blais 2008, 2009; Fischer et al. 2004), a monotone function (Fischer et al. 2002; Goldreich et al. 2000), a dictator (Parnas et al. 2002), a halfspace (Matulef et al. 2009), an s-sparse polynomial, a size-s decision tree, etc. (Diakonikolas et al. 2007). Starting with the ground-breaking work of Goldreich et al. (1998), there has also been much effort directed at determining the query complexity for testing proper- ties of graphs and, more generally, of combinatorial objects. (See, e.g., Goldreich 2010b; Ron 2009.)
Over the course of this effort, a variety of techniques have been developed for designing property testing algorithms, thus proving testing upper bounds. However, as is often the case in theoretical computer science, lower bounds are harder to come by. Although several lower bounds for specific problems are known, few general techniques are known beyond the use of Yao’s minimax lemma.

Property Testing Lower Bounds 3
Communication complexity is an area which has collected many effective techniques for proving lower bounds in other areas of com- puter science. In a typical setup, two parties, Alice and Bob, each have an input and they would like to decide something about their joint input. Their computational power is unbounded, but they would like to compute the answer with as little communication as possible.
The communication complexity framework has been extensively studied; in particular, several problems are known to require a large amount of communication. These include set-disjointness, in- dex, inner-product, and gap-hamming-distance. The hard- ness of these and related problems has been used to obtain lower bounds in many areas such as streaming algorithms, circuit com- plexity, data structures, and proof complexity (Indyk & Woodruff 2003; Kushilevitz & Nisan 1997; Miltersen et al. 1995).
Property testing and communication complexity have striking similarities. Both involve parties with unbounded computational power (in one case, the tester, and in the other case, the commu- nicating players), and both involve algorithms which are restricted by the parties’ limited access to their input. Despite these similar- ities, no previous connection between these fields has been made.
In this work we show that there is indeed a strong connection between testing and communication complexity. More specifically, we show how to reduce certain communication problems to prop- erty testing problems. This reduction method represents a new approach to proving testing lower bounds. This approach turns out to be quite fruitful, both for proving new bounds and for giv- ing simpler proofs of known bounds in property testing.
1.1. Our Results. A detailed description of our results follows below.
Testing k-linear functions. The function f : {0, 1}n → {0, 1} is linear, i.e. a parity function, when there exists a set S = {i1,…,is} ⊆ [n] such that for every x ∈ {0,1}n, f(x) = xi1 ⊕···⊕ xis . When |S| = k, we say that f is a k-linear function. The prob- lem of testing k-linear functions was first studied by Fischer et al.

4 Blais, Brody & Matulef
(2004). The best lower bound is due to Goldreich (2010a), who
k) queries are required to test k-linear functions. He also showed that non-adaptive testers require Ω(k) queries to test the same property, and conjectured that this stronger lower
bound holds for all testers (adaptive or not).1
We confirm Goldreich’s conjecture. Using the same construc-
tion, we also obtain lower bounds on the query complexity for testing juntas,2 testing functions of low Fourier degree, and testing sparse polynomials.
Theorem 1.1. Fix 1 < k < n−1. At least Ω(min{k,n−k}) queries are required to test (i) k-linear functions, (ii) k-juntas, (iii) functions of Fourier degree at most k, and (iv) functions with k-sparse polynomial representation in GF(2). Remark 1.2. In parallel work, Blais & Kane (2011) simultane- ously obtained a different proof of Goldreich’s conjecture using Fourier-analytic methods. Theorem 1.1 has implications for the problem of isomorphism testing, or testing whether an unknown function f is equivalent, up to permutation of variables, to a fixed function g : {0,1}n → {0,1}. Alon & Blais (2010) showed that for most functions g, testing g-isomorphism non-adaptively requires Ω(n) queries. Sim- ilarly, Chakraborty et al. (2011b) showed that for every k ≤ n, 1The conjecture and results of Goldreich (2010a) are stated in terms of testing ≤k-linear functions (the class of functions that are parities on at most k bits) but the proofs of Goldreich (2010a) give identical lower bounds for testing k-linearity. Similarly, the technique in our lower bounds for testing k-linearity gives identical bounds for testing ≤k-linearity. 2Informally, a function is a k-junta if it has at most k relevant variables. For a complete definition of the properties stated in Theorem 1.1, see Section 3. Similarly, the properties introduced in the rest of the introduction are defined formally in the sections containing the proofs of the corresponding theorems. showed that Ω( √ Property Testing Lower Bounds 5 there exists a k-junta g such that testing g-isomorphism requires Ω(k) queries. Both of these results are non-constructive, and they raise the question of whether we can identify an explicit func- tion for which the same lower bounds apply. Theorem 1.1 shows that for every k ≤ n, the lower bound applies to the function 2 g : x 􏰶→ x1 ⊕ · · · ⊕ xk since testing isomorphism to this function is equivalent to testing k-linearity. Testing and OBDDs. Fix some finite sets X and Y . An ordered binary decision diagram (OBDD) is a directed acyclic graph with a single root and at most n + 1 levels of nodes. The sink nodes in the last level are each associated with some element from Y . All other levels are associated with an index from {1, . . . , n}. The nodes in these levels have out-degree |X|, with one edge associated with each element of X. For x = (x1,...,xn) ∈ Xn, define f(x) to be the value of the sink node that we reach when we start at the source, then at each level we follow the edge associated with xi, where i is the index associated with the current level. The resulting function f : Xn → Y is the function computed by the OBDD. The width of an OBDD is the maximum number of nodes at any level. Ron & Tsur (2009) first studied the problems of determining the query complexity for testing whether a function is computable by small-width OBDDs. Goldreich (2010a) continued this line of research and also asked whether we can establish stronger lower bounds for the query complexity of testing properties that include a subset of the functions computable by small-width OBDDs. In particular, he showed that there is a property consisting of func- tions computable by width-2 OBDDs that requires Θ(n) queries to test. Theorem 1.1 gives a different proof of the same result, since n -linear functions are computable by width-2 OBDDs. 2 Goldreich (2010a) conjectured in that an identical lower bound also held for testing an explicit subclass of functions computable by width-3 OBDDs and for testing functions computable by width-4 OBDDs. Recently, he observed (private communication) that the method of the proof of Theorem 1.1 can also be used to prove these conjectures: 6 Blais, Brody & Matulef Theorem 1.3. Testing the class of linear functions from GF(3)n to GF(3) that have only 0-1 coefficients requires Θ(n) queries. Note that this class of functions can be trivially computed by a width-3 OBDD by maintaining a partial sum of the inputs. Theorem 1.4. Testing the class of functions that are computable by width-4 OBDDs requires Θ(n) queries. Remark 1.5. Theorem 1.4 was proved independently by Brody et al. (2011). Testing monotonicity. Fix R ⊆ R. The function f : {0, 1}n → R is monotone if for any two inputs x,y ∈ {0,1}n where x1 ≤ y1,...,xn ≤ yn, we have that f(x) ≤ f(y). The problem of test- ing monotonicity was first studied by Goldreich et al. (2000), who introduced a natural tester: sample random edges from the hyper- cube and verify that the function is monotone on those edges. This algorithm makes O(n log |R|) queries (Dodis et al. 1999). An im- portant open problem in property testing is to determine whether there exist more efficient monotonicity testers. Despite much attention to monotonicity testing (Batu et al. 1999; Bhattacharyya et al. 2009; Bri ̈et et al. 2010; Dodis et al. 1999; Ergun et al. 2000; Fischer et al. 2002; Goldreich et al. 2000), lower bounds for the query complexity of this problem have been elusive. Previously, the best bound for non-adaptive testers, due to Fischer et al. (2002), was only Ω(log n). This translates to a Ω(log log n) lower bound for general (adaptive) testers.3 We pro- vide a significant improvement to this lower bound for functions with large ranges: Theorem 1.6. Testing f : {0, 1}n → R for monotonicity requires Ω(min{n, |R|2}) queries. Notably, Theorem 1.6 gives the first progress on the natural- monotonicity-tester problem mentioned above: it shows that for 3Stronger bounds have been established for testers with one-sided error. See (Bri ̈et et al. 2010; Fischer et al. 2002) for details. Property Testing Lower Bounds 7 √n ≤ |R| ≤ poly(n), no monotonicity tester can improve on the query complexity of the natural tester by more than a logarithmic factor. We note, however, that this problem is still open in the important special case when R = {0, 1}. By a recent result of Seshadhri & Vondr ́ak (2011), Theorem 1.6 also gives a new lower bound for the query complexity of testing submodularity. Corollary 1.7. Testing f : {0,1}n → R for submodularity re- quires Ω(n) queries. Testing concise representations. Parnas, Ron & Samorodnit- sky (2002) showed that testing whether a function can be repre- sented by a monotone DNF with at most s terms can be done with a number of queries that depends only on s. This result was gen- eralized by Diakonikolas et al. (2007), who introduced the method of testing by implicit learning and showed that this method can be used to test whether a function can be represented by a DNF with few terms, by a small decision tree, by a small branching program, etc. Our technique gives lower bounds on the query complexity for testing two of these properties. Theorem 1.8. At least Ω(min{s, n − s}) queries are required to test (i) size-2s decision trees, and (ii) size-s branching programs. Testing juntas. The proof of Theorem 1.8 can also be extended to answer a question of Fischer et al. (2004): they asked if the query complexity of testing k-juntas can be reduced if the tester is only required to reject functions that are far from (k+t−2)-juntas for some t > 0. We show that the answer to this question is “no” √
foranyt≤O( k).
Theorem 1.9. Fix k ≤ n and t > 0. Any algorithm that accepts
2
k-juntas and rejects functions 1 -far from (k + t − 2)-juntas with
􏰃4 k2 􏰄
high probability must make Ω min{( t ) , k} queries.

8 Blais, Brody & Matulef
Remark 1.10. Subsequently, the result of Theorem 1.9 was es- sentially strengthened by Ron & Tsur (2011), who showed that for any constants ε and γ, a nearly linear lower bound of Ω(k/logk) queries holds even if we are only required to accept k-juntas and reject functions that are ε-far from (1 + γ)k-juntas.
Testers with one-sided error. The technique we introduce for proving new lower bounds can also be used to prove lower bounds for testers with one-sided error (that is, testers which accept func- tions with probability 1 if they have property P, and reject them with probability at least 2/3 if they are far from having property P). As a first application, we get a much stronger lower bound for the query complexity of testing decision trees with one-sided error.
Theorem 1.11. At least Ω(s) queries are required to test size-s decision trees with one-sided error.
We also obtain a lower bound on the query complexity of one- sided testers for a subclass of halfspaces, the class of “signed” ma- jority functions on k variables.
Theorem 1.12. Fix any constant γ ∈ (0, 1). For k ≤ γn, at least Ω(k/logk) queries are required to test signed k-majorities with one-sided error.
1.2. Techniques. The main idea behind all of our lower bounds is to show that the query complexity for testing a property P is bounded below by the randomized communication complexity of some well-studied communication game G. To do so, we introduce a P-testing game. The definition of this game varies according to the situation, but typically looks like this: Alice receives a boolean function f, Bob receives a boolean function g, and they must test whether the joint function h = f ⊕ g has the property P. We can then relate the number of queries required to test whether h has this property to the number of bits Alice and Bob need to communicate. Finally, we show that the P-testing game requires large communication by using it to solve G.

Property Testing Lower Bounds 9
This technique is best illustrated by example. In fact, we can give a very simple sketch of the proof of Theorem 1.1 (i), by show- ing how to reduce a version of the well-known set-disjointness problem to testing k-linearity. Suppose Alice and Bob each have sets of size k from a universe of size n. Suppose further that their sets are guaranteed to either intersect in exactly one place, or not at all, and they want to decide which is the case. We let k-disj de- note this particular setting for set-disjointness. It is well-known that the communication complexity of k-disj is Ω(k) (H ̊astad & Wigderson 2007; Kalyanasundaram & Schnitger 1992).
One way Alice and Bob can solve k-disj is by forming lin-
ear functions based on their two sets. For a set S ⊆ [n], define
ParityS to be the linear function on the bits indexed from S; i.e.,
ParityS(x) := 􏰁i∈S xi. Given input sets A and B, Alice forms
the function f = ParityA and Bob forms the function g = ParityB.
The joint function h = f ⊕g is 2k-linear if the sets do not intersect,
and (2k − 2)-linear if they do. Note that every 2k-linear function
is 1 -far from being (2k − 2)-linear (see Proposition 3.4). Therefore, 2
they can determine if their sets intersect by emulating a testing al- gorithm for (2k − 2)-linearity on h. The testing algorithm requires oracle access to h, which neither Alice nor Bob have. However, they do know f and g, so Alice and Bob can simulate oracle access to h by exchanging f(x) and g(x), at a cost of two bits of com- munication per query. The total number of bits communicated is then twice the number of queries of the tester. Since we can lower bound the number of bits communicated by Ω(k), this implies that testing (2k − 2)-linearity also requires Ω(k) queries. By scaling k, we achieve the first part of Theorem 1.1.
To summarize, our lower bound for testing k-linearity follows from three inequalities. Letting Ck-linear denote the communica-
tion game where Alice and Bob get f and g as input and wish to determine if f ⊕ g is k-linear or far from k-linear, and using Q(P) to denote the query complexity of testing for P and R(G) to denote the randomized communication complexity of a commu- nication game G, we achieve a lower bound on testing k-linearity via the following chain of inequalities:
(1.13) 2Q(k-linear) ≥ R(Ck-linear) ≥ R(k-disj) = Ω(k) . ⊕
⊕

10 Blais, Brody & Matulef
All of the testing lower bounds in this paper follow the above struc- ture. A crucial aspect of this proof technique is that emulating the property testing algorithm must be done in a communication ef- ficient manner. In the example above, the joint function h was just the xor of Alice’s and Bob’s functions, so simulating each query required only two bits of communication. For other lower bounds, we require more complicated ways to build a joint func- tions. However, as long as each h(x) can be simulated with low communication, a similar lower bound will hold. We formalize this statement in Lemma 2.4.
Note that in most situations, it is possible to use problems such as k-disj whose communication complexity is well understood, and therefore we get the equality in (1.13) essentially for free. The re- duction in the first inequality is captured by Lemma 2.4, so for most proofs, the bulk of the actual work is in proving a so-called “dis- tance lemma”—that yes instances for the communication problem map to instances where the combined function has property P, and that no instances will map to functions that are far from having P. In most cases, as in Proposition 3.4, these are simple to prove.
1.3. Organization. In Section 2, we introduce the communi- cation complexity and property testing definitions, the Main Re- duction Lemma (Lemma 2.4), and the communication complexity lower bounds that we use in the later sections.
The proofs of Theorem 1.1–1.4, as well as the formal definitions of the properties defined in those theorems, are presented in Sec- tion 3. The lower bound in Theorem 1.6 for testing monotonicity and the lower bound in Corollary 1.7 for testing submodularity are presented in Section 4. We complete the proof of Theorem 1.8 re- garding the query complexity for testing functions computable by small decision trees or by small branching programs in Section 5. In the same section, we also complete the proof of Theorem 1.9. Finally, we present the lower bounds on the query complexity of one-sided testers for decision trees (Theorem 1.11) and for unsigned k-majority functions (Theorem 1.12) in Section 6.

Property Testing Lower Bounds 11 2. From Communication Complexity to
Property Testing
2.1. Property Testing Definitions. Recall that for a fixed range R ⊆ R, a property of the functions {0, 1}n → R is a sub- set of those functions. The distance between two functions f,g : {0,1}n → R is the fraction of inputs x ∈ {0,1}n for which f(x) ̸= g(x). The distance between f and a property P is the minimum distance between f and any function g in P. When the distance fromf toP isatleastε,wesaythatf isε-far fromP.
Definition 2.1 (Tester). An (ε,q)-tester for the property P of functions {0,1}n → R is a randomized algorithm that queries a function f : {0, 1}n → R on at most q inputs from {0, 1}n and
(i) Accepts with probability at least 2 when f is in P; and 3
(ii) Rejects with probability at least 2 when f is ε-far from P. 3
A tester is said to be non-adaptive if it selects its q queries
before observing the value of f on any of those queries; otherwise
it is adaptive. A tester that always accepts functions in P has one-
sided error; a tester that accepts functions in P with probability
p for some 2 ≤ p < 1 has two-sided error. 3 For any 0 < ε < 1, the query complexity of the property P at distance ε, denoted Qε(P), is the minimum value of q for which P has an (ε,q)-tester. Similarly, Q1(P) and Qna(P) denote the εε minimum number of queries required to ε-test P with one-sided error and non-adaptive testers, respectively. Throughout this work, we will assume that ε is a small fixed constant—say, ε = 0.01 for concreteness—and for simplicity we state all query complexity bounds only in terms of the other parameters and will omit ε from the notation. 2.2. Communication Complexity Definitions. In this sub- section, we review the basic communication complexity setup and highlight some of the terms and concepts particularly relevant to this article. For more details, we refer the interested reader to the standard textbook by Kushilevitz & Nisan (1997). 12 Blais, Brody & Matulef In a typical communication game, there are two parties—Alice, who receives an input x, and Bob, who receives some input y. Al- ice and Bob wish to jointly compute some function f(x,y) of their inputs. Neither player sees all the information needed to compute f, so they must communicate together to solve the problem. Com- munication complexity is the study of how much communication is necessary to compute f, for various functions f. A protocol is a distributed algorithm that Alice and Bob use to compute f(x,y); in particular, it specifies what messages Alice and Bob send to each other. In a deterministic protocol, Alice’s messages are a function only of her input x and the previous com- munication in the protocol. Similarly, Bob’s messages are a func- tion of y and the previous communication. The cost of a protocol is the maximum (over all inputs) number of bits sent by Alice and Bob. The deterministic communication complexity of f, denoted D(f), is the minimum cost of a deterministic protocol computing f. In a randomized protocol, Alice and Bob have shared access to a (public coin) random string r ∈ {0,1}∗. We say that P is a δ-error protocol for f if for any input pair x, y, P computes f (x, y) with probability at least 1 − δ, where the probability is taken over the random string r. We use Rδ(f) to denote the minimum cost of a δ-error protocol for f and define R(f) := R1/3(f). When f is a binary function, we say that a protocol computes f with one-sided error if there exists z ∈ {0, 1} such that P computes f with certainty whenever f (x, y) ̸= z, and with probability at least 1 − δ when f (x, y) = z. When considering randomized protocols with one-sided error, it is important to note which “side” the error guarantee is on. We use Rδz(f) to denote the minimum cost of a randomized protocol for f that correctly computes f whenever f (x, y) ̸= z and computes f with probability at least 1−δ whenever f(x,y) = z. We define Rz(f) := Rz (f). 1/3 A protocol is one-way if the communication consists of a sin- gle message from Alice to Bob, who then outputs an answer. We use Rδ→(f) to denote the minimum communication cost of a ran- domized, δ-error, one-way protocol for f. Finally, we use R→,z(f) δ to denote the minimum communication cost of randomized one- Property Testing Lower Bounds 13 way protocols for f with with one-sided error δ, and we define R→,z(f) := R→,z(f). 1/3 2.3. The Main Reduction. Below we define a class of property testing communication games and show how communication lower bounds for these games yield query complexity lower bounds for property testers. Our communication games are based on what we call combining operators. Definition 2.2 (Combining operator). A combining operator is an operator ψ that takes as input two functions f, g : {0, 1}n → Z and returns a function h : {0, 1}n → R. We refer to the inputs f and g as the base functions of ψ. By con- vention, we use h to refer to the output of ψ. Given a combining operator ψ and a property P, we define CPψ to be the following property testing communication game. Alice receives f. Bob re- ceives a function g. They need to compute 􏰀1 ifψ(f,g)∈P CPψ(f,g) := 0 if ψ(f,g) is ε-far from P. We prove all of our testing lower bounds by reducing from an associated communication game CPψ . As mentioned in Section 1.2, thisreductionissimple—AliceandBobsolveCPψ byemulatingaP- testing algorithm on h := ψ(f, g). Note that neither Alice nor Bob have enough information to evaluate a query h(x), because h de- pends on both f and g. Instead, they must communicate to jointly compute h(x). For this reduction to give a strong query complexity lower bound for the property testing problem, it is essential that the joint computation of h(x) occurs in a communication-efficient manner. The following definition gives a sufficient condition on combin- ing operators that yield strong reductions to testing problems. Definition 2.3 (Simple combining operator). A combining oper- ator ψ is simple if for all f, g, and for all x, the query h(x) can be computed given only x and the queries f(x) and g(x). 14 Blais, Brody & Matulef For example, when the base functions are boolean, the combin- ing operator defined by ψ(f, g) := f ⊕ g is clearly simple—each h(x) = f (x) ⊕ g(x) can trivially be computed from f (x) and g(x). On the other hand, the combining operator ψ that returns the function defined by h(x) := 􏰁y∈T [f (y) · g(y)] is not simple when T is a large set of strings (say a Hamming ball centered at x), since computing h(x) requires knowledge of f(y) and g(y) for several y. All of the property testing communication games we use in this paper are based on simple combining operators and give us a tight connection between property testing and communication complexity via the following lemma. Lemma 2.4 (Main Reduction Lemma). Fix Z to be a finite set. For any simple combining operator ψ with base functions f,g : {0, 1}n → Z and any property P, we have (i) R(CPψ)≤2Q(P)·⌈log|Z|⌉, (ii) R0(CPψ)≤2Q1(P)·⌈log|Z|⌉, (iii) R→(CPψ ) ≤ Qna(P) · ⌈log |Z|⌉, and (iv) R→,0(CPψ ) ≤ Qna,1(P) · ⌈log |Z|⌉. Proof. We begin by proving (iii). Let A be a q-query non- adaptive tester for P. We create a one-way protocol P for CPψ in the following manner. Alice and Bob use public randomness to gener- ate queries x(1), . . . , x(q). Then, Alice computes f(x(1)), . . . , f(x(q)) and sends them to Bob in a single (q · ⌈log |Z|⌉)-bit message. For each i, Bob computes g(x(i)) and combines it with f(x(i)) to compute h(x(i)). Finally, Bob emulates A using the responses h(x(1)), . . . , h(x(q)) and outputs 1 if and only if A accepts h. If A has two-sided error, then by the correctness of A, P computes CPψ with probability at least 2/3. Hence, R→(CPψ) ≤ q · ⌈log |Z|⌉. In particular, if A is an optimal non-adaptive tester with two-sided error, then q = Qna(P), and part (iii) of the lemma is proved. If A has one-sided error, then whenever h ∈ P, the protocol P correctly outputs 1, and when h is ε-far from P, the proto- col correctly outputs 0 with probability at least 2/3. Therefore, Property Testing Lower Bounds 15 R→,0(CPψ ) ≤ q · ⌈log |Z|⌉. In particular, when A is an optimal non- adaptive tester with one-sided error, R→,0(CPψ) ≤ Q1(P)·⌈log|Z|⌉. Now, suppose A is a q-query adaptive tester for P. Again, Alice and Bob use public randomness to generate queries x(1),...,x(q). However, since A is adaptive, the distribution of the ith query x(i) depends on h(x(j)) for all j < i. Instead of generating all queries in advance, Alice and Bob generate queries one at a time. Each time a query x(i) is generated, Alice and Bob exchange f(x(i)) and g(x(i)). Since ψ is a simple combining operator, this is enough information for Alice and Bob to individually compute h(x(i)), which in turn gives them enough information to generate the next query with the appropriate distribution. When h(x(1)),...,h(x(q)) have all been computed, Bob outputs 1 if and only if A accepts h. This protocol costs 2q · ⌈log |Z|⌉ bits of communication, and if A is an optimal adaptive tester, then R(CPψ ) ≤ 2 Q(P) · ⌈log |Z|⌉. Similarly, if A is an optimal adaptive tester with one-sided error, then R0(CPψ ) ≤ 2 Q1(P) · ⌈log |Z|⌉. 􏰮 2.4. Communication Complexity Problems. We achieve all of our testing lower bounds via Lemma 2.4. To prove lower bounds for CPψ , we reduce from one of several standard communication complexity problems. However, we often require special flavors of these problems—either we need protocols with one-sided error, or we require the input to be restricted in some balanced way. We describe the variants that we will need for our reductions in this section. Let n ∈ N,t := t(n), and x,y ∈ {0,1}n. We use ◦ to denote string concatenation and 0k (1k) to denote the string of k consec- utive zeros (ones). Let x ⊕ y denote the bitwise exclusive-or of x and y. We use 1 − x to denote the bitwise complement of x. The Hamming weight of a string x, denoted |x|, is the number of i such that xi = 1. The Hamming distance between strings x and y, denoted ∆(x, y), is the number of coordinates i such that xi ̸= yi. Note that ∆(x, y) = |x ⊕ y|. We are interested in the following functions: 16 Blais, Brody & Matulef Set-Disjointness. Alice and Bob are given n-bit strings x and y respectively and wish to compute n disjn(x, y) := 􏰘 xi ∧ yi . i=1 Equivalently, Alice and Bob’s inputs can be viewed as sets A, B ⊆ [n]. In this case, disj(A, B) = 1 if and only if their sets intersect. When n is clear from context, we drop the subscript. A cele- brated result of Kalyanasundaram & Schnitger (1992), later simpli- fied by Razborov (1990) and Bar-Yossef et al. (2002), showed that R(disjn) = Ω(n), even under the promise that A and B intersect in at most one element. Theorem 2.5 (Kalyanasundaram & Schnitger 1992). R(disjn) = Ω(n). We use a balanced version of disjointness called k-bal-disj. In this version, Alice receives a set A ⊆ [n] of size |A| = ⌊k/2⌋ + 1, Bob receives a set B ⊆ [n] of size ⌈k/2⌉ + 1, and there is a promise that |A ∩ B| ≤ 1. Lemma 2.6. For all 0 ≤ k ≤ n − 2, we have R(k-bal-disj) = Ω (min{k, n − k}). Proof. If n−k = O(1), there is nothing to prove. Otherwise, let m := min{⌊k/2⌋ + 1, n − k − 2}. We reduce from disjm. Partition the elements of [n][m] into sets I := {m+1,...,m+1+⌊k/2⌋} and J := {m + 2 + ⌊k/2⌋,...,n}. Note that |I| = ⌊k/2⌋ + 1. Furthermore, we have |J| ≥ ⌈k/2⌉ + 1, since |J| = n−(m+2+⌊k/2⌋)+1 = n−1−m−⌊k/2⌋ = n−1−m+⌈k/2⌉−k = ⌈k/2⌉+1+n−2−m−k ≥ ⌈k/2⌉+1, Property Testing Lower Bounds 17 where the penultimate equality holds because k = ⌊k/2⌋ + ⌈k/2⌉, and the inequality comes from the fact that m ≤ n − k − 2. Let A′ and B′ be the sets received by Alice and Bob respectively as inputs to disjm. Alice pads her input with elements from I until she gets a set of size ⌊k/2⌋ + 1. Bob similarly pads his input with elements from J. Let a := ⌊k/2⌋+1−|A′| and b := ⌈k/2⌉+1−|B′|. Specifically, Alice sets A = A′ ∪ {m + 1,...,m + a} and Bob sets B = B′ ∪ {n, n − 1, . . . , n − b + 1}. Note that |A| = ⌊k/2⌋+1, |B| = ⌈k/2⌉+1, and A∩B = A′ ∩ B′. Therefore, a solution to k-bal-disj(A, B) gives a solution to disjm(A′, B′), hence R(k-bal-disj) ≥ R(disjm) = Ω(m) = Ω(min{k, n − k}) . 􏰮 Gap-Equality. Alice and Bob are given n-bit strings x and y respectively and wish to compute 1 ifx=y,  geqn,t(x,y) := 0 if ∆(x,y) = t, ∗ otherwise. We drop the subscripts when n is clear from context and t = n/8. When geq(x, y) = ∗, we allow the protocol to output 0 or 1. We are interested in Rz(geq); recall that Rz(geq) is the minimum communication cost of a protocol for geq that only makes mis- takes when geq(x,y) = z. The standard public-coin equality protocol gives R0(geq) = O(1). For protocols that only err when geq(x, y) = 1, the complexity is drastically different. Buhrman et al. (1998) proved an Ω(n) lower bound on the de- terministic communication complexity of geqn,n/2; their result ex- tends to other gap sizes and to randomized protocols with one-sided error. Lemma 2.7 (Buhrman et al. 1998). For all even t = Θ(n), we have R1(geqn,t) = Ω(n).4 4Curiously, the parity of t turns out to be necessary. Since ∆(x,y) = |x| + |y| − 2|x ∧ y|, Alice and Bob can deterministically distinguish x = y from 18 Blais, Brody & Matulef Gap-Hamming-Distance. Alice and Bob are given n-bit strings x and y respectively and wish to compute 1 if∆(x,y)≥n/2+t,  ghdn,t(x,y):= 0 if∆(x,y)≤n/2−t, ∗ otherwise. As in the definition of set-disjointness, it will occasionally be useful to view inputs to ghd as sets A,B ⊆ [n] and to express ghd in terms of the size of the symmetric difference |A∆B| rather than Hamming distance ∆(x, y). The standard gap size for ghd is t = √n. In this case, we drop the subscripts and use just ghd. A tight lower bound of R(ghd) = Ω(n) is known, due to Chakrabarti & Regev (2011). Theorem 2.8 (Chakrabarti & Regev 2011). R(ghd) = Ω(n). For larger gap sizes, a padding argument5 implicit in Brody et al. (2010), together with the aforementioned Ω(n) bound for ghd, shows that R(ghdn,t) = Ω((n/t)2) for all t = Ω(√n). When we require one-sided error, the situation changes. Lemma 2.9. For all z ∈ {0,1} and all constant 0 < δ < 1/2, Rz(ghdn,δn) = Ω(n). Proof. First, we prove a lower bound for R0(ghdn,δn). Let d be the least integer greater than or equal to δn, and let m := n/2 + d. We reduce from geqm,2d. Specifically, let P be a protocol for ghdn,δn that only makes errors when ghdn,δn(x,y) = 0. We use it to construct a protocol Q for geqm,2d that makes mistakes ∆(x,y) being odd with a single bit of communication—Alice sends Bob the parity of |x|, and Bob computes the parity of |x| + |y|. This does not affect our property testing lower bounds. √ 5This padding argument reduces ghdn,√n to ghdn,t for any n < t ≤ O(n). Choose nˆ such that n = (nˆ/t(nˆ))2, and let m := nˆ/n. Then, given inputs x,y ∈ {0,1}n, Alice and Bob can compute ghdn,√n by repeating each string m times. The resulting strings xˆ and yˆ have length nˆ, and ghdnˆ,t(nˆ)(xˆ,yˆ) = ghdn,√n(x, y), hence a protocol for the former can be used to solve the latter. It follows that R(ghdnˆ,t(nˆ)) ≥ R(ghdn,√n) = Ω(n) = Ω((nˆ/t(nˆ))2). Property Testing Lower Bounds 19 only when x = y. Given inputs x,y ∈ {0,1}m, Alice constructs xˆ := x ◦ 0n−m, and Bob builds yˆ := y ◦ 1n−m. Then, they run protocol P and output Q(x,y) := 1 − P(xˆ,yˆ). Note that if x = y, then ∆(xˆ, yˆ) = n/2 − d ≤ n/2 − δn, hence ghd(xˆ, yˆ) = 0. Simi- larly, when ∆(x,y) = 2d, we have ∆(xˆ,yˆ)=n/2+d≥n/2+δn, and ghd(xˆ, yˆ) = 1. In either case, the new protocol correctly out- puts geqm,2d(x,y) whenever P correctly computes ghdn,δn(xˆ,yˆ). Since P only makes mistakes when ghdn,δn(xˆ,yˆ) = 0, it follows that Q only makes mistakes when geqm,2d(x,y) = 1. Therefore, R0(ghdn,δn) ≥ R1(geqm,2d) = Ω(m) = Ω(n). Next, we prove a lower bound for R1(ghdn,δn). Observe that ghdn,δn(x, y) = 1−ghdn,δn(x, 1−y). Therefore, Alice and Bob can build a protocol for ghdn,δn which errs only when ghdn,δn(x, y) = 0 from one which errs only when ghdn,δn(x,y) = 1 by comput- ing ghdn,δn(x, 1 − y) and inverting the output. It follows that R1(ghdn,δn) ≥ R0(ghdn,δn) = Ω(n). In this way, we get a lower bound for Rz(ghdn,δn) by embedding an instance of geq into either side of the ghd problem. 􏰮 We also consider an extended version of ghd. In eghdn,k,t, Alice and Bob’s inputs x, y are n-bit strings, with the promise that |x| = |y| = k, and they wish to distinguish ∆(x,y) ≥ k + t from ∆(x, y) ≤ k − t. Lemma 2.10. For all k, t ≤ n/2, we have R(eghdn,k,t) = Ω(min{(k/t)2, k}) . In particular, we show that ghdn,t remains hard even under the promise that |x| = |y| = n/2. Proof. First, we prove the lemma for the case k = n/2 by reduction from ghdn/2,t/2. Let P be a protocol for eghdn,n/2,t. Given inputs xˆ, yˆ ∈ {0, 1}n/2 to ghdn/2,t/2, Alice and Bob create n-bit strings x, y by mapping each bit 0 → 01 and each bit 1 → 10.6 Then, they run protocol P on input (x,y) and output the result. 6Formally, Alice creates an n-bit string x by setting x2i−1 := xˆi and x2i := 1 − xˆi for all 1 ≤ i ≤ n/2. Similarly, Bob defines y by setting y2i−1 := yˆi and y2i :=1−yˆi. 20 Blais, Brody & Matulef Note that |x| = |y| = n/2. Furthermore, ∆(x, y) = 2∆(xˆ, yˆ). Therefore, if ∆(xˆ,yˆ) ≥ n/4+t/2 then ∆(x,y) ≥ n/2+t, and simi- larly if ∆(xˆ, yˆ) ≤ n/4−t/2 then ∆(x, y) ≤ n/2−t. It follows that a correct answer for eghdn.n/2,t gives a correct answer to ghdn/2,t/2, hence R(eghdn,n/2,t) ≥ R(ghdn/2,t/2) = Ω 􏰃min 􏰷(n/t)2, n􏰸􏰄 = Ω 􏰃min 􏰷(k/t)2, k􏰸􏰄 . Proving the general case follows from a simple padding argument. Specifically, we reduce eghd2k,k,t to eghdn,k,t. Given 2k-bit strings xˆ and yˆ, Alice and Bob construct n-bit strings x and y by setting x := xˆ◦0n−2k and y := yˆ◦0n−2k. It is easy to see that |x| = |y| = k and that ∆(x,y) = ∆(xˆ,yˆ). Therefore, an answer to eghdn,k,t(x, y) gives an answer to eghd2k,k,t(xˆ, yˆ), hence R(eghdn,k,t) ≥ R(eghd2k,k,t) = Ω 􏰃min{(k/t)2, k}􏰄 . 􏰮 3. Testing k-Linearity and Related Properties In this section we prove Theorem 1.1. Recall that a k-linear func- tion is a function of the form f(x) = 􏰂i∈S xi (mod 2) for some set S ⊆ [n] of size |S| = k. We use k-linear to denote the property that a function is k-linear. The definitions of the other properties in the statement of Theorem 1.1 are as follows: Definition 3.1 (Junta). The function f : {0, 1}n → {0, 1} is a k-junta if there is a set J ⊆ [n] of size |J| ≤ k such that for every x,y∈{0,1}n thatsatisfyxi =yi foreachi∈J,wehavef(x)= f(y). We use k-junta to denote the property that a function is a k-junta. Definition 3.2 (Low Fourier degree). For convenience when dis- cussing Fourier degree we will represent boolean functions using range {−1, 1} instead of {0, 1}. It is well known that every boolean function f : {0, 1}n → {−1, 1} has a unique representation of 􏰂 ˆ 􏰂 xi the form f(x) = S⊆[n] f(S)χS(x), where χS = (−1) i∈S and Property Testing Lower Bounds 21 f(S) ∈ R. The terms f(S) are the Fourier coefficients of f, and ˆˆ the Fourier degree of f is the maximum value of k ≥ 0 such that ˆ7 f(S)̸=0forsomesetSofsize|S|=k. Weusedegree-kto denote the property that the Fourier degree of a function is at most k. Definition 3.3 (Sparse polynomials). Every boolean function f : {0, 1}n → {0, 1} also has a unique representation as a polynomial over GF(2). We say that f is a k-sparse polynomial if its represen- tation over GF(2) has at most k terms. Let k-sparse denote the property that a function has a k-sparse GF(2) representation. The following facts about k-linear functions will be used in the proof of Theorem 1.1: Proposition 3.4. Fix n > 2 and 1 ≤ k ≤ n − 2. If f : {0, 1}n → {0, 1} is (k + 2)-linear, then f is
(i) 1 -far from k-linear functions, 2
(ii) 1-farfromk-juntas, 2
(iii) 1-far from functions of Fourier degree at most k, and 2
(iv) 1 -far from k-sparse polynomials. 20
Proof. We first prove part (iii). Parts (i) and (ii) will follow immediately from part (iii) and the observation that k-juntas and k-linear functions have Fourier degree at most k.
Let f be a (k + 2)-linear function over the variables of some set
T ⊆ [n] of size |T| = k+2, and let g be any function of Fourier
degree at most k. For convenience, we will represent f and g as
functions from {0, 1}n to {−1, 1}. Since f is a linear function over ˆˆ
the variables in T, we know that f(T) = 1, and f(S) = 0 for all S ̸= T. Moreover, since g has Fourier degree k and |T| > k, we know by definition that gˆ(T ) = 0. Thus by Parseval’s theorem
􏰕ˆ
f(S)gˆ(S) = 0 ,
S ⊆[n]
7For more details on the Fourier representation of boolean functions see, e.g., O’Donnell 2008; de Wolf 2008.
E[f(x)g(x)] = x

22 Blais, Brody & Matulef
which implies Prx[f(x) ̸= g(x)] = 1/2.
Finally, part (iv) is a special case of a more general theorem of
Diakonikolas et al. (2007, Thm. 36). For convenience, we provide a self-contained proof as Lemma A.1 in Appendix A. 􏰮
Theorem 1.1 (Restated). Fix 1 < k < n − 1. Then, at least Ω(min{k, n − k}) queries are required to test (i) k-linear functions, (ii) k-juntas, (iii) functions of Fourier degree at most k, and (iv) functions with k-sparse polynomial representation in GF(2). Proof. We prove the lower bound for k-linear functions by re- ducing from the k-bal-disj problem. Recall that Ck-linear is the communication game where the inputs are the functions f,g : {0,1}n → {0,1} and the players must test whether the function h = f ⊕ g is k-linear. Lemma 2.4 and 2.6 imply that 2 Q(k-linear) ≥ R(Ck-linear) ⊕ and To complete the proof, we show that R(Ck-linear) ≥ R(k-bal-disj) R(k-bal-disj) = Ω(min{k, n − k}) . ⊕ with a reduction from k-bal-disj to Ck-linear. ⊕ Let A,B ⊆ [n] be the two sets of size |A| = ⌊k⌋+1 and 2 |B| = ⌈k⌉+1 received by Alice and by Bob, respectively, as the in- 2 put to an instance of k-bal-disj. Alice and Bob can construct the functions ParityA, ParityB : {0, 1}n → {0, 1}. When |A ∩ B| = 1, the symmetric difference of the two sets has size |A△B| = |A| + |B|−2|A∩B| = k, and the function ParityA⊕ParityB = ParityA△B is k-linear. Conversely, when A and B are disjoint, the function ParityA ⊕ ParityB is a (k+2)-parity function and, by Proposi- tion 3.4, it is 1-far from k-linear functions. So Alice and Bob can 2 solve their instance of k-bal-disj with a communication protocol for Ck-linear. This implies that R(Ck-linear) ≥ R(k-bal-disj), as ⊕ ⊕⊕ we wanted to show. The same reduction from k-bal-disj yields lower bounds for testing the other properties. Let Ck-junta denote the communica- ⊕ tion game where Alice and Bob receive boolean functions f and g Property Testing Lower Bounds 23 as inputs and must decide if h = f ⊕ g is a k-junta. Similarly, de- fine Cdegree-k and Ck-sparse to be the corresponding communication ⊕⊕ games where Alice and Bob must decide if h has Fourier degree at most k or can be represented by a k-sparse GF(2) polynomial. In the k-bal-disj reduction above, Alice and Bob create a joint func- tion ParityA△B that is (k + 2)-linear if A and B are disjoint, and k-linear if A and B intersect. By Proposition 3.4, (k + 2)-linear functions are 1 -far from k-juntas, 1 -far from functions with Fourier 22 degree at most k, and 1 -far from k-sparse polynomials. Recalling 20 that a k-linear function is a k-junta, has Fourier degree at most k, and can be represented by a k-sparse GF(2) polynomial, it follows that R(k-bal-disj) ≤ min{R(Ck-junta),R(Cdegree-k),R(Ck-sparse)}. ⊕⊕⊕ Together with Lemma 2.4 and 2.6, we have 2 Q(k-junta) ≥ R(Ck-junta) = Ω(min{k, n − k}) , 2 Q(degree-k) ≥ R(Cdegree-k) = Ω(min{k, n − k}) , and ⊕ 2 Q(k-sparse) ≥ R(Ck-sparse) = Ω(min{k, n − k}) . 􏰮 ⊕ Testing linear functions with 0-1 coefficients. With Oded Goldreich’s kind permission, we present his proof of Theorem 1.3. Theorem 1.3 (Restated). Testing the class of linear functions from GF(3)n to GF(3) that have only 0-1 coefficients requires Θ(n) queries. Proof. The upper bound in the theorem follows from the query complexity of learning subclasses of linear functions over GF(3)n. See Goldreich (2010a) for the details. For the lower bound, we establish a reduction from the set- disjointness problem. Let C{0,1}-Lin be the communication game where Alice and Bob receive the functions f, g : GF(3)n → GF(3), respectively, and must determine if the function h = f + g (where the sum is taken pointwise over GF(3)) is linear and has only {0, 1}- coefficients. By Lemma 2.4 and Theorem 2.5, 4 Q({0,1}-Lin) ≥ R(C{0,1}-Lin) and R(disj) = Ω(n) . + ⊕ + 24 Blais, Brody & Matulef To complete the proof, it suffices to show that R(C{0,1}-Lin) ≥ R(disj). We do so with a reduction from set-disjointness to the {0,1}-Lin testing communication game. Let a, b ∈ {0, 1}n be the strings received by Alice and Bob as input to the set-disjointness problem. Alice and Bob build the functions f,g : GF(3)n → GF(3) defined by f(x) = 􏰂ni=1 aixi and g(x) = 􏰂ni=1 bixi, respectively. The combined function h = f +g is defined by h(x) = 􏰂ni=1(ai + bi)xi. This function is clearly linear. When a and b are disjoint, then every coefficient ai + bi of h takes value 0 or 1. Conversely, when a and b are not disjoint, there is an index i for which ai + bi = 2. Then for any linear function l with {0, 1}-valued coefficients, the function h − l is a non-zero linear function. The Schwartz-Zippel Lemma states that every non-zero linear function over GF(3)n takes the value 0 on at most 1 of the inputs from GF(3)n. Thus, h is 2-far from all the linear 33 functions with only {0, 1}-valued coefficients. Therefore, Alice and Bob can run a protocol for C{0,1}-Lin to solve their instance of set- disjointness and R(C{0,1}-Lin) ≥ R(disj). 􏰮 + Testing computability by width-4 OBDDs. Again with the kind permission of Oded Goldreich, we present his proof of Theo- rem 1.4. We again remark that this result was obtained indepen- dently by Brody et al. (2011), who gave a similar proof. The hard instances we use in this proof are those introduced by Goldreich (2010a). Let nˆ := ⌊n−1⌋. We develop base functions 4 from the following primitive functions. Consider the following four- bit functions φ0, φ1, φ2, φ3 : {0, 1}4 → {0, 1}: φ0(x1, x2, x3, x4) := 0 , φ1(x1,x2,x3,x4):=x1x3 , φ2(x1,x2,x3,x4):=x2x4 , φ3(x1, x2, x3, x4) := x1x3 ⊕ x2x4 . Given z = (z1,...,znˆ) ∈ {0,1,2,3}nˆ, define the function hz : {0, 1}n → {0, 1} by setting nˆ hz(x1,...,xn):=x1 ⊕􏰕φzj(x4j−2,x4j−1,x4j,x4j+1). + + j=1 Property Testing Lower Bounds 25 Lemma 3.5 (Goldreich 2010a, Thm. 4.2). Fix z ∈ {0, 1, 2, 3}nˆ . If every coordinate j ∈ [nˆ] of z satisfies zj ∈ {0, 1, 2} then hz can be computed by a width-4 OBDD. Otherwise, if there exists j ∈ [nˆ] such that zj = 3 then hz is 1 -far from all functions computable 16 by width-4 OBDDs. Goldreich (2010a) uses Lemma 3.5 to show that testing com- putability by width-4 OBDDs requires Ω(√n) queries. We combine this construction with our technique and get an Ω(n) lower bound. Theorem 1.4 (Restated). Testing the class of functions that are computable by width-4 OBDDs requires Θ(n) queries. Proof. We reduce from disjnˆ . Given sets A, B ⊆ [nˆ], Alice and Bobfirstbuildstringsa,b∈{0,1,2,3}nˆ bysetting 􏰀1 ifj∈A 􏰀2 ifj∈B aj := 0 otherwise and bj := 0 otherwise Alice and Bob then define functions f := ha and g := hb. We define the combining operator ψ(f,g) to return the function hz, where zj := aj + bj . By our choice of base functions, for every x ∈ {0, 1}n we have hz(x) = ha(x) ⊕ hb(x) ⊕ x1, so ψ is a simple combining operator. Also, our definitions of a, b, and z imply that zj = 3 iff j ∈ A ∩ B. By Lemma 3.5, this means that hz is computable by a width-4 OBDD when A and B is disjoint and hz is 1 -far 16 from all functions computable by width-4 OBDDs when A and B intersect. Thus, R(C4-OBDD) ≥ R(disjnˆ). This inequality, together ψ with Lemma 2.4, Theorem 2.5, and the fact that nˆ = Θ(n), yields 2 Q(4-OBDD) ≥ R(C4-OBDD) ≥ R(disj ) = Ω(n) . 􏰮 ψ nˆ 4. Testing Monotonicity and Submodularity Fix R ⊆ R. Recall that the function f : {0, 1}n → R is monotone if for any two inputs x,y ∈ {0,1}n that satisfy x1 ≤ y1,...,xn ≤ yn, we have f(x) ≤ f(y). In this section, we prove the following lower bound on the query complexity for testing monotonicity. 26 Blais, Brody & Matulef Theorem Theorem 1.6 (Restated). Testing f : {0, 1}n → R for monotonicity requires Ω(min{n, |R|2}) queries. Proof. We first consider the case where R = R. We prove the lower bound for testing monotonicity in this case with a reduction from set-disjointness. Let ψ be the combining operator that, given two functions f, g : {0, 1}n → {−1, 1}, returns the function h : {0,1}n → Z defined by h(x) := 2|x| + f(x) + g(x). Define Cmono be the communication game where Alice and Bob are given ψ two functions f, g : {0, 1}n → {−1, 1} and they must test whether h is monotone. By Lemma 2.4 and Theorem 2.5, 2 Q(mono) ≥ R(Cmono) and R(disj) = Ω(n) . ψ We complete the proof by showing that R(Cmono) ≥ R(disj). ψ Let A,B ⊆ [n] be the subsets received by Alice and Bob as the input to an instance of the set-disjointness problem. Alice and Bob build functions χA, χB : {0, 1}n → {−1, 1}, respectively, by setting χA(x) = (−1)􏰂i∈A xi and χB(x) = (−1)􏰂i∈B xi. Let h:=ψ(χA,χB). Notethath(x)=2|x|+χA(x)+χB(x).Weclaim that (a) when A and B are disjoint, h is monotone, and (b) when A and B are not disjoint, h is 1 -far from monotone. If this claim is 8 true, then we have completed our lower bound since it implies that Alice and Bob can run a protocol for Cmono to solve their instance of set-disjointness and, therefore, R(Cmono) ≥ R(disj). ψ We now prove Claim (a). Fix i ∈ [n]. For x ∈ {0,1}n, let x0, x1 ∈ {0, 1}n be the vectors obtained by fixing the ith coordinate of x to 0 and to 1, respectively. Note that for any set S ⊆ [n], χS(x1) = −χS(x0) if i ∈ S, and χS(x1) = χS(x0) otherwise. So when i ∈/ A and i ∈/ B, h(x1) − h(x0) = 2 |x1| − 2 |x0| = 2 > 0 , when i ∈ A and i ∈/ B,
h(x1) − h(x0) = 2 |x1| − 2 |x0| − 2 χA(x0) ≥ 0 , and when i ∈/ A and i ∈ B,
h(x1 ) − h(x0 ) = 2 |x1 | − 2 |x0 | − 2 χB (x0 ) ≥ 0 .
ψ

Property Testing Lower Bounds 27
Those three inequalities imply that when i ̸∈ A∩B, the function h is monotone on each edge (x0, x1) in the ith direction. As a result, when A and B are disjoint the function h is monotone.
Let us now prove Claim (b). Let A∩B ̸= ∅. When i ∈ A∩B, h(x1 ) − h(x0 ) = 2 |x1 | − 2 |x0 | − 2 χA (x0 ) − 2 χB (x0 ).
This implies that for each x that satisfy χA(x0) = χB(x0) = 1,
it holds that h(x1 ) < h(x0 ). Partition {0, 1}n into 2n−1 pairs that form the endpoints to all the edges in the ith direction. We claim that at least 1 of these pairs satisfy the condition χA(x0) = 4 χB(x0) = 1. To see this, note that when A = {i}, then χA(x0) = 1 with certainty. On the other hand, if j ∈ A for some j ̸= i, then take any x0, and let xˆ0 be x0 with the jth bit flipped. Then, χA(x0) = −χA(xˆ0). It follows that χA(x0) = 1 with prob- ability exactly 1. A similar argument holds independently for 2 χB(x0). Therefore, at least 1 of these pairs will satisfy the con- 4 dition χA(x0) = χB(x0) = 1, and for each of these pairs, either h(x0) or h(x1) must be modified to make h monotone. Therefore, when A and B intersect, we need to modify at least 2n/8 entries, just to correct the violated edges in the ith direction. It follows that h is at least 1 -far from monotone. 8 Suppose now that |R| ≥ 12√n + 5. Without loss of generality assume R⊇{n−6√n−2,...,n+6√n+2}.8 As before, we do a reduction from set-disjointness. Alice and Bob receive sets A, B ⊆ [n], respectively, and build the functions χA, χB : {0, 1}n → {−1, 1}. The modification to the construction is in the definition of the combining operator. We now define ψ(χA,χB) to return the 8This essentially boils down to a renaming of R. Formally, we prove a lower bound for testing fˆ : {0, 1}n → Rˆ for an arbitrary Rˆ with |Rˆ| ≥ 12√n + 5 by reducing from the problem of testing f : {0,1}n → R. Let φ : R → Rˆ be the bijection that maps the ith least element of R to the ith least element of Rˆ, ˆˆˆ and define f(x) := φ(f(x)). f is monotone if f is monotone, and f is ε-far from monotone if f is ε-far from monotone. Thus, testing fˆ for monotonicity has the same query complexity as testing f for monotonicity. 28 Blais, Brody & Matulef function h′ defined by h(x) if n − 3√n ≤ |x| ≤ n + 3√n , √2√2 h′(x):= n−6 n−2 if|x|n +3 n. 2
Note that when n −3√n ≤ |x| ≤ n +3√n, we have n−6√n−2 ≤ √22′
h(x) ≤ n + 6 n + 2. The definition of h takes strings with low Hamming weight and “rounds h(x) up” to n − 6√n − 2. In the same way, it takes strings of high Hamming weight and “rounds h(x) down” to n + 6√n + 2. We claim that this preserves mono- tonicity when h is monotone, while ensuring that when h is far from monotone, our new function h′ remains reasonably far from monotone.
Claim 4.1. If A and B are disjoint, then h′ is monotone. If A and B intersect, then h′ is 1 -far from monotone.
16
Proof. Suppose that A ∩ B = ∅. We proceed in a manner
similar to the general case. Fix any i ∈ [n], and for x ∈ {0, 1}n, let
x0 and x1 be the vectors obtained by setting the ith bit to 0 and 1
respectively. If A and B are disjoint, then h is monotone. When
|x0| and |x1| both lie in the range {n − 3√n,…, n + 3√n}, then 22
h′(x1) = h(x1) ≥ h(x0) = h′(x0), so monotonicity is preserved. If |x0| and |x1| are either both less than n −3√n or both greater than
n√2′
2 + 3 n, then monotonicity is trivially preserved, as h is constant
on each of these ranges. It remains to show that monotonicity is
preserved when |x0| and |x1| lie in different ranges. But h′(x) =
h(x) ∈ {n−6√n−2,…,n+6√n+2} for all x in this middle
range. Therefore, h′(x) ≤ h′(y) ≤ h′(z) for all x,y,z such that
|x|n +3√n. 222
If A ∩ B ̸= ∅ then h is 1/8-far from monotone. We claim that h′ is at most 1/16-far from h. To see this, let x ∈ {0,1}n be a uniform random string. By the Chernoff Bound,
Pr 􏰥􏰅􏰅|x| − n 􏰅􏰅 > 3√n􏰦 < 0.03 < 1/16 . 2 Furthermore, h′(x) = h(x) whenever n − 3√n ≤ |x| ≤ n + 3√n, hence Pr[h′(x) ̸= h(x)] ≤ 1/16. 22 Property Testing Lower Bounds 29 Suppose for the sake of contradiction that h′ is not 1 -far from 16 monotone, and let h ̃ denote the monotone function closest to h′. By the triangle inequality and the fact that h′ is at most 1/16-far from h, we have Pr[h(x) ̸= h ̃(x)] ≤ Pr[h(x) ̸= h′(x)] + Pr[h′(x) ̸= h ̃(x)] < 1/8 . This violates the fact that h is 1/8-far from monotone. 􏰮 It is possible to make the above argument much tighter, and get the corresponding linear query complexity lower bound for a smaller range of |R|, although |R| remains Ω(√n). We chose the above range size to maximize clarity. Finally, suppose that |R| = o(√n). We prove the lower bound for testing monotonicity in this case via a reduction from the |R| ≥ 12√n + 5 case. Let A be an optimal monotonicity testing algorithm for functions f : {0, 1}n → R, and let m be the greatest integer such that |R| ≥ 12√m + 5. We will use A to construct a monotonicity testing algorithm A′ for functions g : {0, 1}m → R. The construction of A′ depends on the following claim. Claim 4.2. Given a function g : {0, 1}m → R, there exists a function h : {0, 1}n → R with the following properties: (i) If g is monotone, then h is monotone. (ii) If g is ε-far from monotone, then h is ε-far from monotone. (iii) For all x ∈ {0, 1}n, the value of h(x) can be deter- mined with one query to g. Proof. We construct h : {0,1}n → R from g by padding. Specifically, define h(x, y) := g(x) for strings x ∈ {0, 1}m and y ∈ {0,1}n−m. This construction clearly satisfies the first and third conditions of the claim. For the second condition, we prove the contrapositive. Suppose that h is not ε-far from monotone. Let h ̃ be the monotone function closest to h; thus, Prx,y[h ̃(x,y) ̸= h(x, y)] < ε. By an averaging argument, there exists y ̃ ∈ {0, 1}n−m such that Prx[h ̃(x, y ̃) ̸= h(x, y ̃)] < ε. Define g ̃ : {0, 1}m → R 30 Blais, Brody & Matulef as g ̃(x) := h ̃(x,y ̃). Then g ̃ is monotone and Prx[g ̃(x) ̸= g(x)] = Prx[h ̃(x, y ̃) ̸= h(x, y ̃)] < ε, so g is not ε-far from monotone. 􏰮 The construction of A′ is simple. Given input g : {0,1}m → R, let h be the function guaranteed by Claim 4.2. A′ runs A on h and accepts if and only if A accepts h. By Claim 4.2, if g is monotone, then h is monotone, and if g is ε-far from monotone, then h is ε-far from monotone. The correctness of A′ then follows from the correctness of A. Furthermore, by Claim 4.2, A′ uses one query per query of A. However, testing g : {0,1}m → R for monotonicity requires Ω(m) queries, because g has range size |R| ≥ 12√m + 5. Since A is an optimal monotonicity tester and uses the same number of queries as A′, it follows that testing f : {0,1}n → R for monotonicity requires Ω(m) = Ω(|R|2) queries when |R| = o(√n). 􏰮 Testing submodularity. The function f : {0, 1}n → R is sub- modular if for every x, y ∈ {0, 1}n, f(x∨y)+f(x∧y) ≥ f(x)+f(y), where(x∨y)i =max{xi,yi}and(x∧y)i =min{xi,yi}. Testing submodularity was first studied by Parnas, Ron & Rubinfeld (2003) for functions over rectangles. Seshadhri & Vondra ́k (2011) initiated the study of submodularity testing for functions over the boolean hypercube and, in particular, showed that testing submodularity is at least as difficult as testing monotonicity. Specifically, they established the following result. Lemma 4.3 (Seshadhri & Vondra ́k 2011). Given the function f : {0, 1}n → R, there exists a function g : {0, 1}n+1 → R with the following properties: (i) If f is monotone, then g is submodular. (ii) If f is ε-far from monotone, then g is ε -far from submodular. 2 (iii) For each x ∈ {0, 1}n+1, the value of g(x) can be determined with 2 queries to f. Combining the lemma with the lower bound of Fischer et al. (2002) on testing monotonicity yields a lower bound of Ω(logn) Property Testing Lower Bounds 31 queries for testing submodularity non-adaptively. This implies a weak lower bound of Ω(log log n) queries for general (i.e., adaptive) submodularity testers. Combining Lemma 4.3 with Theorem 1.6 instead, we get a stronger lower bound. Corollary 1.7 (Restated). Testing f : {0, 1}n → R for submod- ularity requires Ω(n) queries. Proof. Consider the task of testing whether f : {0, 1}n−1 → R is monotone. Let g : {0,1}n → R be the corresponding function whose existence is guaranteed by Lemma 4.3. We can test whether f is monotone by simulating a submodularity tester T on g. If T makes q queries, the resulting monotonicity tester makes a total of 2q queries. By Theorem 1.6, all monotonicity testers must make at least Ω(n) queries, so our submodularity tester must also make q = Ω(n) queries. 􏰮 5. Testing Concise Representations We begin with formal definitions for decision trees and branching programs. Definition 5.1 (Decision tree). A decision tree is a directed bi- nary tree in which each internal node is labelled with some element from [n], the two edges going out of an internal node are labelled with 0 and 1, and each leaf node has a label from {0, 1}. The deci- sion tree D computes the function f : {0, 1}n → {0, 1} if for every x ∈ {0,1}n, the path defined in D by querying the value of xi at each internal node labelled with i and following the corresponding edge leads to a leaf node with value f(x). The size of a decision tree is the total number of leaves it contains. Definition 5.2 (Branching program). A branching program is a directed acyclic graph with two sink nodes labelled with 0 and 1, respectively, and where all other nodes have out-degree 2. Each non-sink node has a label from [n] and the two edges leaving a node are labelled with 0 and 1, respectively. The branching program P computes the function f : {0, 1}n → {0, 1} if each x ∈ {0, 1}n 32 Blais, Brody & Matulef defines a path in the branching program that leads to the sink labelled with f(x). The size of a branching program is the total number of nodes it contains. The proof of Theorem 1.8 relies on the following two simple lemmas. Lemma 5.3. Fixs≥1and0<α<1. Letf :{0,1}n →{0,1}be an s-linear function. Then f can be computed by a decision tree of size 2s and is 1−α -far from all functions that are computable by 2 decision trees of size at most α 2s. Proof. To construct a decision tree of size 2s that computes the function f : x 􏰶→ xi1 ⊕ ··· ⊕ xis, create a complete tree of depth s where each node at level j of the tree queries xij . This tree has 2s leaves and, by setting the value of each leaf appropriately, computes the function f exactly. Consider now a decision tree T of size at most α2s, and let g : {0,1}n → {0,1} be the function computed by this tree. We want to show that Pr[f(x) ̸= g(x)] ≥ 1−α when the probability is 2 over the uniform distribution of x ∈ {0,1}n. For each leaf l of T, let depth(l) denote the number of unique variables queried by the nodes in the path from the root of T to l and let Rl ⊆ {0,1}n represent the set of inputs x ∈ {0,1}n that define a path in T that reaches l. (Note that the sets Rl form a partition of {0, 1}n.) Define B := 􏰒l : depth(l) 0. The lower bound of Chockler & Gutfreund (2004) gives a lower bound of Ω(k/t) queries for this task. (See also (Diakonikolas et al. 2007, App. E).) This bound is not sufficiently strong to answer Fischer et al.’s question for any t = ω(1).
√
The following result shows that for any t ≤ O( k), the task
of distinguishing k-juntas from functions that are far from (k + t)- juntas requires (asymptotically) as many queries as the standard k-junta testing problem.
Theorem 1.9 (Restated). Fix k ≤ n and t > 0. Any algorithm 2
that accepts k-juntas and rejects functions far from (k + t − 2)- juntas with high probability must make Ω􏰃 min{(k )2, k}􏰄 queries.
t
Proof. We prove the theorem with a reduction from the ex-
tended Gap Hamming Distance problem. If t = Ω(k), there is
nothing to prove. Otherwise, suppose t = o(k), and let C(k,t)-junta ⊕
be the communication game where Alice and Bob receive the func- tions f, g : {0, 1}n → {0, 1} and must distinguish between the case where h = f ⊕g is a k-junta from the case where h is far from (k + t − 2)-juntas. By Lemma 2.4 and 2.10 and the fact that k + t/2 = Θ(k), we have
2 Q􏰃(k, t)-junta􏰄 ≥ R(C(k,t)-junta) ⊕
and
To complete the proof, we want to show that R(C(k,t)-junta) ≥
R(eghdn,2k+t, t ). 2
R(eghdn,k+ t , t ) = Ω􏰃 min{(k )2, k}􏰄 . 22t
Let x and y be the strings received by Alice and Bob, respec- tively, as input to an instance of the eghdn,k+ t , t problem. Alice
22
and Bob then construct the functions ParityA, ParityB : {0, 1}n → {0,1},whereA:={i:xi =1}andB:={i:yi =1}. Thefunc- tion h = ParityA ⊕ ParityB = ParityA△B is |A△B|-linear. When ∆(x, y) = |A△B| ≤ k + t/2 − t/2 = k, the function h is a k-parity
⊕