Authors Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99
www.theoryofcomputing.org
Testing Linear-Invariant
Non-Linear Properties
Arnab Bhattacharyya∗ Victor Chen† Madhu Sudan‡ Ning Xie§
Received: September 18, 2009; published: March 29, 2011.
Abstract: We consider the task of testing properties of Boolean functions that are invariant
under linear transformations of the Boolean cube. Previous work in property testing,
including the linearity test and the test for Reed-Muller codes, has mostly focused on such
tasks for linear properties. The one exception is a test due to Green for “triangle freeness”: a
function f : Fn2 → {0, 1} has this property if f (x), f (y), f (x + y) do not all equal 1, for any
pair x, y ∈ Fn2 .
Here we extend this test to a more systematic study of testing for linear-invariant non-
linear properties. We consider properties that are described by a single forbidden pattern
(and its linear transformations), i. e., a property is given by k points v1 , . . . , vk ∈ Fk2 and
f : Fn2 → {0, 1} has the property that if for all linear maps L : Fk2 → Fn2 it is the case that
f (L(v1 )), . . . , f (L(vk )) do not all equal 1. We show that this property is testable if the
underlying matroid specified by v1 , . . . , vk is a graphic matroid. This extends Green’s result
to an infinite class of new properties. Part of our main results was obtained independently
by Král’, Serra, and Venna [Journal of Combinatorial Theory Series A, 116 (2009), pp.
971–978].
∗ Supported in part by a DOE Computational Science Graduate Fellowship and by NSF grants 0514771, 0732334, and
0728645.
† Supported in part by NSF Award CCR-0514915.
‡ Supported in part by NSF Award CCR-0514915.
§ Supported in part by an Akamai Presidential Fellowship and NSF grant 0514771.
ACM Classification: F.2.2
AMS Classification: 68W20, 68Q25
Key words and phrases: property testing, Fourier analysis
2011 Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2011.v007a006
A RNAB B HATTACHARYYA , V ICTOR C HEN , M ADHU S UDAN AND N ING X IE
Our techniques extend those of Green and in particular we establish a link between the
notion of “1-complexity linear systems” of Green and Tao, and graphic matroids, to derive
the results.
1 Introduction
Property testing considers the task of testing, “super-efficiently,” if a function f : D → R mapping a finite
domain D to a finite range R essentially possesses some desirable property. Letting {D → R} denote the
set of all functions from D to R, a property is formally specified by a family F ⊆ {D → R} of functions.
A tester has oracle access to the function f and should accept with high probability (this probability is
called the completeness of the tester) if f ∈ F and reject also with high probability (this probability is
called the soundness of the tester) functions that are far from F, while making very few queries to the
oracle for f . Here, distance between functions f , g : D → R, denoted δ ( f , g), is simply the probability
that f (x) 6= g(x) when x is chosen uniformly at random from D and δ ( f , F) = ming∈F {δ ( f , g)}. We
say f is δ -far from F if δ ( f , F) ≥ δ and δ -close otherwise. The central parameter associated with a
tester is the number of oracle queries it makes to the function f being tested. In particular, a property is
called (locally) testable if there is a tester with query complexity that is a constant depending only on the
distance parameter δ . Property testing was initiated by the works of Blum, Luby and Rubinfeld [16] and
Babai, Fortnow and Lund [9] and was formally defined by Rubinfeld and Sudan [30]. The systematic
exploration of property testing was initiated by Goldreich, Goldwasser, and Ron [19] who expanded
the scope of property testing to combinatorial and graph-theoretic properties (all previously considered
properties were algebraic). In the subsequent years, a rich collection of properties have been shown to
be testable [5, 4, 1, 17, 29, 3, 2, 25, 24] and many property tests have ended up playing a crucial role in
constructions of probabilistically checkable proofs [8, 7, 11, 23, 31].
The rich collection of successes in property testing raises a natural question: Why are so many
different properties turning out to be locally testable? Are there some broad “features” of properties
that make them amenable to such tests? Our work is part of an attempt to answer such questions. Such
questions are best understood by laying out broad (infinite) classes of properties (hopefully some of them
are new) and showing them to be testable (or characterizing the testable properties within the class). In
this paper we introduce a new such class of properties, and show that (1) they are locally testable, and (2)
that they contain infinitely many new properties that were not previously known to be testable.
The properties, and our results The broad scope of properties we are interested in are properties
that view their domain D as a vector space and are invariant under linear transformations of the domain.
Specifically, we consider the domain D = Fn2 , the vector space of n-dimensional Boolean vectors, and
the range R = {0, 1}. In this setting, a property F is said to be linear-invariant if for every f ∈ F and
linear map L : Fn2 → Fn2 we have that f ◦ L ∈ F. Specific examples of linear-invariant properties that
were previously studied (especially in the Boolean setting) include that of linearity, studied by Blum et
al. [16] and Bellare et al. [10], and the property of being a “moderate-degree” polynomial (also known
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 76
T ESTING L INEAR -I NVARIANT N ON -L INEAR P ROPERTIES
as a Reed-Muller codeword) studied by Alon et al. [2].1 While the tests in the above-mentioned works
potentially used all features of the property being tested, Kaufman and Sudan [26] showed that the
testability can be attributed principally to the linear-invariance of the property. However their setting only
considers linear properties, i. e., F itself is a vector space over {0, 1} and this feature plays a key role in
their results: It lends an algebraic flavor to all the properties being tested and plays a central role in their
analysis.
We thus ask the question: Is linear-invariance sufficient2 to imply testability, even if the property
being tested is non-linear? The one previous work in the literature that gave examples of non-linear linear-
invariant properties is Green [21] where a test for the property of being “triangle-free” was described.
A function f : Fn2 → {0, 1} is said to be triangle-free if for every x, y ∈ Fn2 it is the case that at least
one of f (x), f (y), f (x + y) does not equal 1. The property of being triangle-free is easily seen to be
linear-invariant and yet not linear. Green [21] showed that the natural test for this property does indeed
work correctly, though the analysis is quite different from that of typical algebraic tests and is more
reminiscent of graph-property testing. In particular, Green develops an algebraic regularity lemma to
analyze this test. (We note that the example above is not the principal objective of Green’s work, which
is directed mostly at abelian groups D and R. The above example with D = Fn2 and R = {0, 1} is used
mainly as a motivating example.)
Motivated by the above example, we consider a broad class of properties that are linear-invariant
and non-linear. A property in our class is given by k vectors v1 , . . . , vk in the k-dimensional space
Fk2 . (Throughout this paper we think of k as a constant.) These k vectors uniformly specify a family
F = Fn;v1 ,...,vk for every positive integer n, containing all functions that, for every linear map L : Fk2 → Fn2
take on the value 0 on at least one of the points L(v1 ), . . . , L(vk ). (In Section 6 we consider an even
more generalized class of properties where the forbidden pattern of values for f is not 1k but some other
string and show a limited set of cases where we can test such properties.) To see that this extends the
triangle-freeness property, note that triangle-freeness is just the special case with k = 3 and v1 = h100i,
v2 = h010i, v3 = h110i. Under different linear transforms, these three points get mapped to all the
different triples of the form x, y, x + y and so Fn;v1 ,v2 ,v3 equals the class of triangle-free functions.
Before giving a name to our class of functions, we make a quick observation. Note that the property
specified by v1 , . . . , vk is equivalent to the property specified by T (v1 ), . . . , T (vk ) where T is a non-singular
linear map from Fk2 to Fk2 . Thus the property is effectively specified by the dependencies among v1 , . . . , vk
which are in turn captured by the matroid3 underlying v1 , . . . , vk . This leads us to our nomenclature:
Definition 1.1 (M-freeness). Given a (binary, linear) matroid M represented by vectors v1 , . . . , vk ∈ Fk2 ,
the property of being M-free is given by, for every positive integer n, the family
FM = { f : Fn2 → {0, 1} | ∀ linear L : Fk2 → Fn2 , h f (L(v1 )), . . . , f (L(vk ))i 6= 1k }.
1 In the literature, the term “low-degree polynomial” is typically used for polynomials whose degree is smaller than the
order of the field. In the paper [2] the degrees considered are larger than the order of the field, but are best thought of as large
constants. The phrase “moderate-degree” above describes this setting of parameters.
2 Strictly speaking, here we implicitly assume that the property satisfies any other necessary conditions for testability, such as
being “locally characterized” [26].
3 For the sake of completeness we include a definition of matroids in Section 2.1. However, a reader unfamiliar with this
notion may just use the word “matroid” as a synonym for a finite collection of binary vectors, for the purposes of reading this
paper.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 77
A RNAB B HATTACHARYYA , V ICTOR C HEN , M ADHU S UDAN AND N ING X IE
The property of being M-free has a natural k-local test associated with it: Pick a random linear map
L : Fk2 → Fn2 and test that h f (L(v1 )), . . . , f (L(vk ))i 6= 1k . Analyzing this test turns out to be non-trivial,
and indeed we only manage to analyze this in special cases.
Recall that a matroid M = {v1 , . . . , vk }, vi ∈ Fk2 , forms a graphic matroid if there exists a graph G on
k edges with the edges being associated with the elements v1 , . . . , vk such that a set S ⊆ {v1 , . . . , vk } has a
linear dependency if and only if the associated set of edges contains a cycle. In this paper, we require that
the graph G be simple, that is, without any self-loops or parallel edges. Our main theorem shows that the
property F associated with a graphic matroid v1 , . . . , vk ∈ Fk2 is testable.
Theorem 1.2. For a graphic matroid M, the property of being M-free is locally testable. Specifically, let
M = {v1 , . . . , vk } be a graphic matroid. Then, there exists a function τ : R+ → R+ and a k-query tester
that accepts members of M-free functions with probability one and rejects functions that are ε-far from
being M-free with probability at least τ(ε).
Our bound on τ is quite weak. We let W (t) denote a tower of twos with height dte. Our proof only
guarantees that τ(ε) ≥ W (poly(1/ε))−1 , a rather fast vanishing function. We do not know if such a weak
bound is required for any property we consider.
We describe the techniques used to prove this theorem shortly (which shed light on why our bound on
τ is so weak) but first comment on the implications of the theorem. First, note that for a graphic matroid
it is more natural to associate the property with the underlying graph. We thus use the phrase G-free to
denote the property of being M-free where M is the graphic matroid of G. This terminology recovers
the notion of being triangle-free, as in [21], and extends to cover the case of being k-cycle free (also
considered in [21]). But it includes every other graph too!
For every integer k ≥ 3, let Ck denote the cycle graph with k vertices and let Kk denote the complete
graph on k vertices. Syntactically, Theorem 1.2 seems to include infinitely many new properties (other
than being k-cycle free). However, this may not be true semantically. For instance the property of being
triangle-free is essentially the same as being G-free for every G whose biconnected components are
triangles. Indeed, prior to our work, it was not even explicitly noted whether being Ck -free is essentially
different from being triangle-free. (By “essentially,” we ask if there exist triangle-free functions that are
far from being Ck -free.) It actually requires careful analysis to conclude that the family of properties
being tested includes (infinitely-many) new ones. Our second theorem addresses this point.
Theorem 1.3. The class of G-free properties include infinitely many distinct ones. In particular:
1. For every odd k, if f is Ck+2 -free, then it is also Ck -free. Conversely, there exist functions g that are
Ck -free but far from being Ck+2 -free.
2. If k ≤ ` and f is Kk -free, then it is also K` -free. On the other hand, if k ≥ 3 and ` ≥ 2k + 2 then
there exists a function g that is K` -free but far from being Kk -free.
Techniques Our proof of Theorem 1.2 is based on Green’s analysis of the triangle-free case [21]. To
analyze the triangle-free case, Green develops a “regularity” lemma for groups, which is analogous to
Szemerédi’s regularity lemma for graphs. In our setting, Green’s regularity lemma shows how, given
any function f : Fn2 → {0, 1}, one can find a subgroup H of Fn2 such that the restriction of f to almost all
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 78
T ESTING L INEAR -I NVARIANT N ON -L INEAR P ROPERTIES
cosets of H is “regular,” where “regularity” is defined based on the “Fourier coefficients” of f . (These
notions are made precise in Section 3.1.)
This lemma continues to play a central role in our work as well, but we need to work further on this.
In particular, a priori it is not clear how to use this lemma to analyze M-freeness for arbitrary matroids
M. To extract a large feasible class of matroids we use a notion from a work of Green and Tao [22] of
the complexity of a linear system (or matroids, as we refer to them). The “least complex” matroids have
complexity 1, and we show that the regularity lemma can be applied to all matroids of complexity 1 to
show that they are testable (see Section 3).
The notion of a 1-complex matroid is somewhat intricate, and a priori it may not even be clear that
this introduces new testable properties. We show (in Section 4) that these properties actually capture all
graphic matroids which is already promising. Yet this is not a definite proof of novelty, and so in Section 5
we investigate properties of graphic matroids and give some techniques to show that they are “essentially”
different. Our proofs show that if two (binary) matroids are not “homomorphically” equivalent (in a sense
that we define) then there is an essential difference between the properties represented by them.
Significance of problems/results We now return to the motivation for studying M-free properties. Our
interest in these families is mathematical. We are interested in broad classes of properties that are testable;
and invariance seems to be a central notion in explaining the testability of many interesting properties.
Indeed this was what led Kaufman and Sudan [26] to examine this notion explicitly in the context of
algebraic functions. They considered families that were linear-invariant and linear, and our work is
motivated by the quest to see if the latter part is essential.
In contrast to other combinatorial settings, linear-invariance counts on a (quantitatively) very restricted
collection of invariances. Indeed the set of linear transforms is only quasi-polynomially large in the
domain (which may be contrasted with the exponentially large set of invariances that need to hold for
graph-properties). So the ability to test properties based on this feature is mathematically interesting and
leads to the question: what kind of techniques are useful in these settings. Our work manages to highlight
some of those (in particular, Green’s regularity lemma).
Related work Král’, Serra and Venna in [28], independently of us, established a variant of Theorem 1.2
using completely different techniques. In our language, they demonstrated a direct reduction from testing
freeness of a graphic matroid in a function to testing freeness of a subgraph in a graph, at which point
they could apply a (colored) regularity lemma for graphs.
In the additive combinatorics community, subsequent to Green’s work [21], there has been a lot of
work developing better understanding of the regularity lemma and associated technology. In particular,
Bergelson, Tao and Ziegler [12, 33] have resolved the inverse conjecture for the Gowers norms over
finite fields. However, to the best of our knowledge, there does not yet exist in the literature a concrete
formulation of a regularity lemma with respect to higher-order Gowers norms over F2 , akin to Green’s
regularity lemma.
Subsequent Work Following our work, Shapira in [32] and Král’, Serra and Vena in [27] indepen-
dently extended the reduction in [28] to show that M-freeness for an arbitrary matroid M is testable,
resolving one of our main open questions. They achieved this by reducing the testing of M-freeness in
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 79
A RNAB B HATTACHARYYA , V ICTOR C HEN , M ADHU S UDAN AND N ING X IE
functions to testing whether a hypergraph is free from a fixed sub-hypergraph and then applying existing
powerful hypergraph regularity lemmas. We remark that our proofs are very differently styled from those
in [28], [27] and [32], and in particular, our view on invariance leads us to develop techniques which
show that syntactically different properties are indeed distinct. We are also naturally led to the study of
non-monotone properties (see Section 2.2) which were not investigated in these works.
More recent work has extended these aspects of our work. Bhattacharyya, Grigorescu and Shapira [15]
have shown that non-monotone matroid-freeness properties are testable when the matroid is restricted to
be of complexity 1. Interestingly, their proof uses arithmetic regularity lemmas, like Green [21] and us,
instead of reductions to hypergraph properties as in [28, 27, 32]. The question of removing the restriction
to matroids of complexity 1 for non-monotone properties remains open. Separately, Bhattacharyya,
Grigorescu, Nordström and Xie [14] have extended the hierarchy of syntactically distinct properties to
non-monotone matroid-freeness properties. Along the way, they demonstrate necessary and sufficient
combinatorial conditions that determine when two matroid-freeness properties are identical and when
they are far apart from each other, provided the matroids satisfy some structural conditions. Finally, Chen,
Sudan and Xie [18] have shown that one can use self-correction, instead of the regularity lemma, to prove
testability of some (non-monotone) matroid-freeness properties, thus dramatically improving the bounds
on the query complexity of these properties in terms of dependence on ε.
For a more detailed discussion on the relation of this paper to subsequent works, we refer the reader
to a report that we wrote recently [13].
Organization of this paper In the following section (Section 2) we provide some basic facts on
matroids and define a slightly broader class of properties that we can consider (including some non-
monotone properties). We also define the notion of 1-complexity matroids which forms a central tool
in our analysis of the tests. In Section 3 we show that for any 1-complexity matroid M, M-freeness
is testable. In Section 4 we show that graphic matroids are 1-complexity matroids. Theorem 1.2 thus
follows from the results of Sections 3 and 4. In Section 5 we prove that there are infinitely many distinct
properties among G-free properties. Section 6 and Section 7 are devoted to results on testing some
non-monotone properties as well as some “collapse” results showing that many non-monotone properties
collapse to some simple classes of functions. Finally Section 8 contains some concluding remarks.
2 Additional definitions, results, and overview of proofs
In this section, we first provide some additional definitions, then describe some further results that we
present in the paper and finally give an outline of proofs.
2.1 Matroids
For more background on matroid theory, we refer the reader to [35].
Definition 2.1 (Matroids). A matroid M is a finite set S (called ground set) and a collection F of subsets
of S (called independent sets) such that the followings hold:
1. 0/ ∈ F.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 80
T ESTING L INEAR -I NVARIANT N ON -L INEAR P ROPERTIES
2. If X ∈ F and Y ⊆ X, then Y ∈ F.
3. If X and Y are both in F with |X| = |Y | + 1, then there exists an x ∈ X \Y such that Y ∪ x ∈ F.
A subset of the ground set F that is not independent is called dependent. A maximal independent
set—that is, an independent set which becomes dependent on adding any element of F—is called a basis
for the matroid. The collection of bases of M is denoted by B(M).
A matroid M on a ground set S = {x1 , . . . , xk } is said to be linear if there exists a field F and vectors
v1 , . . . , vk ∈ Fk such that some subset { xi | i ∈ T } indexed by T ⊆ {1, . . . , k} is independent if and only if
the corresponding vectors { vi | i ∈ T } are linearly independent. A linear matroid is binary if F can be
chosen to be the field F2 of order 2.
Let G be a graph, let S be its set of edges E(G). For all X ⊆ E(G), let X ∈ F if and only if X does
not contain a cycle of G. Then F is the collection of independent sets of a matroid on S, called the cycle
matroid or graphic matroid of the graph G and denoted by M(G). Graphic matroids are binary; for
example, if M is the graphic matroid of a graph G and I is the incidence matrix with rows indexed by
edges of G and columns indexed by vertices of G, then the rows of I form a set of vectors that represent
M over {0, 1}.
If M is a finite matroid, then we define the dual matroid M∗ by taking the same ground set and calling
a set a basis in M∗ if and only if its complement is a basis in M. It can be easily verified that M∗ is indeed
a matroid and that the dual of M∗ is M. A matroid M is called a cographic matroid if its dual matroid
M∗ is graphic.
2.2 Extensions to non-monotone families
We now generalize Definition 1.1 to a wider collection of forbidden patterns.
Definition 2.2 (M-freeness). Given Σ ∈ Fk2 and a binary matroid M represented by vectors v1 , . . . , vk ∈ Fk2 ,
the property of being (M, Σ)-free is given by, for every positive n, the family
F(M,Σ) = { f : Fn2 → {0, 1} | ∀ linear L : Fk2 → Fn2 , h f (L(v1 )), . . . , f (L(vk ))i 6= Σ} .
If for some linear L : Fk2 → Fn2 , h f (L(v1 )), . . . , f (L(vk ))i = Σ, then we say f contains (M, Σ) at L.
Also, to be consistent with Definition 1.1, we suppress mention of Σ when Σ = 1k .
Recall that a property P ⊆ {D → {0, 1}} is said to be monotone if f ∈ P and g ≺ f implies g ∈ P,
where g ≺ f means that g(x) ≤ f (x) for all x ∈ D.
Observation 2.3. For a binary matroid M, (M, Σ)-freeness is a monotone property if and only if Σ = 1k .
In addition to our main results (Theorems 1.2 and 1.3) on monotone properties, we also obtain local
testability results for a limited class of non-monotone properties.
Theorem 2.4. Let Ck denote the cycle on k vertices and let Σ be an arbitrary element of Fk2 . Then there
exists a function τ : R+ → R+ and a k-query tester that accepts members of F(Ck ,Σ) with probability 1
and rejects f that are ε-far from F(Ck ,Σ) with probability at least τ(ε).
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 81
A RNAB B HATTACHARYYA , V ICTOR C HEN , M ADHU S UDAN AND N ING X IE
However, in sharp contrast to Theorem 1.3, we show that, unless Σ equals 0k or 1k , the class of
(Ck , Σ)-freeness properties is not at all very rich semantically.
Theorem 2.5. The class of properties { F(Ck ,Σ) | k ≥ 3, Σ 6= 0k , Σ 6= 1k } is only finitely large.
The goal of Theorem 2.4 is not to introduce new testable properties but rather to illustrate possible
techniques for analyzing local tests that may lead to more classes of testable non-monotone properties.
2.3 Overview of proofs
We now give an outline of the proofs of our main theorems (Theorems 1.2 and 1.3), and also the extensions
(Theorems 2.4 and 2.5).
Our claim in Theorem 1.2, that graphic matroid freeness properties are locally testable, is based on
analyzing the structure of dependencies among elements of a graphic matroid. To this end, we first recall
the classification of linear forms due to Green and Tao [22]. We require a minor modification of their
definition since, for us, the structure of the linear constraints is described by elements of a matroid.
Definition 2.6 (Complexity). Given a binary matroid M represented by v1 , . . . , vk ∈ Fk2 , we say that M
has complexity c at coordinate i if we can partition {v j } j∈[k]\{i} into c + 1 classes such that vi is not in
the span of any of the classes. We say that M has complexity c if c is the minimum such that M has
complexity c at coordinate i for all i ∈ [k].
To avoid triviality, we will consider in this paper only matroids whose complexities are greater
than zero. This is because a matroid M has complexity 0 if and only if M consists of a set of linearly
independent vectors. It follows that the all-zero function is the only function that is M-free.
The above definition makes sense because the span of a set of elements is not dependent on the specific
basis chosen to represent the matroid. As a motivating example, consider the graphic matroid of Ck
studied by Green [21]. It can be represented by v1 = e1 , v2 = e2 , . . . , vk−1 = ek−1 and vk = e1 + · · · + ek−1 .
We see then that the graphic matroid of Ck has complexity 1 because for every i < k, the rest of the
matroid elements can be partitioned into two sets {e j } j6=i and ∑ j∈[k] e j such that vi is not contained in
the span of either set, and for i = k, any nontrivial partition of the remaining elements ensures that vk
does not lie in the span of either partition. In Section 4, we extend this observation about Ck to all graphs.
Lemma 2.7. For all graphs G, the graphic matroid of G has complexity 1.
Green and Tao [22] showed that if a matroid M has complexity c and if A is a subset of Fn2 , then
the number of linear maps L : Fk2 → Fn2 such that L(vi ) ∈ A for all i ∈ [k] is controlled by the (c + 1)th
Gowers uniformity norm of A. Previously, Green [21] proved an arithmetic regularity lemma, which
essentially states that any set A ⊆ Fn2 can be partitioned into subsets of affine subspaces such that nearly
every partition is nearly uniform with respect to linear tests. We show in Section 3 how to combine these
two results to obtain the following:
Lemma 2.8. Given any binary matroid M represented by v1 , . . . , vk ∈ Fk2 , if M has complexity 1, then
there exists a function τ : R+ → R+ and a k-query tester that accepts members of FM with probability 1
and rejects f that are ε-far from FM with probability at least τ(ε), where τ(ε) ≥ 1/W (poly(1/ε)).
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 82
T ESTING L INEAR -I NVARIANT N ON -L INEAR P ROPERTIES
Theorem 1.2 directly follows from combining Lemma 2.7 and Lemma 2.8. In fact, Lemma 2.8
implies testability of all matroids that have complexity 1, not only those that are graphic. In Section 4, we
give examples of binary matroids that have complexity 1 and yet are provably not graphic.
Theorem 1.3 provides a proper hierarchy among the graphical properties. Moreover, the containments
P1 ( P2 in this hierarchy are shown to be “statistically proper” in the sense that we demonstrate functions
f that are ε-far from P1 but are in P2 . The theorem implies the following hierarchy:
· · · ( Ck+2 -free ( Ck -free ( · · · ( C3 -free = K3 -free ( · · · ( Kk -free ( K(k)+2 -free ( · · ·
2
Thus, the class of properties FG does indeed contain infinitely many more properties than the cycle
freeness properties considered by Green [21].
Both the hierarchy among the cyclic freeness properties and among the clique freeness properties
are derived in Section 5 using a general technique. In order to show a statistically proper containment
M1 -free ( M2 -free, we construct a function f that, by its definition, contains M1 at a large number of
linear maps and so is far from being M1 -free. On the other hand, the construction ensures that if f is also
not M2 -free, then there is a matroid homomorphism from M2 to M1 . We define a matroid homomorphism
from a binary matroid M2 to a binary matroid M1 to be a map from the ground set of M2 to the ground
set of M1 which maps cycles to cycles. The separation between M2 -freeness and M1 -freeness is then
obtained by proving that there do not exist any matroid homomorphisms from M2 to M1 . This proof
framework suffices for both the claims in Theorem 1.3 and is reminiscent of proof techniques involving
graph homomorphisms in the area of graph property testing (see [6] for a survey).
Theorem 2.4 is the result of a more involved application of the regularity lemma. To deal with
non-monotone properties, we employ a different “rounding” scheme inspired by the testability of non-
monotone graph properties in [1]. Unlike Szemerédi’s regularity lemma, a “strong form” of the arithmetic
regularity lemma is not known, so we restrict our attention to cyclic matroids and exploit the additive
structure of the pattern. Theorem 2.5 is based on a characterization theorem in Section 7 that classifies
(Ck , Σ)-freeness properties into 9 classes when Σ 6= 0k , 1k .
3 Freeness of complexity 1 matroids is testable
In this section we prove Lemma 2.8. Before doing so, we fix our notation and provide a quick background
on Fourier analysis. We will be working with abelian groups with additive notation. If H is a subgroup of
G, the cosets of H are indicated by g+H, with g ∈ G chosen to represent that coset. Let fg+H : H → {0, 1}
denote f restricted to the coset g + H, defined by sending h to f (g + h); that is, for every h ∈ H, g ∈ G,
fg+H (h) := f (g + h). For σ ∈ {0, 1}, we define µσ ( fg+H ) := Prh∈H [ fg+H (h) = σ ] to be the density of σ
in f restricted to coset g + H.
3.1 Fourier analysis and Green’s regularity lemma
Definition 3.1 (Fourier Transform). If f : Fn2 → {0, 1}, then we define its Fourier transform fb : Fn2 → R
to be fb(α) = Ex∈Fn2 f (x)χα (x), where χα (x) = (−1)∑i∈[n] αi xi . fb(α) is called the Fourier coefficient of f
at α, and the {χα }α are the characters of Fn2 .
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 83
A RNAB B HATTACHARYYA , V ICTOR C HEN , M ADHU S UDAN AND N ING X IE
It is easy to see that for α, β ∈ Fn2 , E χα · χβ is 1 if α = β and 0 otherwise. Since there are 2n
characters, the characters form an orthonormal basis for functions on Fn2 , and we have the Fourier
inversion formula
f (x) = ∑ fb(α)χα (x)
α∈Fn2
and Parseval’s identity
∑ fb(α)2 = Ex f (x)2 .
α∈Fn2
We extend Definition 3.1 to functions f : H → {0, 1} where H is a subgroup of Fn2 , by using the fact that
H is isomorphic to Fm 2 for some m ≤ n and applying Definition 3.1 relative to this isomorphism.
Next we turn to Green’s arithmetic regularity lemma, the crux of the analysis of our local testing
algorithm. Green’s regularity lemma over Fn2 is a structural theorem for Boolean functions. It asserts
that for every Boolean function, there is some decomposition of the Hamming cube into cosets, such
that the function restricted to most of these cosets are uniform and pseudorandom with respect to the
linear functions. An alternate and equivalent way is that no matter where we cut the Boolean cube by a
hyperplane, the densities of f on the two halves of the cube separated by the hyperplane do not differ
greatly. Formally, we say that a function is uniform if all of its nonzero Fourier coefficients are small.
Definition 3.2 (Uniformity). For every 0 < ε < 1, we say that a function f : Fn2 → {0, 1} is ε-uniform if
for every α 6= 0 ∈ Fn , fb(α) ≤ ε.
2
Recall that we let W (t) denote a tower of twos with height dte. To obtain a partition of the Hamming
cube that satisfies the required uniformity requirement, the number of cosets in the partition may be rather
large. More precisely,
Lemma 3.3 (Green’s Regularity Lemma). Let f : Fn2 → {0, 1}. For every 0 < ε < 1, there exists a
subspace H of G = Fn2 of co-dimension at most W (ε −3 ), such that Prg∈G [ fg+H is ε-uniform] ≥ 1 − ε.
3.2 Testability of complexity 1 matroid freeness
The proposition below was proved in [22]. Collectively, statements capturing the phenomenon that expec-
tation over certain forms are controlled by varying degrees of the Gowers norm are termed generalized
von-Neumann type theorems in the additive combinatorics literature. In particular, as we only require
the degree 2 Gowers norm of a function, which is equivalent to the `4 norm of the function’s Fourier
transform. The version we state here requires the functions fi to be over Fn2 and possibly distinct; however
as explained by Gowers and Wolf [20], both conditions can be easily satisfied.
Proposition 3.4 (implicit in [22]). Suppose a binary matroid M = {v1 . . . , vk } has complexity 1 and let
f1 , . . . , fk : Fn2 → {0, 1}. Then
" # !1/4
k
4
E
L:Fk2 →Fn2
∏ fi (L(vi )) ≤ min
i∈[k]
∑ fbi (α) .
i=1 α∈Fn2
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 84
T ESTING L INEAR -I NVARIANT N ON -L INEAR P ROPERTIES
It is an easy deduction from Proposition 3.4 to see that if f is uniform, then the number of linear
maps L where f has a M-pattern is close to E[ f ]m N d , where N = 2n . Combining this observation with
the regularity lemma, we prove Lemma 2.8.
Proof of Lemma 2.8. Consider a test that picks a linear map L uniformly at random from all linear maps
from Fk2 → Fn2 and rejects iff for all i ∈ [k], f (L(vi )) = 1. Clearly the test has completeness one.
Now we analyze the soundness of this test. Suppose f is ε-far from being M-free. We want to show
that the test rejects with probability at least τ(ε), such that τ(ε) > 0 whenever τ > 0. Let a(ε) and b(ε)
be two functions of ε that satisfy the constraint a(ε) + b(ε) < ε, we shall specify these two functions
at the end of the proof. We now apply Lemma 3.3 to f to obtain a subspace H of G of co-dimension
at most W (a(ε)−3 ). Consequently, f restricted to all but at most a(ε) fraction of the cosets of H are
a(ε)-uniform. We define a reduced function f R : Fn2 → {0, 1} as follows.
For each g ∈ G, if f restricted to the coset g + H is a(ε)-uniform, then define
(
R 0 if µ1 ( fg+H ) ≤ b(ε)
fg+H (x) =
fg+H otherwise.
R
Else, define fg+H = 0.
Note that at most a(ε) + b(ε) fraction of modification has been made to f to obtain f R . Since f is
ε-far from being M-free, f R has a M-pattern at some linear map L. More precisely, for every i ∈ [k],
f R (L(vi )) = 1. Now consider the cosets L(vi ) + H. By our construction of f R , we know that f restricted
to each of these cosets is a(ε)-uniform and at least b(ε) dense. We will count the number of linear maps
φ : Fk2 → H such that f has a M pattern at L + φ . Notice that the probability the test rejects is at least
−3
2−k·W (a(ε) ) Pr ∀i, fL(vi )+H (φ (vi )) = 1 .
φ :Fk2 →H
To lower-bound this rejection probability, it suffices to show that the probability
Pr ∀i, fL(vi )+H (φ (vi )) = 1
φ :Fk2 →H
is bounded below by at least some constant depending on ε. To this end, we rewrite this probability as
" #
E
φ :Fk2 →H
∏ fi (φ (vi )) , (3.1)
i∈[k]
where fi = fL(vi )+H . By replacing each function fi by E fi + ( fi − E fi ), it is easy to see that the above
expression can be expanded into a sum of 2k terms, one of which is ∏i∈[k] E fi , which is at least b(ε)k . For
the other 2k − 1 terms, by applying Proposition 3.4 and using Parseval’s identity, each of these terms is
bounded above by a(ε)1/2 . So Equation (3.1) is at least b(ε)k − (2k − 1)a(ε)1/2 . To finish the analysis, we
need to specify a(ε), b(ε) such that b(ε)k − (2k − 1)a(ε)1/2 > 0 and a(ε) + b(ε) < ε. Both are satisfied
by setting a(ε) = (ε/4)2k , b(ε) = ε/2. Thus, the rejection probability is at least
6k
τ(ε) ≥ 2−k(W ((4/ε) )+2) · ε k ,
completing the proof.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 85
A RNAB B HATTACHARYYA , V ICTOR C HEN , M ADHU S UDAN AND N ING X IE
4 Graphic matroids have complexity 1
Here we prove that graphic matroids have complexity 1. While the proof is simple, we believe it sheds
insight into the notion of complexity and shows that even the class of 1-complexity matroids is quite rich.
Proof of Lemma 2.7. Recall that throughout we are assuming G to be a simple graph. Fix an arbitrary
edge e in G with vertices v1 and v2 as its two ends. We partition the remaining edges of G into two sets
S1 and S2 such that, if an edge is incident to v1 then it is in S1 and otherwise, it is in S2 . Because G is
simple, a cycle in G containing e must include an edge (apart from edge e) which is incident to v1 and
another edge (other than e) which is not incident to v1 . Therefore e is not in the span of either S1 or S2 .
This shows that the complexity of the matroid of G is at most 1. But since we assume that the complexity
of matroid of G is greater than 0, therefore the graphic matroid of G has complexity 1.
As we have seen earlier, Lemma 2.8 holds for any matroid of complexity 1. Hence, it is a natural
question to ask whether there exist non-graphic matroids which have complexity 1. In the following we
show that such matroids do exist. It is an open question to come up with a natural characterization of
matroids having complexity 1.
First we make the following claim which follows immediately from the definition of cographic
matroids and the notion of complexity.
Claim 4.1. A cographic matroid M∗ (G) has complexity 1 if and only if, for every edge e ∈ E(G), there
is a partition of E(G) \ {e} into two disjoint sets A and B such that both of the subgraphs (V (G), A) and
(V (G), B) are connected.
Proposition 4.2. There is a matroid with complexity 1 that is not graphic.
Proof. Consider the cographic matroid of K5 . Embed K5 in the plane as a pentagon and all its diagonals.
Fix an outer edge e and partition the remaining 9 edges into two sets. One is the 4 outer edges and the
other is the remaining 5 diagonal edges. Clearly both outer-edge set and diagonal-edge set make the five
vertices connected. Therefore by Claim 4.1, the cographic matroid of K5 is of complexity 1. On the other
hand, by a theorem of Tutte [34], a matroid cannot be graphic if it contains M∗ (K5 ) as a minor, which
M∗ (K5 ) clearly does. So, M∗ (K5 ) is an example of a non-graphic matroid that has complexity 1.
We remark that not all cographic matroids have complexity 1. For example, the cographic matroid
of K3,3 cannot have complexity 1 because if we remove an edge from K3,3 , there do not remain enough
edges to form two edge-disjoint connected graphs on 6 vertices, violating Claim 4.1.
5 Infinitely many monotone properties
In this section we prove Theorem 1.3, that there are infinitely many matroids for which the property of
being M-free are pairwise very different.
To do so we consider a pair of target matroids M1 and M2 . Based on just the first matroid M1 , we
create a canonical function f = fM1 : Fn2 → {0, 1}. We show, using a simple analysis, that this canonical
function is far from being M1 -free. We then show that if this function has an instance of M2 inside, then
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 86
T ESTING L INEAR -I NVARIANT N ON -L INEAR P ROPERTIES
there is a “homomorphism” (in a sense we define below) from M2 to M1 . Finally we show two different
ways in which one can rule out homomorphisms between pairs of graphic matroids; one based on the odd
girth of the matroids, and the other based on the maximum degree of M1 . Together these ideas lead to
proofs of distinguishability of many different matroids.
Definition 5.1. Given a binary matroid M represented by vectors v1 , . . . , vk ∈ Fk2 , and integer n ≥ k, let
the canonical function f = fM : Fn2 → {0, 1} be given by f (x, y) = 1 if x ∈ {v1 , . . . , vk } and 0 otherwise;
where x ∈ Fk2 and y ∈ Fn−k
2 .
Claim 5.2. Let M be a binary matroid with vi 6= 0 for all i ∈ {1, . . . , k}. Then fM is 21k –far from being
M-free.
Proof. Note that if we consider the linear map L : Fk2 → Fn2 that sends x to hx, 0i, then f contains M at
L. So f is not M-free. However we wish to show that any function that is 2−k -close to f contains M
somewhere. Fix a function g such that δ ( f , g) = δ < 2−k . We will show that g contains M somewhere.
For i ∈ [k] let
δi = Pr [ f (vi , y) 6= g(vi , y)] .
y∈Fn−k
2
Note that ∑ki=1 δi ≤ 2k · δ < 1. Now consider a random linear map L1 : Fk2 → Fn−k 2 , and its extension
k n
L : F2 → F2 given by L(x) = hx, L1 (x)i. For every non-zero x and in particular for x ∈ {v1 , . . . , vk }, we
have L1 (x) is distributed uniformly over Fn−k
2 . Thus, for any fixed i ∈ [k], we have PrL1 [g(L(vi )) 6= 1] ≤ δi .
By the union bound, we get that PrL1 [∃i such that g(L(vi )) 6= 1] ≤ ∑i δi < 1. In other words, there exists
a linear map L1 (and thus L) such that for every i, g(L(vi )) = 1 and so g contains M at L.
We now introduce our notion of a “homomorphism” between binary matroids. (We stress that the
phrase homomorphism is conjured up here and we are not aware of either this notion, or the phrase being
used in the literature. We apologize for confusion if this phrase is used to mean something else.)
Definition 5.3 (Homomorphism). Let M1 and M2 be binary matroids given by v1 , . . . , vk ∈ Fk2 and
w1 , . . . , w` ∈ F`2 . We say that M2 has a homomorphism to M1 if there is a map φ : {w1 , . . . , w` } →
{v1 , . . . , vk } such that for every set T ⊆ [`] such that ∑i∈T wi = 0, it is the case that ∑i∈T φ (wi ) = 0.
For graphic matroids, the matroid-homomorphism from G to H is a map from the edges of G to the
edges of H that ensures that cycles are mapped to even degree subgraphs of H.
Lemma 5.4. If the canonical function fM1 contains an instance of M2 somewhere, then M2 has a
homomorphism to M1 .
Proof. Let f = fM1 contain M2 at L. So L : F`2 → Fn2 is a linear map satisfying f (L(wi )) = 1 for every
i ∈ [`]. Now consider the projection map π : Fn2 → Fk2 which sends hx, yi to x (where x ∈ Fk2 and y ∈ Fn−k 2 ).
We claim that the map φ which sends x to π(L(x)) gives a homomorphism from M2 to M1 . On the
one hand φ is linear and so if ∑i∈T wi = 0, then we have ∑i∈T φ (wi ) = φ (∑i∈T wi ) = φ (0) = 0. On the
other hand, we also have that φ (wi ) ∈ {v1 , . . . , vk }. This is true since f (L(wi )) = 1, which implies, by the
definition of the canonical function f , that π(L(wi )) ∈ {v1 , . . . , vk }. Thus φ satisfies the requirements of
a homomorphism from M2 to M1 .
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 87
A RNAB B HATTACHARYYA , V ICTOR C HEN , M ADHU S UDAN AND N ING X IE
The above lemma now motivates the search for matroids M2 that are not homomorphic to M1 .
Proving non-homomorphism in general may be hard, but we give a couple of settings where we can find
simple proofs, each addresses a different case of Theorem 1.3.
For a matroid M, let its odd girth, denoted og(M), be the size of the smallest dependent set of odd
cardinality, i. e., the size of the smallest odd set T ⊆ [`] such that ∑i∈T wi = 0.
Lemma 5.5. If M2 has a homomorphism to M1 , then og(M2 ) ≥ og(M1 ).
Proof. Let φ be a homomorphism from M2 to M1 and let T ⊆ [`] denote the smallest odd dependent set
of M2 . Now let T 0 ⊆ [k] be the set
n o
T 0 = j ∈ [k] |{i ∈ T | φ (wi ) = v j }| is odd .
On the one hand, we have T 0 has odd cardinality; and on the other, we have 0 = ∑i∈T φ (wi ) = ∑ j∈T 0 v j .
So T 0 is an odd dependent set in M1 . The lemma follows since |T | ≥ |T 0 |.
For graphic matroids constructed from the odd cycle graph Ck , we have that its odd girth is just k and
so the above lemmas combine to give that Ck -freeness is distinguishable from Ck+2 -freeness, and this
suffices to prove Part (1) of Theorem 1.3.
However the odd girth criterion might suggest that G-freeness for any graph containing a triangle
might be equivalent. We next rule this possibility out.
Lemma 5.6. Let M1 be the graphic matroid of the complete graph Ka on a vertices, and let M2 be the
graphic matroid of Kb . Then, if b ≥ 2 + 2, there is no homomorphism from M2 to M1 .
a
Proof. Assume otherwise and let φ be such a homomorphism. Fix any vertex of Kb and let e1 , . . . , eb−1
denote the b − 1 edges incident to this vertex. By the pigeonhole principle, (since b − 1 > a2 ) there must
exist a pair of incident edges ei and e j such that φ (ei ) = φ (e j ). But now let f denote the edge which
forms a triangle with ei and e j . Since in Kb we have ei + e j + f = 0 (viewing these elements as vectors
over {0, 1}), it must be that φ ( f ) = φ (ei ) + φ (e j ) = 0 which is not an element of the ground set of M1 .
This yields the desired contradiction.
We are now ready to prove Theorem 1.3.
Proof of Theorem 1.3. First note that Ck+2 -free functions are also Ck -free. Informally, suppose a function
f has a k cycle at point x1 , . . . , xk , i. e., f (xi ) = 1 at these points and ∑i xi = 0. Then f has a k + 2 cycle at
the points x1 , x1 , x1 , x2 , . . . , xk . (This informal argument can obviously be converted to a formal one once
we specify the graphic matroids corresponding to Ck and Ck+2 formally.)
On the other hand, if we take M1 to be the graphic matroid corresponding to Ck+2 and f to be the
canonical function corresponding to M1 , then by Claim 5.2 it is 2−k -far from M1 -free, and by Lemmas 5.4
and 5.5 it does not contain M2 , the graphic matroid of Ck .
For the second part of the theorem, note that every property that is G-free is also H-free if G is a
subgraph of H. Thus Kk -free is contained in K` free if k ≤ `. The proper containment can now be shown
as above, using Claim 5.2 and Lemmas 5.4 and 5.6.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 88
T ESTING L INEAR -I NVARIANT N ON -L INEAR P ROPERTIES
6 Testing non-monotone properties
In this section we prove Theorem 2.4. (Readers may find it useful to recall the background material in
Section 3.1.) We show that for non-monotone properties, i. e., when Σ 6= 0k or 1k , the property of (M, Σ)-
free is testable when the underlying graph is a cycle. However, as opposed to Section 5, the number of
non-monotone properties associated with cycles is finite. In fact we give a complete characterization of
these non-monotone properties in Section 7.
Proof of Theorem 2.4. Suppose we have oracle access to a function f : Fn2 → {0, 1}. Consider the
following k-query test T , which selects a linear map L : Fk2 → Fn2 uniformly at random from all such
possible linear maps. T has oracle access to f and queries f at the points L(v1 ), . . . , L(vk ). T rejects iff
all of these points are evaluated to 1. If f is (M, Σ)-free, T never rejects and has completeness 1.
Now we analyze the soundness of T . Suppose that f is ε-far from being (M, Σ)-free. We want to
show that T rejects with probability at least τ(ε), such that τ(ε) > 0 whenever ε > 0.
Let 1/2 < η < 1 be any constant, and a(ε) and b(ε) be functions of ε that satisfy the constraints
a(ε) + b(ε) < ε and 1 − η > b(ε). We shall specify these two functions at the end of the proof.
Now let G denote Fn2 . We apply Lemma 3.3 to f to obtain a subspace H of G of co-dimension at most
W (a(ε)−3 ). We define a reduced function f R : Fn2 → {0, 1} as follows. We assume that Σ has at least two
occurrences of 1. (Otherwise it has at least two occurrences of 0, and in the construction of f R , we flip
the roles of 1 and 0 when fg+H is not uniform. The rest of the proof will proceed analogously, and we
leave its verification to the readers.)
For each g ∈ G, if f restricted to the coset g + H is a(ε)-uniform, then define
0
if µ1 ( fg+H ) < b(ε)
R
fg+H = 1 if µ1 ( fg+H ) > 1 − b(ε)
fg+H otherwise.
Otherwise, define (
R 1 if µ1 ( fg+H ) ≥ η
fg+H =
0 otherwise.
Note that at most a(ε) + b(ε) fraction of modification has been made to f to obtain f R , so f R is ε-close to
f . By assumption, f is ε-far from (M, Σ)-free, so f R has a (M, Σ) pattern at some linear map L : Fk2 → Fn2 ,
i. e., for each i ∈ [k], f R (L(vi )) = σi , where Σ = hσ1 , . . . , σk i, and σi ∈ {0, 1}. Now consider the cosets
L(vi ) + H. By our choice of rounding, f restricted to each L(vi ) + H is dense in the symbol σi , i. e.,
µσi ( fL(vi )+H ) ≥ b(ε), since 1 − η ≥ b(ε). We want to show that there are many (M, Σ) patterns spanning
across these cosets. In particular, we restrict our attention to the relative number of (M, Σ)-patterns at
linear maps of the form L + φ , where φ maps linearly from Fk2 to H. Notice that the probability the test
T rejects is at least
−3
2−(k−1)W (a(ε) ) · Pr [∀i ∈ [k], fL(vi )+H (φ (vi )) = σi ] .
φ :Fk2 →H
It suffices to show that the probability
Pr [∀i ∈ [k], fL(vi )+H (φ (vi )) = σi ] (6.1)
φ :Fk2 →H
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 89
A RNAB B HATTACHARYYA , V ICTOR C HEN , M ADHU S UDAN AND N ING X IE
is bounded below by some constant depending only on ε. To this end, we divide our analysis into two
cases, based on whether there is some j ∈ [k] such that fL(v j )+H is a(ε)-uniform or not.
Case 1: There exists some j ∈ [k] such that fL(v j )+H is a(ε)-uniform.
For each i ∈ [k], define fi : H → {0, 1} to be fi = fL(vi )+H + σi + 1. Note that by definition, E fi ≥ b(ε).
We begin by arithmetize Equation (6.1) as
" #
E
φ :Fk2 →H
∏ fi (φ (vi )) .
i∈[k]
Since M is a cyclic matroid, by Fourier expansion,
" #
E
φ :Fk2 →H
∏ fi (φ (vi ))
i∈[k]
= E [ f1 (x1 ) · · · fk−1 (xk−1 ) fk (x1 + · · · + xk−1 )]
x1 ,...,xk−1 ∈H
" #
= E
x1 ,...,xk−1 ∈H
∑ fb1 (α1 )χα (x1 ) · · · ∑ fd
1 k−1 (αk−1 )χα k−1
fk (α)χα (x1 + · · · + xk−1 )
(xk−1 ) ∑ b
α1 ∈H αk−1 ∈H α∈H
= ∑ fb1 (α1 ) · · · fd
k−1 (αk−1 ) f k (α) E[χα1 +α (x1 )] · · ·
b E [χαk−1 +α (xk−1 )]
x1 xk−1
α1 ,...,αk−1 ,α∈H
k−1
= ∑ fb1 (α1 ) · · · fd
k−1 (αk−1 ) f k (α) ∏ δ (α, αi )
b
α1 ,...,αk−1 ,α∈H i=1
= ∑ ∏ bfi (α) ,
α∈H i∈[k]
where in the second last step we use the notation of δ -function, which is defined by δ (α, αi ) = 1 if
αi = α and 0 otherwise.
Using the facts that E fi ≥ b(ε), f j is a(ε)-uniform, there exist two distinct indices i1 , i2 6= j ∈ [k]
(since k ≥ 3), Cauchy-Schwarz, and Parseval’s identity, respectively, we have
∑ ∏ bfi (α) ≥ b(ε)k − ∑ ∏ bfi (α)
α∈H i∈[k] α6=0∈H i∈[k]
≥ b(ε)k − a(ε) ∑ ∏ bfi (α)
α6=0∈H i∈[k]\{ j}
≥ b(ε)k − a(ε) ∑ fi1 (α) c
c fi2 (α) ,
α6=0∈H
!1/2 !1/2
≥ b(ε)k − a(ε) fi (α)2
∑ c 1 fi (α)2
∑ c 2
α6=0∈H α6=0∈H
≥ b(ε)k − a(ε) .
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 90
T ESTING L INEAR -I NVARIANT N ON -L INEAR P ROPERTIES
To finish the analysis, we need to specify a(ε), b(ε) such that the constraints a(ε) + b(ε) < ε and
1 − η > b(ε) are satisfied. Let
1
b(ε) = (1 − η) · ε and a(ε) = (1 − η)k ε k ,
2
we have that the rejection probability is at least
−3 )
τ(ε) ≥ 2−(k−1)W (a(ε) (1 − η)k ε k /2 .
Case 2: No j ∈ [k] exists such that fL(v j )+H is a(ε)-uniform.
Since M is a cyclic matroid, it is not hard to see that Equation (6.1) is equal to
Pr ∀i ∈ [k], fL(vi ) (xi ) = σi . (6.2)
x1 ,...,xk ∈H
∑i xi =0
Since Σ contains at least two occurrences of the symbol 1, we may assume without loss of generality
that σk−1 = σk = 1. Fix x1 , . . . , xk−2 ∈ H such that fL(vi ) (xi ) = σi . Let z = ∑k−2
i=1 xi . Since η > 1/2, by the
union bound we have
Pr [ fL(vk−1 ) (x) = fL(vk ) (x + z) = 1] = 1 − Pr [ fL(vk−1 ) (x) = 0 or fL(vk ) (x + z) = 0]
x∈H x∈H
≥ 1 − 2(1 − η)
> 0.
Since for each i ∈ [k], fL(vi )+H is not a(ε)-uniform, by our choice of rounding, Prx∈H [ fL(vi ) (xi ) = σi ] is
at least 1 − η. By picking x1 , . . . , xk−2 uniformly at random from H, it is not hard to see that the rejection
probability of the test is at least
−3 )
τ(ε) ≥ 2−(k−1)W (a(ε) (1 − η)k−2 (2η − 1),
where a(ε) = 21 (1 − η)k ε k .
7 Characterization of cycle-free functions
In this section we consider the property of being (M, Σ)-free, where M is the matroid of the k-cycle.
Syntactically these appear to be infinitely many different properties. We show that there are only finitely
many distinct properties here when Σ is not equal to 0k or 1k . (As noted in Section 5, when Σ = 1k , we do
get infinitely many distinct properties.)
Remarks on notation. For any x ∈ Fk2 and any y ∈ F`2 , we use xy to denote the concatenation of x and y,
which is an element in Fk+` k
2 . If x ∈ F2 is a binary string, then we write ones(x) for the number of indexes
i such that xi = 1, and similarly write zeros(x) for the number of zeros in x. Let f : Fn2 → {0, 1} be a
Boolean function. The complement of f , denoted f¯, is also a Boolean function such that f¯(x) = 1 − f (x)
for every x ∈ Fn2 . Let 0 (resp. 1) stand for the all-zero (resp. all-one) function over the Boolean cube
Fn2 . Finally, we use the following (standard) terminology to describe the distinct families of Boolean
functions which we are going to refer to in our characterization of (Ck , Σ)-free functions.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 91
A RNAB B HATTACHARYYA , V ICTOR C HEN , M ADHU S UDAN AND N ING X IE
• Const is the set of constant functions (i. e., Const = {0, 1}).
• Lin denotes the set of all linear functions, including the constant functions.4 coLin denotes the
complementary family, i. e., all functions whose complements are in Lin.
• Flin stands for the family of characteristic functions of linear subspaces and the 0 function, i. e.,
Flin = {0} ∪ { f : Fn2 → {0, 1} | f −1 (1) is a linear subspace of Fn2 } .
coFlin is the complementary family.
• Faff stands for the family of characteristic functions of affine subspaces and the 0 function, i. e.,
Faff = {0} ∪ { f : Fn2 → {0, 1} | f −1 (1) is an affine subspace of Fn2 } .
coFaff is the complementary family.
It turns out that for every k ≥ 3 and every Σ 6= 0k , 1k , a (Ck , Σ)-free family is one of the seven families
Const, Lin, coLin, Flin , coFlin , Faff , coFaff .
Theorem 7.1. For every k ≥ 3 and every Σ 6= 0k , 1k , a (Ck , Σ)-free family is one of
Const, Lin, coLin, Flin , coFlin , Faff , coFaff .
Specifically:
1. If zeros(Σ) and ones(Σ) are both even, the FCk ,Σ = Const.
2. If ones(Σ) > 1 is odd and zeros(Σ) is even, then FCk ,Σ = Lin. Complementarily, if zeros(Σ) > 1 is
odd and ones(Σ) is even, then FCk ,Σ = coLin.
3. If ones(Σ) = 1 and zeros(Σ) is even, then FCk ,Σ = Flin . Complementarily, if zeros(Σ) = 1 and
ones(Σ) is even, then FCk ,Σ = coFlin .
4. If ones(Σ), zeros(Σ) > 1 and are both odd, then FCk ,Σ = Faff .
5. If zeros(Σ) = 1 and ones(Σ) > 1 is odd, then FCk ,Σ = Faff . Complementarily, if ones(Σ) = 1 and
zeros(Σ) > 1 is odd, then FCk ,Σ = coFaff .
We begin with some simple facts and observations.
Fact 7.2 ([29]). Let S be an affine subspace. Then x, y and z are all in S implies x + y + z is also in S.
Conversely, if for any triple x, y and z in S implying x + y + z in S, then S is an affine subspace.
This fact immediately gives the following observations.
Observation 7.3. A function f : Fn2 → {0, 1} is (C4 , 1110)-free if and only if f is in Faff .
4 One may think of linear functions here as being the codewords of the Hadamard codes.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 92
T ESTING L INEAR -I NVARIANT N ON -L INEAR P ROPERTIES
In a similar fashion, the following fact provides a characterization of (C3 , 100)-free (and (C3 , 110)-
free) functions.
Fact 7.4. A function f : Fn2 → {0, 1} is (C3 , 100)-free if and only if f is the disjunction (OR) of linear
functions (or the all 1 function). Consequently, f is (C3 , 110)-free if and only if f is in Flin .
Proof. Let S = { x ∈ Fn2 | f (x) = 0}. If S is empty, then f is the all 1 function. Otherwise let x and y be
any two elements in S (not necessarily distinct). Then if f is (C3 , 100)-free, it must be the case that x + y
is also in S. Thus S is a linear subspace in Fn2 . Suppose the dimension of S is k with k ≥ 1. Then there
are k linearly independent vectors a1 , . . . , ak ∈ Fn2 such that z ∈ S iff (hz, a1 i = 0) ∧ · · · ∧ (hz, ak i = 0).
Therefore, by De Morgan’s law, f (z) = 1 iff z ∈ S̄ iff (hz, a1 i = 1) ∨ · · · ∨ (hz, ak i = 1), which is equivalent
to the claim. Similar argument proves the characterization of (C3 , 110)-free functions.
Observation 7.5. If Σ 6= 1k for some k > 2, then (Ck+2 , Σ00)-free ⊆ (Ck , Σ)-free. Similarly, if Σ 6= 0k for
some k > 2, then (Ck+2 , Σ11)-free ⊆ (Ck , Σ)-free.
Proof. By symmetry, we only need to prove the first part. Let f ∈ (Ck+2 , Σ00)-free. Suppose f ∈ /
j
(Ck , Σ)-free, then there exists a violating tuple, say, hx1 , x2 , . . . , x j i such that ∑i=1 xi = 0 and
h f (x1 ), f (x2 ), . . . , f (x j )i = Σ .
Since Σ is not an all 1 vector, there exists some k such that f (xk ) = 0. But then hx1 , x2 , . . . , x j , xk , xk i
would be a violation tuple of pattern (Ck+2 , Σ00), contradicting our assumption that the function f is in
(Ck+2 , Σ00)-free.
Observation 7.6. (C4 , 0011)-free equals the set of constant functions.
Proof. Clearly a constant function has no 0011 pattern. For the reverse inclusion, suppose f is (C4 , 0011)-
free but not a constant function. Then there exist x and y such that f (x) = 0 f (y) = 1. Then
h f (x), f (x), f (y), f (y)i = 0011 .
Proof of Theorem 7.1.
1. This follows from Observation 7.5 and Observation 7.6.
2. We only need to prove the first half of the claim, since the second half will then follow by symmetry.
It is easy to check that, if ones(Σ) > 1 is odd and zeros(Σ) is even, then Lin ⊆ FCk ,Σ . To prove the
other containment, note that by Fact 7.4 and Observation 7.5, FCk ,Σ is contained in the disjunction
of linear functions and in particular, we may assume f is (C5 , 00111)-free. So
f (x) = (ha1 , xi = 1) ∨ (ha2 , xi = 1) ∨ · · · ,
where a1 , a2 , . . . , are non-zero, distinct and linearly independent vectors. Since a1 and a2 are
linearly independent, there exist x1 , x2 such that ha1 , x1 i = ha2 , x2 i = 1 while ha1 , x2 i = ha2 , x1 i = 0.
Then h f (0), f (0), f (x1 ), f (x2 ), f (x1 + x2 )i = 00111. Therefore f cannot be the disjunction of more
than one linear function, making it linear. Finally note that
Lin ⊆ (C|Σ| , Σ)-free ⊆ (C5 , 00111)-free ⊆ Lin .
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 93
A RNAB B HATTACHARYYA , V ICTOR C HEN , M ADHU S UDAN AND N ING X IE
3. This follows from Fact 7.4 and Observation 7.5.
4. Let i and j be odd integers. If f (x) is a linear function, then it is (Ci+ j , 0i 1 j )-free since j is
odd. If f (x) is the complement of a linear function, then it is (Ci+ j , 0i 1 j )-free since i is odd. So
if f is an affine function, then it is (Ci+ j , 0i 1 j )-free. Now consider (C6 , 000111)-free. If f is
(C6 , 000111)-free then the set f −1 (1) forms an affine subspace (since f is also (C4 , 0111)-free.).
Similarly the set f −1 (0) forms an affine subspace (since f is also (C4 , 0001)-free) and so f is an
affine function.
5. This follows from Observation 7.3 and Observation 7.5.
8 Conclusions and future work
We introduced an infinite family of properties of Boolean functions and showed them to be testable.
Unfortunately, we were only able to analyze the tests when the matroid M was graphic and the pattern
was monochromatic. This raises a plethora of new problems that we describe below.
The first natural quest is to generalize the problem to the solution to the case when the matroid is
arbitrary over {0, 1}, and further to the case when the matroid is over other fields. We note that this
seems to pose significant technical hurdles and indeed even the simple property of being free of the
matroid {e1 , e2 , e3 , e1 + e2 , e2 + e3 , e3 + e1 , e1 + e2 + e3 } (where e1 , e2 , e3 are linearly independent vectors)
is problematic. Subsequent to this work, Shapira [32] and Král’ et al [27] have successfully resolved this
question.
Next, it would be nice to extend the results to the case where the pattern Σ is an arbitrary binary string,
as opposed to being monotone. We did manage to extend this in the special case where M is a cyclic
matroid, but in this case the extension is not very interesting. We do feel that our proof techniques already
capture some non-trivial other cases, but are far from capturing all cases, even for graphic matroids.
Extending the patterns further, there is no real reason to view the range as a field element, so a major
generalization would be to consider matroids over arbitrary fields, and letting the range be some arbitrary
finite set R where the forbidden pattern Σ ∈ Rk . (We don’t believe there should be any major technical
barriers in this step, once we are able to handle arbitrary 0/1 patterns Σ.) Finally, all the above problems
consider the case of a single forbidden pattern (and its linear transformations). A more general setting
would be the forbidden pattern consisting of a collection of strings in Fk2 , i. e., Ξ = {Σ1 , . . . , Σ` } for some
` > 1.
These properties were specified by a matroid M on k elements and a pattern Ξ ⊆ Fk2 . However to
capture the full range of linear-invariant non-linear properties that allow one-sided error local tests, we
should also allow the conjunction of a constant number of constraints. We believe this could lead to a
characterization of all linear-invariant non-linear properties that allow one-sided error local tests.
In a different direction, we feel that it would also be nice to develop richer techniques to show the
distinguishability of syntactically different properties. For instance, even for the graphic case we don’t
have a good understanding of when two different graphs represent essentially the same properties, and
when they are very different.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 94
T ESTING L INEAR -I NVARIANT N ON -L INEAR P ROPERTIES
Acknowledgments
We are grateful to Kevin Matulef for suggesting this research direction. We thank Tali Kaufman and
Swastik Kopparty for helpful discussions. We thank Asaf Shapira for drawing our attention to his
preprint [32]. Finally we would like to thank the anonymous referees for their useful comments and
suggestions.
References
[1] N OGA A LON , E LDAR F ISCHER , I LAN N EWMAN , AND A SAF S HAPIRA: A combinatorial charac-
terization of the testable graph properties: It’s all about regularity. SIAM J. Comput., 39:143–167,
2009. [doi:10.1137/060667177] 76, 83
[2] N OGA A LON , TALI K AUFMAN , M ICHAEL K RIVELEVICH , S IMON L ITSYN , AND DANA RON:
Testing low-degree polynomials over GF(2). In Proc. Approx. Random. Comb. Opt. (RANDOM ’03),
volume 2764 of Lecture Notes in Computer Science, pp. 188–199. Springer, 2003. [doi:10.1007/978-
3-540-45198-3 17] 76, 77
[3] N OGA A LON , M ICHAEL K RIVELEVICH , I LAN N EWMAN , AND M ARIO S ZEGEDY: Regular
languages are testable with a constant number of queries. SIAM J. Comput., 30(6):1842–1862, 2000.
[doi:10.1137/S0097539700366528] 76
[4] N OGA A LON AND A SAF S HAPIRA: A characterization of the (natural) graph properties testable
with one-sided error. In Proc. 46th FOCS, pp. 429–438. IEEE Comp. Soc. Press, 2005.
[doi:10.1109/SFCS.2005.5] 76
[5] N OGA A LON AND A SAF S HAPIRA: Every monotone graph property is testable. In Proc. 37th
STOC, pp. 128–137. ACM Press, 2005. [doi:10.1145/1060590.1060611] 76
[6] N OGA A LON AND A SAF S HAPIRA: Homomorphisms in graph property testing - a survey. Technical
Report 085, Electron. Colloq. on Comput. Complexity (ECCC), 2005. [ECCC:TR05-085] 83
[7] S ANJEEV A RORA , C ARSTEN L UND , R AJEEV M OTWANI , M ADHU S UDAN , AND M ARIO
S ZEGEDY: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555,
1998. [doi:10.1145/278298.278306] 76
[8] S ANJEEV A RORA AND S HMUEL S AFRA: Probabilistic checking of proofs: A new characterization
of NP. J. ACM, 45(1):70–122, 1998. [doi:10.1145/273865.273901] 76
[9] L ÁSZL Ó BABAI , L ANCE F ORTNOW, AND C ARSTEN L UND: Non-deterministic exponen-
tial time has two-prover interactive protocols. Comput. Complexity, 1(1):3–40, 1991.
[doi:10.1007/BF01200430] 76
[10] M IHIR B ELLARE , D ON C OPPERSMITH , J OHAN H ÅSTAD , M ARCOS A. K IWI , AND M ADHU
S UDAN: Linearity testing over characteristic two. IEEE Trans. Inform. Theory, 42(6):1781–1795,
1996. [doi:10.1109/18.556674] 76
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 95
A RNAB B HATTACHARYYA , V ICTOR C HEN , M ADHU S UDAN AND N ING X IE
[11] M IHIR B ELLARE , O DED G OLDREICH , AND M ADHU S UDAN: Free bits, PCPs, and
nonapproximability—towards tight results. SIAM J. Comput., 27(3):804–915, 1998.
[doi:10.1137/S0097539796302531] 76
[12] V ITALY B ERGELSON , T ERENCE TAO , AND TAMAR Z IEGLER: An inverse theorem for the
uniformity seminorms associated with the action of Fω . Geom. Funct. Anal., 19:1539–1596, 2010.
[doi:10.1007/s00039-010-0051-1] 79
[13] A RNAB B HATTACHARYYA , V ICTOR C HEN , M ADHU S UDAN , AND N ING X IE: Testing linear-
invariant non-linear properties: A short report. Technical Report 10-116, Electron. Colloq. on
Comput. Complexity (ECCC), July 2010. [ECCC:TR10-116] 80
[14] A RNAB B HATTACHARYYA , E LENA G RIGORESCU , JAKOB N ORDSTR ÖM , AND N ING X IE: Sep-
arations of matroid freeness properties. Technical Report 10-136, Electron. Colloq. on Comput.
Complexity (ECCC), August 2010. [ECCC:TR10-136] 80
[15] A RNAB B HATTACHARYYA , E LENA G RIGORESCU , AND A SAF S HAPIRA: A unified framework
for testing linear-invariant properties. In Proc. 51st FOCS, pp. 478–487. IEEE Comp. Soc. Press,
2010. [doi:10.1109/FOCS.2010.53] 80
[16] M ANUEL B LUM , M ICHAEL L UBY, AND RONITT RUBINFELD: Self-testing/correcting with appli-
cations to numerical problems. J. Comput. System Sci., 47(3):549–595, 1993. [doi:10.1016/0022-
0000(93)90044-W] 76
[17] C HRISTIAN B ORGS , J ENNIFER T. C HAYES , L ÁSZL Ó L OV ÁSZ , V ERA T. S ÓS , BAL ÁZS S ZEGEDY,
AND K ATALIN V ESZTERGOMBI : Graph limits and parameter testing. In Proc. 38th STOC, pp.
261–270. ACM Press, 2006. [doi:10.1145/1132516.1132556] 76
[18] V ICTOR C HEN , M ADHU S UDAN , AND N ING X IE: Property testing via set-theoretic operations. In
Proc. 2nd Symp. Innov. Comput. Sci. (ICS ’11), pp. 211–222, 2011. 80
[19] O DED G OLDREICH , S HAFI G OLDWASSER , AND DANA RON: Property testing and its connection
to learning and approximation. J. ACM, 45(4):653–750, 1998. [doi:10.1145/285055.285060] 76
[20] T IMOTHY G OWERS AND J ULIA W OLF: The true complexity of a system of linear equations.
Technical Report 0711.0185, arXiv e-print archive, 2007. [arXiv:0711.0185] 84
[21] B EN G REEN: A Szemerédi-type regularity lemma in abelian groups, with applications. Geom.
Funct. Anal., 15(2):340–376, 2005. [doi:10.1007/s00039-005-0509-8] 77, 78, 79, 80, 82, 83
[22] B EN G REEN AND T ERENCE TAO: Linear equations in primes. Ann. of Math., 171(3):1753–1850,
2010. [doi:10.4007/annals.2010.171.1753] 79, 82, 84
[23] J OHAN H ÅSTAD: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001.
[doi:10.1145/502090.502098] 76
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 96
T ESTING L INEAR -I NVARIANT N ON -L INEAR P ROPERTIES
[24] C HARANJIT S. J UTLA , A NINDYA C. PATTHAK , ATRI RUDRA , AND DAVID Z UCKERMAN: Testing
low-degree polynomials over prime fields. In Proc. 45th FOCS, pp. 423–432. IEEE Comp. Soc.
Press, 2004. [doi:10.1109/FOCS.2004.64] 76
[25] TALI K AUFMAN AND DANA RON: Testing polynomials over general fields. In Proc. 45th FOCS,
pp. 413–422. IEEE Comp. Soc. Press, 2004. [doi:10.1109/FOCS.2004.64] 76
[26] TALI K AUFMAN AND M ADHU S UDAN: Algebraic property testing: The role of invariance. In Proc.
40th STOC, pp. 403–412. ACM Press, 2008. [doi:10.1145/1374376.1374434] 77, 79
[27] DANIEL K R ÁL ’, O RIOL S ERRA , AND L LU ÍS V ENA: A removal lemma for systems of linear equa-
tions over finite fields. Technical Report 0809.1846, arxiv e-print archive, 2008. [arXiv:0809.1846]
79, 80, 94
[28] DANIEL K R ÁL ’, O RIOL S ERRA , AND L LU ÍS V ENA: A combinatorial proof of the removal lemma
for groups. J. Combin. Theory Ser. A, 116(4):971–978, 2009. [doi:10.1016/j.jcta.2008.12.003] 79,
80
[29] M ICHAL PARNAS , DANA RON , AND A LEX S AMORODNITSKY: Testing basic Boolean formulae.
SIAM J. Discrete Math., 16(1):20–46, 2003. [doi:10.1137/S0895480101407444] 76, 92
[30] RONITT RUBINFELD AND M ADHU S UDAN: Robust characterizations of polynomi-
als with applications to program testing. SIAM J. Comput., 25(2):252–271, 1996.
[doi:10.1137/S0097539793255151] 76
[31] A LEX S AMORODNITSKY AND L UCA T REVISAN: Gowers uniformity, influence of variables,
and PCPs. In Proc. 38th STOC, pp. 11–20, New York, NY, USA, 2006. ACM Press.
[doi:10.1145/1132516.1132519] 76
[32] A SAF S HAPIRA: Green’s conjecture and testing linear-invariant properties. In Proc. 41st STOC, pp.
159–166. ACM Press, 2009. [doi:10.1145/1536414.1536438] 79, 80, 94, 95
[33] T ERENCE TAO AND TAMAR Z IEGLER: The inverse conjecture for the Gowers norm over finite fields
via the correspondence principle. Analysis & PDE, 3(1):1–20, 2010. [doi:10.2140/apde.2010.3.1]
79
[34] W ILLIAM T. T UTTE: Matroids and graphs. Trans. Amer. Math. Soc., 90:527–552, 1959.
[doi:10.2307/1993185] 86
[35] D OMINIC J.A. W ELSH: Matroid Theory. Academic Press Inc., London, 1976. 80
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 97
A RNAB B HATTACHARYYA , V ICTOR C HEN , M ADHU S UDAN AND N ING X IE
AUTHORS
Arnab Bhattacharyya
CSAIL MIT, Cambridge, MA
abhatt mit edu
http://web.mit.edu/abhatt/www/
Victor Chen
Princeton University, Princeton, NJ
vychen princeton edu
http://people.csail.mit.edu/victor/
Madhu Sudan
Microsoft Research NE, Cambridge, MA
madhu mit edu
http://people.csail.mit.edu/madhu/
Ning Xie
CSAIL MIT, Cambridge, MA
ningxie csail mit edu
http://people.csail.mit.edu/ningxie/
ABOUT THE AUTHORS
A RNAB B HATTACHARYYA is a Ph. D. student at MIT, advised by Ronitt Rubinfeld. His
research interests are algorithms (sublinear-time and otherwise) and extremal and ad-
ditive combinatorics. He enjoys pigeonholing (his colleagues’) arguments, chopping
misbehaving objects into more well-behaved ones, and studying ZFC for surprise quizzes.
Lately, he has been really yearning for the days when Federer was the dominant tennis
player in the world.
V ICTOR C HEN did his undergraduate work at the University of Texas at Austin, and he
obtained his Ph. D. under the supervision of Madhu Sudan at MIT. His research interests
include property testing and combinatorics. In his spare time, he enjoys scavenging for
used CDs and watching foreign movies.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 98
T ESTING L INEAR -I NVARIANT N ON -L INEAR P ROPERTIES
M ADHU S UDAN received his Ph. D. from the University of California at Berkeley in 1992.
From 1992 to 1997 he was a research staff member at IBM’s Thomas J. Watson Research
Center. From 1997-2009 he was a faculty member at the Electrical Engineering and
Computer Science Department at the Massachusetts Institute of Technology. He is
currently a Principal Researcher at Microsoft Research New England. His research has
focussed on Probabilistic Checking of Proofs, List-Decoding, Property Testing, and
Semantic Communication.
N ING X IE is a Ph. D. student at MIT. His advisor is Ronitt Rubinfeld. His main research
interest is property testing.
T HEORY OF C OMPUTING, Volume 7 (2011), pp. 75–99 99