Nadya Voronova
CAS CS 591 B: Communication Complexity
Lecture Notes 22:
Property Testing and Communication Complexity
Fall 2019
Talk based on the paper “Property testing lower bounds via communication complexity” by Eric Blais, Joshua Brody, and Kevin Matulef.
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 – instance a graph on n nodes, a function on n variables, a string of numbers, an image, etc. In a typical property testing setup, a tester who has unbounded computational 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.
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 theory (Ron 2008). Over the last two decades, researchers have exerted a considerable amount of effort to determine the query complexity of 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),
• whether f is a monotone function (Fischer et al. 2002; Goldreich et al. 2000),
• whether f is a dictator (Parnas et al. 2002), etc.
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 properties 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 and the communication complexity technique that we’re going to discuss.
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 communi- cating players), both involve algorithms which are restricted by the parties’ limited access to their input and both are interested in the amount of the “information” parties exchange.
We will show that there is indeed a strong connection between testing and communication complexity. More specifically, we will show how to reduce certain communication problems to property testing problems. This reduction method represents an approach to proving testing lower bounds.
1
1 Property testing model
For functions f,g : {0,1}n → R where R ⊆ CC let distance between those functions dist(f,g) be the fraction of inputs x ∈ {0, 1}n for which f (x) ̸= g(x).
Definition 1. A property P of the functions {0, 1}n → R is a subset of those functions. The distance between function f : {0, 1}n → R and a property P is ming∈P dist(f, g). When dist(f, P) ≥ ε, we say that f is ε-far from the property, otherwise it’s ε-close.
Definition 2. An (ε, q)-tester for a property P of a function {0, 1}n → R is a randomized algorithm that has query access to the input f : {0, 1}n → R, makes at most q queries and
• Accepts f with probability at least 2 if f ∈ P 3
• Rejects f with probability at least 2 if f is ε-far from P 3
Definition 3. A tester is called nonadaptive if it can select its q queries before observing the value of f on any of those queries. Otherwise, it’s called adaptive.
Definition 4. A tester that always accepts any function from P has 1-sided error. Otherwise, it has 2-sided error.
We’re going to denote the query complexity of the property P as Qε(P) where Qε(P) is the minimum value of q for which P has (ε, q)-tester. Similarly, Q1(P) and Qna(P) denote the minimum
number of queries required to ε-test the property P with one-sided error and nonadaptive testers, respectively.
Thought this talk, we will assume that ε is a small fixed constant. 2 Main reduction lemma
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. These communi- cation games are based on what we call combining operators.
Definition 5. 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. A combining operator ψ 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).
For example, when the base functions are boolean, the combining 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∈Bx [f (y) · g(y)], where Bx is a Hamming ball centered at x of radius 1, is not simple, since computing h(x) requires knowledge of f(y) and g(y) for several y.
Given a combining operator ψ and a property P, we define CψP to be the following property testing communication game. Alice receives a function f. Bob receives a function g. They need to compute
1 if ψ(f, g) ∈ P
CψP = 0 if ψ(f,g) is ε-far from P
2
εε
We prove all of our testing lower bounds by reducing from an associated communication game CψP . This reduction is simple – Alice and Bob solve CψP by emulating a testing algorithm for P on h = ψ(f,g). Note that neither Alice nor Bob have enough information to evaluate a query h(x), because h depends on both f and g. Instead, they must communicate to jointly compute h(x).
Lemma 6 (Main reduction lemma). Let Z to be a finite set. For any simple combining operator ψ on functions f, g : {0, 1}n → Z and any property over {0, 1}n → R, we have
1. BPP(CψP)≤2Q(P)·⌈log|Z|⌉
2. coRP(CψP)≤2Q1(P)·⌈log|Z|⌉
3. BPP→(CψP)≤Qna(P)·⌈log|Z|⌉
4. coRP→(CψP)≤Qna,1(P)·⌈log|Z|⌉
where coRP(t) denotes protocols that compute t(x, y) with certainty if t(x, y) = 1 and with proba-
bility at least 2 when t(x, y) = 0, and BPP→, coRP→ denotes one-way communication protocols. 3
All of the protocols have error ≤ 1. 3
Proof. We begin by proving (3). Let A be an optimal q-query nonadaptive tester for P. Let’s create a one-way protocol for CψP using A. Firstly, Alice and Bob generate queries x1, . . . xq using public randomness. Then, Alice computes f (x1 ) . . . f (xq ) and sends them to Bob using q · ⌈log |Z |⌉ bits. For each i Bob computes g(xi) and combines it with f(xi) to compute h(xi). Finally, Bob emulates A using h(x1) . . . h(xq) and outputs 1 iff A accepts h.
If A has two-sided error then by the correctness of A, protocol computes CψP with probability at least 2. Hence,BPP→(CP)≤q·⌈log|Z|⌉=Qna(P)·⌈log|Z|⌉,whichprovesproposition(3).
3ψ
If A has one-sided error then whenever h ∈ P the protocol correctly outputs 1, and when h is
ε-far from P the protocol correctly outputs 0 with probability at least 2. Therefore, coRP→(CP) ≤ 3ψ
q · ⌈log |Z|⌉ = Qna,1(P) · ⌈log |Z|⌉, as we wanted in (4).
Now, suppose A is an optimal q-query adaptive tester for P. Again, Alice and Bob will use public
randomness to generate queries, but this time they will do it one at a time since A is adaptive. Each time xi is generated, Alice and Bob exchange f(xi) and g(xi), which is enough information for Alice and Bob to individually compute h(xi) because ψ is simple, which gives them enough information to generate the next query with the appropriate distribution (which depends on previous queries). When h(x1) . . . h(xq) have all been computed, Alice and Bob output 1 iff A accepts h. This protocol costs 2q · ⌈log |Z|⌉ bits of communication and thus coRP(CψP ) ≤ 2q · ⌈log |Z|⌉ = 2Q1(P) · ⌈log |Z|⌉, which proves proposition (1).
Similarly, if A is an optimal adaptive tester with one-sided error then coRP(CψP) ≤ 2Q1(P) · ⌈log |Z|⌉, which proves proposition (2).
3 Lower bounds
Now we can prove some lower bounds for a number of properties that we define below. Definition 7. The function f : {0, 1}n → {0, 1} is linear if there exists S ⊆ [n] such that for every
x ∈ {0,1}n, f(x) = i∈S xi. When |S| = k, we say that f is a k-linear function. 3
Definition 8. The function f : {0,1}n → {0,1} is k-junta if there is a set J ⊆ [n], |J| ≤ k such that for every x,y ∈ {0,1}n such that xj = yj for every j ∈ J we have f(x) = f(y).
Definition 9. For convenience when discussing 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 →
ˆ i∈S xi {−1,1} has a unique representation of form f(x) = S⊆[n] f(S)χS(x), where χS(x) = (−1)
ˆˆ
and 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 f(S) ̸= 0 for some S of size k.
We are interested in functions that have Fourier degree at most k.
Definition 10. Every boolean function f : {0, 1}n → {0, 1} also has a unique representation as a polynomial over GF(2), where ⊕ is used as an addition operation, and logical AND is used as a multiplication operation. We say that f is a k-sparse polynomial if its representation over GF(2) has at most k terms.
One useful fact is true for all of these properties.
Proposition 11. Fix n > 2 and 1 ≤ k ≤ n − 2. If f : {0, 1}n → {0, 1} is (k + 2)-linear, then f is
1. 1-far from k-linear functions,
2
2. 1-far from k-juntas, 2
3. 1-far from functions of Fourier degree at most k, 2
4. 1 -far from k-sparse polynomial. 20
To prove lower bounds on the communication games associated with these properties, we will
reduce to a balanced version of disjointness called k-balanced-DISJ. In this version, Alice receives
a set A ⊆ [n] of size |A| = ⌊k ⌋ + 1, Bob receives a set B ⊆ [n] of size |B| = ⌈k ⌉ + 1, and there is a 22
promise that |A ∩ B| ≤ 1.
Lemma 12. For all 0 ≤ k ≤ n − 2
BPP(k-balanced-DISJn) = Ω(min{k, n − k})
One can find proofs of proposition 11 and lemma 12 in the original paper.
Now we can prove lower bounds on query the complexity of k-linearity and other properties mentioned above. To do this we’re doing to show that if query complexity of these properties are small then we can solve k-balanced-DISJ easier than lemma 12 states because we will provide the protocol for k-balanced-DISJ using an optimal tester for one of properties above.
Theorem 13. Fix 1 < k < n − 1. Then, at least Ω(min{k, n − k}) queries are required to test, if function f : {0, 1}n → {0, 1}
1. is k-linear,
2. is k-junta,
3. is a function of Fourier degree at most k,
4
4. has a k-sparse representation in GF(2). Proof. By Lemma 6
2Q(k-linear) ≥ BPP(Ck-linear) ⊕
where Ck-linear by definition 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. By Lemma 12
BPP(k-balanced-DISJ) = Ω(min{k, n − k})
To complete the proof of (1), we show that BPP(Ck-linear) ≥ BPP(k-balanced-DISJ) with a
reduction from k-balanced-DISJ to Ck-linear. ⊕
Let A,B ⊆ [n] be the two sets of size |A| = ⌊k⌋+1 and |B| = ⌈k⌉+1 received by Alice and 22
Bob as their inputs in k-balanced-DISJ.
Define ParityS = i∈S xi. Alice and Bob can construct the functions ParityA, ParityB :
{0, 1}n → {0, 1}. When |A ∩ B| = 1 the symmetric difference of two input sets has size |A∆B| =
|A|+|B|−2|A∩B| = k and ParityA ⊕ParityB = ParityA∆B is k-linear. When A and B are disjoint,
the function Parity ⊕ Parity is k + 2-linear function and by proposition 11, is 1 -far from k-linear AB2
functions. So Alice and Bob can solve their instance of k-balanced-DISJ using a communication protocol for Ck-linear. This implies BPP(Ck-linear) ≥ BPP(k-balanced-DISJ), as we wanted.
⊕
⊕⊕
The same reduction works for lower bounds for testing the other properties. Let Ck-junta denote ⊕
the communication game where Alice and Bob receive boolean functions f,g and must decide if h = f ⊕g is k-junta. Similarly, Cdegree-k and Ck-sparse denote communication games where Alice and
⊕⊕
Bob need to decide if h = f ⊕ g has Fourier degree at most k or can be represented by a k-sparse GF(2) polynomial.
By proposition 11, (k+2)-linear function is 1-far from k-junta, 1-far from functions with Fourier 22
degree at most k, and 1 -far from k-sparse polynomials. And k-linear function is k-junta, has Fourier 20
degree at most k, and can be represented by a k-sparse GF(2) polynomial, so we can conclude that BPP(k-balanced-DISJ) ≤ min{BPP(Ck-junta), BPP(Cdegree-k), BPP(Ck-sparse)}
Thus,
⊕⊕⊕
BPP(Ck-linear) ≥ BPP(k-balanced-DISJ) = Ω(min{k, n − k}), ⊕
BPP(Ck-junta) ≥ BPP(k-balanced-DISJ) = Ω(min{k, n − k}), ⊕
BPP(Cdegree-k) ≥ BPP(k-balanced-DISJ) = Ω(min{k, n − k}), ⊕
BPP(Ck-sparse) ≥ BPP(k-balanced-DISJ) = Ω(min{k, n − k}). ⊕
5