Property testing and its connection to learning and approximation.
In this paper, we consider the question of determining whether a function f has property P or is &egr;-far from any function with property P. A property testing algorithm is given a sample of the value of f on instances drawn according to some distribution. In some cases, it is also allowed to query f on instances of its choice. We study this question for different properties and establish some connections to problems in learning theory and approximation.In particular, we focus our attention on testing graph properties. Given access to a graph G in the form of being able to query whether an edge exists or not between a pair of vertices, we devise algorithms to test whether the underlying graph has  properties such as being bipartite, k-Colorable, or having a p-Clique (clique of density p with respect to the vertex set). Our graph property testing algorithms are probabilistic and make assertions that are correct with high probability, while making a number of queries that is independent of the size of the graph. Moreover, the property testing algorithms can be used to efficiently (i.e., in time linear in the number of vertices) construct partitions of the graph that correspond to the property being tested, if it holds for the input graph.
Introduction
We are interested in the following general question of Property
Let P be a fixed property of functions, and f
be an unknown function. Our goal is to determine (possibly
if f has property P or if it is far from any
function which has property P, where distance between functions
is measured with respect to some distribution D on the
domain of f . Towards this end, we are given examples of the
form (x; f(x)), where x is distributed according to D. We
may also be allowed to query f on instances of our choice.
The problem of testing properties emerges naturally in the
context of program checking and probabilistically checkable
proofs as applied to multi-linear functions or low-degree polynomials
[14, 7, 6, 19, 21, 36, 5, 4, 10, 11, 8, 9]. Property testing
per se was considered in [36, 35]. Our definition of property
testing is inspired by the PAC learning model [37]. It allows
the consideration of arbitrary distributions rather than uniform
ones, and of testers which utilize randomly chosen instances
only (rather than being able to query instances of their own
choice).
Full version available from http://theory.lcs.mit.edu/~oded/
y Dept. of Computer Science and Applied Math., Weizmann Institute of
Science, ISRAEL. E-mail: oded@wisdom.weizmann.ac.il. On sabbatical
leave at LCS, MIT.
z Laboratory for Computer Science, MIT, 545 Technology Sq., Cambridge,
MA 02139. E-mail: shafi@theory.lcs.mit.edu.
x Laboratory for Computer Science, MIT, 545 Technology Sq., Cambridge,
MA 02139. E-mail: danar@theory.lcs.mit.edu. Supported by an NSF
postdoctoral fellowship.
We believe that property testing is a natural notion whose
relevance to applications goes beyond program checking, and
whose scope goes beyond the realm of testing algebraic prop-
erties. Firstly, in some cases one may be merely interested
in whether a given function, modeling an environment, (resp.
a given program) possesses a certain property rather than be
interested in learning the function (resp. checking that the program
computes a specific function correctly). In such cases,
learning the function (resp., checking the program) as means
of ensuring that it satisfies the property may be an over-kill.
Secondly, learning algorithms work under the postulation that
the function (representing the environment) belongs to a particular
class. It may be more efficient to test this postulation
first before trying to learn the function (and possibly failing
when the postulation is wrong). Similarly, in the context of
program checking, one may choose to test that the program
satisfies certain properties before checking that it computes a
specified function. This paradigm has been followed both in
the theory of program checking [14, 36] and in practice where
often programmers first test their programs by verifying that
the programs satisfy properties that are known to be satisfied
by the function they compute. Thirdly, we show how to apply
property testing to the domain of graphs by considering
several classical graph properties. This, in turn, offers a new
perspective on approximation problems as discussed below.
THE RELEVANT PARAMETERS. Let F be the class of functions
which satisfy property P. Then, testing property P corresponds
to testing membership in the class F . The two parameters
relevant to property testing are the permitted distance, ffl,
and the desired confidence, ffi . We require the tester to accept
each function in F and reject every function which is further
than ffl away from any function in F . We allow the tester to
be probabilistic and make incorrect positive and negative assertions
with probability at most ffi . The complexity measures
we focus on are the sample complexity (the number of examples
of the function's values that the tester requires), the query
complexity (the number of function queries made - if at all),
and the running time of the tester.
1.1. Property Testing and Learning Theory
As noted above, our formulation of testing mimics the standard
frameworks of learning theory. In both cases one is given
access to an unknown target function (either in the form of
random instances accompanied by the function values or in
the form of oracle access to the function). A semantic difference
is that, for sake of uniformity, even in case the functions
are Boolean, we refer to them as functions rather than con-
cepts. However, there are two important differences between
property testing and learning. Firstly, the goal of a learning algorithm
is to find a good approximation to the target function
testing algorithm should only determine
whether the target function is in F or is far away from it. This
makes the task of the testing seem easier than that of learning.
On the other hand, a learning algorithm should perform well
only when the target function belongs to F whereas a testing
algorithm must perform well also on functions far away from
F . Furthermore, (non-proper) learning algorithms may output
an approximation ~
f of the target f 2 F so that ~
f 62 F .
We show that the relation between learning and testing is
non-trivial. On one hand, proper (representation dependent)
learning implies testing. On the other hand, there are function
classes for which testing is harder than (non-proper) learning,
. Nonetheless, there are also function
classes for which testing is much easier than learning. Further
details are given in Subsection 2.2. In addition, the graph
properties discussed below provide a case where testing (with
queries) is much easier than learning (also with queries).
1.2. Testing Graph Properties
In the main technical part of this paper, we focus our attention
on testing graph properties. We view graphs as Boolean
functions on pairs of vertices, the value of the function representing
the existence of an edge. We mainly consider testing
algorithms which use queries and work under the uniform dis-
tribution. That is, a testing algorithm for graph property P
makes queries of the form "is there an edge between vertices
u and v" in an unknown graph G. It then decide whether G
has property P or is "ffl-away" from any graph with property P,
and is allowed to err with probability 1=3. Distance between
two N -vertex graphs is defined as the fraction of vertex-pairs
which are adjacent in one graph but not in the other.
We present algorithms of poly(1=ffl) query-complexity and
running-time 1 at most exp( ~
testing the following
graph properties:
k-Colorability for any fixed k - 2. (Here the query-
complexity is poly(k=ffl), and for the running-time
is ~
ae-Clique for any ae ? 0. That is, does the N -vertex graph
has a clique of size aeN .
ae-CUT for any ae ? 0. That is, does the N -vertex graph has
a cut of size at least aeN 2 . A generalization to k-way cuts
works within query-complexity poly((log k)=ffl).
ae-Bisection for any ae ? 0. That is, does the N -vertex graph
have a bisection of size at most aeN 2 .
1 Here and throughout the paper, we consider a RAM model in which trivial
manipulation of vertices (e.g., reading/writing a vertex name and ordering
vertices) can be done in constant time.
Furthermore:
ffl For all the above properties, in case the graph has the desired
property, the testing algorithm outputs some auxiliary
information which allows to construct, in poly(1=ffl) \Delta N -
time, a partition which approximately obeys the property.
For example, for ae-CUT, we can construct a partition with
at least (ae \Gamma ffl)N 2 crossing edges.
ffl Except for Bipartite (2-Colorability) testing, running-time
of poly(1=ffl) is unlikely, as it will imply NP ' BPP .
ffl None of these properties can be tested without queries when
using o(
examples.
ffl The k-Colorability tester has one-sided error: it always
accepts k-colorable graphs. Furthermore, when rejecting
a graph, this tester always supplies a poly(1=ffl)-size sub-graph
which is not k-colorable. All other algorithms have
two-sided error, and this is unavoidable within o(N ) query-
complexity.
ffl Our algorithms for k-Colorability, ae-Clique and ae-Cut can
be easily extended to provide testers with respect to product
distributions: that is, distributions
the form \Pi(u;
is a distribution on the vertices. In contrast, it is not possible
to test any of the graph properties discussed above in a
distribution-free manner.
GENERAL GRAPH PARTITION. All of the above properties are
special cases of the General Graph k-Partition property, parameterized
by a set of lower and upper bounds. The parameterized
property holds if there exists a partition of the vertices into k
disjoint subsets so that the number of vertices in each subset
as well as the number of edges between each pair of subsets
is within the specified lower and upper bounds. We present
a testing algorithm for the above general property. The algorithm
uses ~
queries, runs in time exponential in its
query-complexity, and makes two-sided error. Approximating
partitions, if they exist, can be efficiently constructed in this
general case as well. We note that the specialized algorithms
perform better than the general algorithm with the appropriate
parameters.
OTHER GRAPH PROPERTIES. Going beyond the general graph
partition problem, we remark that there are graph properties
which are very easy to test (e.g., Connectivity, Hamiltonicity,
and Planarity). On the other hand, there are graph properties
in NP which are extremely hard to test; namely, any testing
algorithm must inspect at
of the vertex
pairs. In view of the above, we believe that providing a characterization
of graph properties according to the complexity of
testing them may not be easy.
OUR TECHNIQUES. Our algorithms share some underlying
ideas. The first is the uniform selection of a small sample and
the search for a suitable partition of this sample. In case of
k-Colorability certain k-colorings of the subgraph induced by
this sample will do, and these are found byk-coloring a slightly
augmented graph. In the other algorithms we exhaustively try
all possible partitions. This is reminiscent of the exhaustive
sampling of Arora et. al. [3], except that the partitions considered
by us are always directly related to the combinatorial
structure of the problem. We show how each possible partition
of the sample induces a partition of the entire graph so that the
following holds. If the tested graph has the property in question
then, with high probability over the choice of the sample,
there exists a partition of the sample which induces a partition
of the entire graph so that the latter partition approximately
satisfies the requirements established by the property in ques-
tion. For example, in case the graph has a ae-cut, there exists a
2-way-partition of the sample inducing a partition of the entire
graph with (ae \Gamma ffl)N 2 crossing edges. On the other hand,
if the graph should be rejected by the test, then by definition
no partition of the entire graph (and in particular none of the
induced partitions) approximately obeys the requirements.
The next idea is to use an additional sample to approximate
the quality of each such induced partition of the graph,
and discover if at least one of these partitions approximately
obeys the requirements of the property in question. An important
point is that since the first sample is small (i.e., of
size poly(1=ffl)), the total number of partitions it induces is
only exp poly(1=ffl). Thus, the additional sample must approximate
only these many partitions (rather than all possible
partitions of the entire graph) and it suffices that this sample
be of size poly(1=ffl),
The difference between the various algorithms is in the way
in which partitions of the sample induce partitions of the entire
graph. The simplest case is in testing Bipartiteness. For a
partition of the sample, all vertices in the graph which
have a neighbor in S 1 are placed on one side, and the rest of the
vertices are placed on the other side. In the other algorithms
the induced partition is less straightforward. For example, in
case of ae-Clique, a partition (S 1 of the sample S with
induces a candidate clique roughly as follows.
Consider the set T of graph vertices each neighboring all of
Then the candidate clique consists of the aeN vertices with
the highest degree in the subgraph induced by T. In the, ae-
Cut, ae-Bisection and General Partition testing algorithms, we
use auxiliary guesses which are implemented by exhaustive
search.
1.3. Testing Graph Properties and Approximation
The relation of testing graph properties to approximation
is best illustrated in the case of Max-CUT. A tester for the
class ae-Cut, working in time T (ffl; N ), yields an algorithm for
approximating the maximum cut in an N -vertex graph, up to
additive error fflN 2 , in time 1
ffl \DeltaT (ffl; N ). Thus, for any constant
ffl ? 0, we can approximate the size of the max-cut to within
fflN 2 in constant time. This yields a constant time approximation
scheme (i.e., to within any constant relative error) for
dense graphs, improving on Arora et. al. [3] and de la Vega [17]
who solved this problem in polynomial-time (O(N 1=ffl 2
)-time
and exp( ~
In both works
the problem is solved by actually constructing approximate
max-cuts. Finding an approximate max-cut does not seem to
follow from the mere existence of a tester for ae-Cut; yet, as
mentioned above, our tester can be used to find such a cut in
time linear in N (i.e., ~
One can turn the question around and ask whether approximation
algorithms for dense instances can be transformed into
corresponding testers as defined above. In several cases this is
possible. For example, using some ideas from our work, the
Max-CUT algorithm of [17] can be transformed into a tester
of complexity comparable to ours. We do not know whether
the same is true with respect to the algorithms in [3]. Results
on testing graph properties can be derived also from work
by Alon et. al. [1]. That paper proves a constructive version
of the Regularity Lemma of Szemer-edi, and obtains from it
a polynomial-time algorithm that given an N -vertex graph,
finds a subgraph of size f(ffl; k) which
is not k-colorable, or omits at most fflN 2 edges and k-colors
the rest. Noga Alon has observed that the analysis can be modified
to yield that almost all subgraphs of size f(ffl; k) are not
k-colorable, which in turn implies a tester for k-Colorability.
In comparison with our k-Colorability Tester, which takes a
sample of O(k 2 log k=ffl 3 ) vertices, the k-colorability tester derived
(from [1]) takes a much bigger sample of size equaling a
tower of (k=ffl) 20 exponents (i.e., log   f(ffl;
A DIFFERENT NOTION OF APPROXIMATION FOR MAX-CLIQUE.
Our notion of ae-Clique Testing differs from the traditional notion
of Max-Clique Approximation. When we talk of testing
"ae-Cliqueness", the task is to distinguish the case in which an
N -vertex graph has a clique of size aeN from the case in which
it is ffl-far from the class of N -vertex graphs having a clique
of size aeN . On the other hand, traditionally, when one talks
of approximating the size of Max-Clique, the task is to distinguish
the case in which the max-clique has size at least aeN
from, say, the case in which the max-clique has size at most
aeN=2. Whereas the latter problem is NP-Hard, for ae - 1=64
(see [9, Sec. 3.9]), we've shown that the former problem can be
solved in exp(O(1=ffl 2 ))-time, for any ae; ffl ? 0. Furthermore,
Arora et. al. [3] showed that the "dense-subgraph" problem, a
generalization of ae-cliqueness, has a polynomial-time approximation
scheme (PTAS) for dense instances.
TESTING k-COLORABILITY VS. APPROXIMATING k-
COLORABILITY. Petrank has shown that it is NP-Hard to
distinguish 3-colorable graphs from graphs in which every
3-partition of the vertex set violates at least a constant fraction
of the edges [30]. In contrast, our k-Colorability Tester implies
that solving the same promise problem is easy for dense
graphs, where by dense graphs we mean N -vertex graphs
edges. This is the case since, for every ffl ? 0,
our tester can distinguish, in exp(k 2 =ffl 3 )-time, between k-
colorable N -vertex graphs and N -vertex graphs which remain
non-k-colorable even if one omits at most fflN 2 of their edges. 2
We note that deciding k-colorability even for N -vertex
graphs of minimum degree at least k\Gamma3
k\Gamma2 \Delta N is NP-complete
(cf., Edwards [18]). On the other hand, Edwards also gave
a polynomial-time algorithm for k-coloring k-colorable N -
vertex graphs of minimum degree at least ffN , for any constant
k\Gamma2 .
1.4. Other Related Work
PROPERTY TESTING IN THE CONTEXT OF PCP: Property testing
plays a central role in the construction of PCP systems. Specif-
ically, the property tested is being a codeword with respect to
a specific code. This paradigm explicitly introduced in [6] has
shifted from testing codes defined by low-degree polynomials
[6, 19, 5, 4] to testing Hadamard codes [4, 10, 11, 8], and
recently to testing the "long code" [9].
PROPERTY TESTING IN THE CONTEXTOF PROGRAM CHECKING:
There is an immediate analogy between program self-testing
[14] and property-testing with queries. The difference is that
in self-testing, a function f (represented by a program) is
tested for being close to a fully specified function g, whereas
in property-testing the test is whether f is close to any function
in a function class G. Interestingly, many self-testers [14, 36]
work by first testing that the program satisfies some properties
which the function it is supposed to compute satisfies
(and only then checking that the program satisfies certain constraints
specific to the function). Rubinfeld and Sudan [36]
defined property testing, under the uniform distribution and
using queries, and related it to their notion of Robust Char-
acterization. Rubinfeld [35] focuses on property testing as
applied to properties which take the form of functional equations
of various types.
PROPERTY TESTING IN THE CONTEXT OF LEARNING THEORY:
Departing from work in Statistics regarding the classification
of distributions (e.g., [24, 16, 41]), Ben-David [12] and Kulkarni
and Zeitouni [28] considered the problem of classifying an
unknown function into one of two classes of functions, given
labeled examples. Ben-David studied this classification problem
in the limit (of the number of examples), and Kulkarni and
Zeitouni studied it in a PAC inspired model. For any fixed ffl, the
problem of testing the class F with distance parameter ffl can
be casted as such a classification problem (with F and the set
of functions ffl-away from F being the two classes). A different
variant of the problem was considered by Yamanishi [39].
TESTING GRAPH PROPERTIES. Our notion of testing a graph
property P is a relaxation of the notion of deciding the graph
As noted by Noga Alon, similar results, alas with much worse dependence
on ffl, can be obtained by using the results of Alon et. al. [1].
property P which has received much attention in the last two
decades [29]. In the classical problem there are no margins
of error, and one is required to accept all graphs having property
P and reject all graphs which lack it. In 1975 Rivest and
Vuillemin [33] resolved the Aanderaa-Rosenberg Conjecture
[34], showing that any deterministic procedure for deciding
any non-trivial monotone N -vertex graph property must ex-
entries in the adjacency matrix representing the
graph. The query complexity of randomized decision procedures
was conjectured by Yao to be \Omega\Gamma N 2 ). Progress towards
this goal wasmade by Yao [40], King [27] and Hajnal [23] culminating
in an \Omega\Gamma N 4=3 ) lower bound. Our results, that some
non-trivial monotone graph properties can be tested by examining
a constant number of random locations in the matrix,
stand in striking contrast to all of the above.
APPROXIMATION IN DENSE GRAPHS. As stated previously,
Arora et. al. [3] and de la Vega [17] presented PTAS for dense
instances of Max-CUT. The approach of Arora et. al. uses
Linear Programming and Randomized Rounding, and applies
to other problems which can be casted as a "smooth" Integer
Programs. 3 The methods of de la Vega [17] are purely
combinatorial and apply also to similar graph partition prob-
lems. Following the approach of Alon et. al. [1], but using
a modification of the regularity Lemma (and thus obtaining
much improved running times), Frieze and Kannan [20] devise
PTAS for several graph partition problems such as Max-Cut
and Bisection. We note that compared to all the above re-
sults, our respective graph partitioning algorithms have better
running-times. Like de la Vega, our methods use elementary
combinatorial arguments related to the problem at hand.
Still our methods suffice for dealing with the General Graph
Partition Problem.
Important Note: In this extended abstract, we present
only two of our results on testing graph properties: the k-Colorability
and the ae-Clique testers. The definition and theorem
regarding the General Graph Partition property appears in
Subsection 3.3. All other results as well as proofs and further
details can be found in our report [22].
2. General Definitions and Observations
2.1. Definitions
fFng be a parameterized class of functions,
where the functions 4 in Fn are defined over f0; 1g n and let
be a corresponding class of distributions (i.e., Dn
is a distribution on f0; 1g n ). We say that a function f defined
on f0; 1g n is ffl-close to Fn with respect to Dn if there exists
a function g 2 Fn such that
3 In [2], the approach of [3] is extended to other problems, such as Graph
Isomorphism, using a new rounding procedure for the Assignment Problem.
4 The range of these functions may vary and for many of the results and
discussions it suffices to consider Boolean function.
Otherwise, f is ffl-far from Fn (with respect to Dn ).
We shall consider several variants of testing algorithms, where
the most basic one is defined as follows.
Definition 2.1 (property testing): Let A be an algorithm
which receives as input a size parameter n, a distance parameter
confidence Fixing
an arbitrary function f and distribution Dn over f0; 1g n ,
the algorithm is also given access to a sequence of f-labeled
examples, where each x i is independently
drawn from the distribution Dn . We say that A
is a property testing algorithm (or simply a testing algorithm) for
the class of functions F if for every n, ffl and ffi and for every
function f and distribution Dn over f0; 1g n the following
holds
with probability at least 1 \Gamma ffi (over the
examples drawn from Dn and the possible coins tosses
of A), A accepts f (i.e., outputs 1);
ffl if f is ffl-far from Fn (with respect to Dn ) then with
probability at least rejects f (i.e., outputs 0).
The sample complexity of A is a function of n; ffl and ffi bounding
the number of labeled examples examined by A on input
Though it was not stated explicitly in the definition, we shall
also be interested in bounding the running time of a property
testing algorithm (as a function of the parameters n; ffi; ffl, and
in some case of a complexity measure of the class F ). We
consider the following variants of the above definition: (1) Dn
may be a specific distribution which is known to the algorithm.
In particular, we shall be interested in testing with respect to the
uniform distribution; (2) Dn may be restricted to a known class
of distributions (e.g., product distributions); (3) The algorithm
may be given access to an oracle for the function f , which
when queried on x 2 f0; 1g n , returns f(x). In this case we
refer to the number of queries made by A (which is a function
of n, ffl, and ffi ), as the query complexity of A.
2.2. Property Testing and PAC Learning
A Probably Approximately Correct (PAC) learning algorithm
[37] works in the same framework as that described in
Definition 2.1 except for the following (crucial) differences:
(1) It is given a promise that the unknown function f (referred
to as the target function) belongs to F ; (2) It is required to
output (with probability at least
h which is ffl-close to f , where closeness is as defined in
Equation (1) (and ffl is usually referred to as the approximation
parameter). Note that the differences pointed out above
effect the tasks in opposite directions. Namely, the absence
of a promise makes testing potentially harder than learning,
whereas deciding whether a function belongs to a class rather
than finding the function may make testing easier.
In the learning literature, a distinction is made between
proper (or representation dependent) learning and non-proper
learning [31]. In the former model, the hypothesis output
by the learning algorithm is required to belong to the same
function class as the target function f , i.e. h 2 F , while in
the latter model, no such restriction is made. We stress that
a proper learning algorithm (for F ) may either halt without
output or output a function in F , but it may not output functions
not in F . 5 There are numerous variants of PAC learning
(including learning with respect to specific distributions, and
learning with access to an oracle for the target function f ).
Unless stated otherwise, whenever we refer in this section to
PAC learning we mean the distribution-free no-query model
described above. The same is true for references to property
testing. In addition, apart from one example, we shall restrict
our attention to classes of Boolean functions.
TESTING IS NOT HARDER THAN PROPER LEARNING.
Proposition 2.1 If a function class F has a proper learning
algorithm A, then F has a property testing algorithm A 0
such that mA 0 (n; ffl;
Furthermore, the same relation holds between the running
times of the two algorithm.
The proof of this proposition, as well as of all other propositions
in this section, can be found in our report [22]. The above
proposition implies that if for every n, Fn has polynomial (in
n) VC-dimension [38, 15], then F has a tester whose sample
complexity is poly(n=ffl) \Delta log(1=ffi). The reason is that classes
with polynomial VC-dimension can be properly learned from
a sample of the above size [15]. However, the running time of
such a proper learning algorithm, and hence of the resulting
testing algorithm might be exponential in n.
Corollary 2.2 Every class which is learnable with a
poly(n=ffl) sample is testable with a poly(n=ffl) sample (in
at most exponential time).
TESTING MAY BE HARDER THAN LEARNING. In contrast to
Proposition 2.1 and to Corollary 2.2, we show that there are
classes which are efficiently learnable (though not by a proper
learning algorithm) but are not efficiently testable. This is
proven by observing that many hardness results for proper
learning (cf. [31, 13, 32]) actually establish the hardness of
testing (for the same classes). Furthermore, we believe that
it is more natural to view these hardness results as referring
to testing. Thus, the separation between efficient learning
and efficient proper learning translates to a separation between
efficient learning and efficient testing.
5 We remark that in case the function is F have an easy to recognize
representation, one can easily guarantee that the algorithm never outputs a
function not in F . Standard classes considered in works on proper learning
typically have this feature.
Proposition 2.3 If NP 6ae BPP then there exist function
classes which are not poly(n=ffl)-time testable but are
poly(n=ffl)-time (non-properly) learnable.
We stress that while Proposition 2.1 generalizes to learning and
testing under specific distributions, and to learning and testing
with queries, the proof of Proposition 2.3 uses the premise
that the testing (or proper learning) algorithm works for any
distribution and does not make queries.
TESTING MAY BE EASIER THAN LEARNING.
Proposition 2.4 There exist function classes F such that F
has a property testing algorithm whose sample complexity and
running time are O(log(1=ffi)=ffl), yet any learning algorithm
for F must have sample complexity exponential in n.
The impossibility of learning the function class in Proposition
2.4 is due to its exponential VC-dimension, (i.e., it is a pure
information theoretic consideration). We now turn to function
classes of exponential (rather than double exponential) size.
Such classes are always learnable with a polynomial sample,
the question is whether they are learnable in polynomial-time.
We present a function class which is easy to test but cannot
be learned in polynomial-time (even under the uniform distri-
bution), provided trapdoor one-way permutations exist (e.g.,
factoring is intractable).
Proposition 2.5 If there exist trapdoor one-way permutations
then there exists a family of functions which can be tested in
poly(n=ffl)-time but can not be learned in poly(n=ffl)-time,
even with respect to the uniform distribution. Furthermore,
the functions can be computed by poly(n)-size circuits.
The class presented in Proposition 2.5 consists of multi-valued
functions. We leave it as an open problem whether a similar
result holds for a class of Boolean functions.
LEARNING AND TESTING WITH QUERIES (under the uniform
distribution). Invoking known results on linearity testing [14,
7, 19, 10, 11, 8] we conclude that there is a class of 2 n functions
which can be tested within query complexity O(log(1=ffi)=ffl),
and yet learning it requires at least n queries. Similarly, using
results on low-degree testing [7, 6, 21, 36], there is a class of
which can be tested within query complexity
O( log(1=ffi)
ffl \Delta n), and yet learning it requires exp(n) many
queries.
AGNOSTICLEARNING AND TESTING. In a variant of PAC learn-
ing, called Agnostic PAC learning [26], there is no promise
concerning the target function f . Instead, the learner is required
to output a hypothesis h from a certain hypothesis class
H, such that h is ffl-close to the function in H which is closest
to f . The absence of a promise makes agnostic learning
closer in spirit to property testing than basic PAC learning. In
particular, agnostic learning with respect to a hypothesis class
H implies proper learning of the class H and thus property
testing of H.
LEARNING AND TESTING DISTRIBUTIONS. The context of
learning (cf., [25]) and testing distributions offers a dramatic
demonstration to the importance of a promise (i.e., the fact that
the learning algorithm is required to work only when the target
belongs to the class, whereas the testing algorithm needs to
work for all targets which are either in the class or far away
from it).
Proposition 2.6 There exist distribution classes which are efficiently
learnable (in both senses mentioned above) but cannot
be tested with a subexponential sample (regardless of the
running-time).
3. Testing Graph Properties
We concentrate on testing graph properties using queries
and with respect to the uniform distribution.
We consider undirected, simple graphs (no multiple edges
or self-loops). For a simple graph G, we denote by V(G)
its vertex set and assume, without loss of generality, that
jV(G)jg. The graph G is represented by
the (symmetric) Boolean function
where g(u; only if there is an edge between u
and v in G. This brings us to associated undirected graphs
with directed graphs, where each edge in the undirected graph
is associated with a pair of anti-parallel edges. Specifically,
for a graph G, we denote by E(G) the set of ordered pairs
which correspond to edges in G (i.e., (u; v) 2 E(G) iff there
is an edge between u and v in G). The distance between
two N -vertex graphs, G 1 and G 2 , is defined as the number of
entries which are in the
symmetric difference of E(G 1 ) and E(G 2 ). We denote
This notation is extended naturally to a set, C, of N -vertex
graphs; that is, dist(G; C) )g.
3.1. Testing k-Colorability
In this subsection we present an algorithm for testing the
k-Colorability property for any given k. Namely, we are interested
in determining if the vertices of a graph G can be colored
by k colors so that no two adjacent vertices are colored by the
same color, or if any k-partition of the graph has at least fflN 2
violating edges (i.e. edges between pairs of vertices which
belong to the same side of the partition).
The test itself is straightforward. We uniformly select a
sample, denoted X, of O
vertices of the graph,
query all pairs of vertices in X to find which are edges in
G, and check if the induced subgraph is k-Colorable. In
lack of efficient algorithms for k-Colorability, for k - 3, we
use the obvious exponential-time algorithm on the induced
subgraph. The resulting algorithm is called the k-Colorability
Testing Algorithm. Towards analyzing it, we define violating
edges and good k-partitions. 6
Definition 3.1.1 (violating edges and good k-partitions): We
say that an edge (u; v) 2 E(G) is a violating edge with respect
to a k-partition
say that a k-partition is ffl-good if it has at most fflN 2 violating
edges (otherwise it is ffl-bad). The partition is perfect if it has
no violating edges.
Theorem 3.1 The k-Colorability Testing Algorithm is a property
testing algorithm for the class of k-Colorable graphs whose
query complexity is poly(k log(1=ffi)=ffl) and whose running
time is exponential in its query complexity. If the tested graph
G is k-Colorable, then it is accepted with probability 1, and
with probability at least 1 \Gamma ffi (over the choice of the sampled
vertices), it is possible to construct an ffl-good k-partition of
V(G) in time poly(k log(1=ffi)=ffl) \Delta jV(G)j.
Proof: If G is k-Colorable then every subgraph of G is k-
Colorable, and hence G will always be accepted. The crux
of the proof is to show that every G which is ffl-far from the
class of k-Colorable graphs, denoted G k , is rejected with probability
at least We establish this claim by proving its
counter-positive. Namely, that every G which is accepted with
probability greater than ffi , must have an ffl-good k-partition
(and is thus ffl-close to G k ). This is done by giving a (construc-
tive) proof of the existence of an ffl-good k-partition of V(G).
Hence, in case G 2 G k , we also get an efficient probabilistic
procedure for finding an ffl-good k-partition of V(G). Note
that if the test rejects G then we have a certificate that
in form of the (small) subgraph induced by X which is not
k-colorable.
We view the set of sampled vertices X as a union of two
disjoint sets U and S, where U is a union of ' (disjoint) sets
, each of size m. The size of S is m as well, where
4k=ffl. The set U (or rather
a k-partition of U) is used to define a k-partition of V(G).
The set S ensures that with high probability, the k-partition of
U which is induced by the perfect k-partition of
defines an ffl-good partition of V(G).
In order to define a k-partition of V(G) given a k-partition
of U, we first introduce the notion of a clustering of the vertices
in V(G) with respect to this partition of U. More precisely,
we define the clustering based on the k-partition of a subset
U, where this partition, denoted (U 0
k ), is the
one induced by the k-partition of U. The clustering is defined
so that vertices in the same cluster have neighbors on the
6 k-partitions are associated with mappings of the vertex set into the canonical
k-element set [k]. The partition associated with
shall use the mapping notation
-, and the explicit partition notation
same sides of the partition of U 0 . For every A ' [k], the A-
cluster, denoted CA , contains all vertices in V(G) which have
neighbors in U 0
i for every i 2 A (and do not have neighbors in
the other U 0
's). The clusters impose restrictions on possible
extensions of the partition of U 0 to partitions
of all V(G), which do not have violating edges incident to
vertices in U 0 . Namely, vertices in CA should not be placed
in any V i such that i 2 A. As a special case, C ; is the set of
vertices that do not have any neighbors in U 0 (and hence can
be put on any side of the partition). In the other extreme, C [k]
is the set of vertices that in any extension of the partition of U 0
will cause violations. For each i, the vertices in C [k]nfig are
forced to be put in V i , and thus are easy to handle. It is more
difficult to deal with the the clusters CA where jAj
Definition 3.1.2 (clusters): Let U 0 be a set of vertices, and
let - 0 be a perfect k-partition of U 0 . Define U 0
ig. For each subset A ' [k] we define the A-cluster
with respect to - 0 as follows:
The relevance of the above clusters becomes clear given the
following definitions of extending and consistent partitions.
Definition 3.1.3 (consistent extensions): Let U 0 and - 0 be as
above. We say that a k-partition - of V(G) extends a k-partition
- 0 of U 0 if
extended partition - is consistent with - 0 if -(v) 6= - 0 (u) for
every is the [k]-cluster
Thus, each vertex v in the cluster CA (w.r.t - 0 defined on
forced to satisfy -(v) 2 -
every k-partition
- which extends - 0 in a consistent manner. There
are no restrictions regarding vertices in C ; and vertices in
C [k] (the latter is guaranteed artificially in the definition and
the consequences will have to be treated separately). For
the consistency condition forces
We now focus on the main problem of the analysis. Given
a k-partition of U, what is a good way to define a k-partition
of V(G)? Our main idea is to claim that with high probability
the set U contains a subset U 0 so that the clusters with respect
to the induced k-partition of U 0 determine whatever needs
to be determined. That is, if these clusters allow to place
some vertex on a certain side of the partition, then doing so
does not introduce too many violating edges. The first step in
implementing this idea is the notion of a restricting vertex.
Definition 3.1.4 (restricting vertex): A pair (v; i), where
is said to be restricting with respect
to a k-partition - 0 (of U 0 ) if v has at least ffl
neighbors
7 In the Bipartite case, this is easy too (since C ; is likely to contain few
vertices of high degree).
in [B:i= 2B CB . Otherwise, (v; i) is non-restricting. A vertex
restricting with respect to - 0 if
for every
A the pair (v; i) is restricting. Otherwise, v is
non-restricting. As always, the clusters are with respect to - 0 .
Thus, a vertex v 2 CA is restricting if for every
adding
v to U 0
(and thus to U 0 ) will cause may of its neighbors to
move to a cluster corresponding to a bigger subset. That is,
v's neighbors in the B-cluster (w.r.t (U 0
move to
the (B [ fig)-cluster (w.r.t (U 0
Given a prefect k-partition of U, we construct U 0 in steps
starting with the empty set. At step j we add to U 0 a vertex
which is a restricting
vertex with respect to the k-partition of the current set U 0 . If
no such vertex exists, the procedure terminates. When the
procedure terminates (and as we shall see it must terminate
after at most ' steps), we will be able to define, based on the
k-partition of the final U 0 , an ffl-good k-partition of V(G). The
procedure defined below is viewed at this point as a mental
experiment. Namely, it is provided in order to show that with
high probability there exists a subset U 0 of U with certain
desired properties (which we later exploit).
Restriction Procedure (Construction of U 0 )
Input: a perfect k-partition of
1. U 0 ;.
2. For do the following. Consider the current
set U 0 and its partition - 0 (induced by the perfect k-partition
of U).
ffl If there are less than (ffl=8)N restricting vertices with
respect to - 0 then halt and output U 0 .
ffl If there are at least (ffl=8)N restricting vertices but
there is no restricting vertex in U j , then halt and output
error.
ffl Otherwise (there is a restricting vertex in U j ), add the
first (by any fixed order) restricting vertex to U 0 .
3.1.5 For every U and a perfect k-partition of U, after
at most iterations, the Restriction Procedure halts
and outputs either U 0 or error.
The proof of this claim, as well as all other missing proofs, can
be found in our report [22]. Before we show how U 0 can be
used to define a k-partition - of V(G), we need to ensure that
with high probability, the restriction procedure in fact outputs
a set U 0 and not error. To this end, we first define the notion of
a covering set.
Definition 3.1.6 (covering sets - for k-coloring): We say that
U is a covering set for V(G), if for every perfect k-partition
of U, the Restriction Procedure, given this partition as input,
halts with an output U 0 ae U (rather than an error message).
In other words, U is such that for every perfect k-partition of
U and for each of the at most ' iterations of the procedure, if
there exist at least (ffl=8)N restricting vertices with respect to
the current partition of U 0 , then U j will include at least one
such restricting vertex.
Lemma 3.1.7 With probability at least 1 \Gamma ffi, a uniformly
chosen set of size ' \Delta
is a covering set.
Definition 3.1.8 (closed partitions): Let U 0 be a set and - 0 a
k-partition of it. We call (U closed if there are less than
(ffl=8)N restricting vertices with respect to - 0 .
Clearly, if the Restriction Procedure outputs a set U 0 then this
set together with its (induced) partition are closed. If (U
is closed, then most of the vertices in V(G) are non-restricting.
Recall that a non-restricting vertex v, belonging to a cluster
[k], has the following property. There exists at least
one index
A, such that (v; i) is non-restricting. It follows
from Definition 3.1.4 that for every consistent extension of - 0
to - which satisfies there are at most fflN violating
edges incident to v. 8 However, even if v is non-restricting
there might be indices
A such that (v; i) is restricting, and
hence there may exist a consistent extensions of - 0 to - which
in which there are more than ffl
violating
edges incident to v. Therefore, we need to define for each
vertex its set of forbidden indices which will not allow to have
restricting pair (v; i).
Definition 3.1.9 (forbidden sets): Let (U closed and
consider the clusters with respect to - 0 . For each v 2 V(G) n
U 0 we define the forbidden set of v, denoted F v , as the smallest
set satisfying
ffl For every
if v has at least (ffl=4)N neighbors in
the clusters CB for which
2 B, then i is in F v .
For
Lemma 3.1.10 Let (U be an arbitrary closed pair and
's be as in Definition 3.1.9. Then:
8 N .
2. Let - be any k-partition of V(G)
that
Then, the number
of edges (v; v 0 is at
most (ffl=2)N 2 .
First note that by definition of a consistent extension no vertex in cluster
CB , where i 2 B, can have -value i. Thus, all violated edges incident to v
are incident to vertices in clusters CB so that
B. Since the pair (v; i) is
non-restricting, there are at most fflN such edges.
The lemma can be thought of as saying that any k-partition
which respects the forbidden sets is good (i.e., does not have
many violating edges). However, the partition applies only
to vertices for which the forbidden set is not [k]. The first
item tells us that there cannot be many such vertices which
do not belong to the cluster C [k] . We next show that, with
high probability over the choice of S, the k-partition - 0 of U 0
(induced by the k-partition of U[S) is such that C [k] is small.
This implies that all the vertices in C [k] (which were left out
of the partition in the previous lemma) can be placed in any
side without contributing too many violating edges (which are
incident to them).
Definition 3.1.11 (useful k-partitions): We say that a pair
8 N . Otherwise it is ffl-unuseful.
The next claim directly follows from our choice of m and the
above definition.
3.1.12 Let U 0 be a fixed set of size ' and - 0 be a fixed
k-partition of U 0 so that (U S be a
uniformly chosen set of size m. Then, with probability at
least ffik \Gamma' , there exists no perfect k-partition of U 0 [ S which
extends - 0 .
The following is a corollary to the above claim and to the fact
that the number of possible closed pairs (U
by all possible k-partitions of U is at most k ' .
Corollary 3.1.13 If all closed pairs (U are determined
by all possible k-partitions of U are unuseful, then with
probability at least over the choice of S, there is no
perfect k-partition of
We can now wrap up the proof of Theorem 3.1. If G is
accepted with probability greater than ffi , then by Lemma 3.1.7,
the probability that it is accepted and U is a covering set is
greater than ffi =2. In particular, there must exist at least one
covering set U, such that if U is chosen then G is accepted
with probability greater than ffi =2 (with respect to the choice
of S). That is, (with probability greater than ffi =2) there exists
a perfect partition of U [ S. But in such a case (by applying
Corollary 3.1.13), there must be a useful closed pair (U
(where U 0 ae U). If we now partition V(G) as described in
Lemma 3.1.10, where vertices with forbidden set [k] are placed
arbitrarily, then from the two items of Lemma 3.1.10 and the
usefulness of (U that there are at most fflN 2
violating edges with respect to this partition. This completes
the main part of the proof. (Theorem 3.1)
3.2. Testing Max-Clique
Let !(G) denote the size of the largest clique in graph G,
and C ae
jV(G)jg be the set of graphs
having cliques of density at least ae. The main result of this
subsection is:
Theorem 3.2 Let ' There exists a property
testing algorithm, A, for the class C ae whose edge-query complexity
is O(' 2 ae 2 =ffl 6 ) and whose running time is exp('ae=ffl 2 ).
In particular, A uniformly selects O(' 2 ae 2 =ffl 4 ) vertices in G
and queries the oracle only on the existence of edges between
these vertices. In case G 2 C ae , one can also retrieve in time
set of ae \Delta jV(G)j vertices in G which
is almost a clique (in the sense that it lacks at most ffl \Delta jV(G)j 2
edges to being a clique).
Theorem 3.2 is proven by presenting a seemingly unnatural
algorithm/tester (see below). However, as a corollary, we
observe that "the natural" algorithm, which uniformly selects
poly(log(1=ffi)=ffl) many vertices and accepts iff they induce a
subgraph with a clique of density ae \Gamma ffl
2 , is a valid C ae -tester as
well.
Corollary 3.3 Let R be a uniformly
selected set of m vertices in V (G). Let GR be the subgraph
(of G) induced by R. Then,
2In the rest of this subsection we provide a motivating discussion
to the algorithm asserted in Theorem 3.2. Recall that
jV(G)j denotes the number of vertices in G.
Our first idea is to select at random a small sample U
of V(G) and to consider all subsets U 0 of size ae\Delta jUj of
U where poly(1=ffl). For each U 0 let T(U 0 ) be the
set of all vertices which neighbor every vertex in U 0 (i.e.,
\Gamma(u)). In the subgraph induced by T(U 0 ),
consider the set Y(U 0 ) of aeN vertices with highest degree in
the induced subgraph. Clearly, if G is ffl-far from C ae , then
at least fflN 2 edges to being a clique (for every
choice of U and U 0 ). On the other hand, we show that if G has a
clique C of size aeN then, with high probability over the choice
of U, there exists a subset U 0 ae U such that Y(U 0 ) misses at
most (ffl=3)N 2 to being a clique (in particular, U
will do).
Assume that for any fixed U 0 we could sample the vertices
in Y(U 0 ) and perform edge queries on pairs of vertices in this
sample. Then, a sample of O(t=ffl 2 ) vertices (where
suffices for approximating the edge density in Y(U 0 ) to within
an ffl=3 fraction with probability In particular a
sample can distinguish between a set Y(U 0 ) which is far from
being a clique and a set Y(U 0 ) which is almost a clique. The
point is that we need only consider
possible sets
is only a polynomial in 1=ffl.
The only problem which remains is how to sample from
Certainly, we can sample sampling
V(G) and testing membership in T, but how do we decide
which vertex is among those of highest degree? The first idea
is to estimate the degrees of vertices in T using an additional
sample, denoted W. Thus, instead of considering the aeN
vertices of highest degree in T, we consider the aeN vertices
in T having the most neighbors in T " W. The second idea is
that we can sample T, order vertices in this sample according
to the number of neighbors in T " W, and take the ae fraction
with the most such neighbors.
3.3. The General Partition Problem
The following General Graph Partition property generalizes
all properties considered in previous subsections. In particular,
it captured any graph property which requires the existence of
partitions satisfying certain fixed density constraints. These
constraints may refer both to the number of vertices on each
side of the partition and to the number of edges between each
pair of sides.
ae lb
be a set of
non-negative parameters so that ae lb
GP \Phi be the class of graphs which have a
k-way partition
denotes the set of edges with one endpoint
in V j and one in V j 0
. That is, Eq. (3) places lower and
upper bounds on the relative sizes of the various parts; whereas
Eq. (4) imposes lower and upper bounds on the density of edges
among the various pairs of parts. For example, k-colorability is
expressed by setting % ub
setting ae lb
ae ub
similarly setting the % xx
's for j 0 6= j).
Theorem 3.4 There exists an algorithm A such that for every
given set of parameters \Phi, algorithm A is a property
testing algorithm for the class GP \Phi with query complexity
log(k=fflffi), and running time
exp
Recall that better complexities for Max-CUT and Bisection
(as well as for k-Colorability and ae-Clique), are obtained by
custom-made algorithms.

Acknowledgments

We wish to thank Noga Alon, Ravi Kannan, David Karger
and Madhu Sudan for useful discussions.



--R

The algorithmic aspects of the regularity lemma.
A new rounding procedure for the assignment problem with applications to dense graph arrangement problems.
Polynomial time approximation schemes for dense instances of NP-hard problems
Proof verification and intractability of approximation problems.
Probabilistic checkable proofs: A new characterization of NP.
Checking computations in polylogarithmic time.

Linearity testing in characteristic two.
Free bits
Efficient probabilistically checkable proofs and applications to approximation.
Improved non-approximability results
Can finite samples detect singularities of real-valued functions? In 24th STOC
Training a 3-node neural network is NP-complete

Learnability and the Vapnik-Chervonenkis dimension
On determining the rationality of the mean of a random variable.

The complexity of colouring problems on dense graphs.
Approximating clique is almost NP-complete
The regularity lemma and approximation schemes for dense problems.

Property testing and its connection to learning and approximation.

Distinguishability of sets of distributions.
On the learnability of discrete distributions.
Toward efficient agnostic learning.

On probably correct classification of concepts.
Lecture notes on evasiveness of graph properties.
The hardness of approximations: Gap location.
Computational limitations on learning from examples.
The minimum consistent DFA problem cannot be approximated within any polynomial.
On recognizing graph properties from adjacency matrices.
On the time required to recognize properties of graphs: A problem.
Robust functional equations and their applications to program testing.
Robust characterization of polynomials with applications to program testing.
A theory of the learnable.
On the uniform convergence of relative frequencies of events to their probabilities.
Probably almost discriminative learning.
Lower bounds to randomized algorithms for graph properties.
A general classification rule for probability mea- sures
--TR
A theory of the learnable
Using dual approximation algorithms for scheduling problems theoretical and practical results
The complexity of colouring problems on dense graphs
A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach
Computational limitations on learning from examples
Learnability and the Vapnik-Chervonenkis dimension
Training a 3-node neural network in NP-complete
Checking computations in polylogarithmic time
Self-testing/correcting for polynomials and for approximate functions
Approximating clique is almost NP-complete (preliminary version)
Can finite samples detect singularities of real-valued functions?
Toward efficient agnostic learning
The minimum consistent DFA problem cannot be approximated within any polynomial
Small-bias probability spaces
Efficient probabilistically checkable proofs and applications to approximations
On probably correct classification of concepts
Self-testing/correcting with applications to numerical problems
The algorithmic aspects of the regularity lemma
Improved non-approximability results
On the learnability of discrete distributions
The hardness of approximation
Probably Almost Discriminative Learning
Polynomial time approximation schemes for dense instances of <italic>NP</italic>-hard problems
MAX-CUT has a randomized approximation scheme in dense graphs
Testing of the long code and hardness for clique
Adaptively secure multi-party computation
Some optimal inapproximability results
Property testing in bounded degree graphs
Spot-checkers
A sublinear bipartiteness tester for bounded degree graphs
Recycling queries in PCPs and in linearity tests (extended abstract)
Testing problems with sub-learning sample complexity
Fast Probabilistic Algorithms for Verification of Polynomial Identities
Robust Characterizations of Polynomials withApplications to Program Testing
Linearity testing in characteristic two
Free bits, PCPs and non-approximability-towards tight results
Clique is hard to approximate within n1-
A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
The regularity lemma and approximation schemes for dense problems
Probabilistically checkable proofs and the testing of hadamard-like codes

--CTR
Michal Parnas , Dana Ron , Ronitt Rubinfeld, Testing membership in parenthesis languages, Random Structures & Algorithms, v.22 n.1, p.98-138, January
Oren Ben-Zwi , Oded Lachish , Ilan Newman, Lower bounds for testing Euclidean Minimum Spanning Trees, Information Processing Letters, v.102 n.6, p.219-225, June, 2007
Michal Parnas , Dana Ron, Testing the diameter of graphs, Random Structures & Algorithms, v.20 n.2, p.165-183, March 2002
Hana Chockler , Dan Gutfreund, A lower bound for testing juntas, Information Processing Letters, v.90 n.6, p.301-305,
Uriel Feige , Gideon Schechtman, On the integrality ratio of semidefinite relaxations of MAX CUT, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.433-442, July 2001, Hersonissos, Greece
J. Feigenbaum , S. Kannan , M. Strauss , M. Viswanathan, Testing and spot-checking of data streams (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.165-174, January 09-11, 2000, San Francisco, California, United States
Eldar Fischer, Testing graphs for colorable properties, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.873-882, January 07-09, 2001, Washington, D.C., United States
Eldar Fischer, The difficulty of testing for isomorphism against a graph that is given in advance, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Oded Goldreich , Luca Trevisan, Three theorems regarding testing graph properties, Random Structures & Algorithms, v.23 n.1, p.23-57, August
Nir Ailon , Bernard Chazelle, Information theory in property testing and monotonicity testing in higher dimension, Information and Computation, v.204 n.11, p.1704-1717, November 2006
Gunnar Andersson , Lars Engebretsen, Property testers for dense constraint satisfaction programs on finite domains, Random Structures & Algorithms, v.21 n.1, p.14-32, August 2002
Beate Bollig , Ingo Wegener, Functions that have read-once branching programs of quadratic size are not necessarily testable, Information Processing Letters, v.87 n.1, p.25-29, July
Uriel Feige , Gideon Schechtman, On the optimality of the random hyperplane rounding technique for max cut, Random Structures & Algorithms, v.20 n.3, p.403-440, May 2002
Kenji Obata, Approximate max-integral-flow/min-multicut theorems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Nir Ailon , Bernard Chazelle , Seshadhri Comandur , Ding Liu, Estimating the distance to a monotone function, Random Structures & Algorithms, v.31 n.3, p.371-383, October 2007
Eli Ben-Sasson , Prahladh Harsha , Sofya Raskhodnikova, Some 3CNF properties are hard to test, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Alon , W. Fernandez de la Vega , Ravi Kannan , Marek Karpinski, Random sampling and approximation of MAX-CSP problems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
Eldar Fischer, On the strength of comparisons in property testing, Information and Computation, v.189 n.1, p.107-116, 25 February 2004
Alon , Asaf Shapira, Testing satisfiability, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.645-654, January 06-08, 2002, San Francisco, California
Alon, Testing subgraphs in large graphs, Random Structures & Algorithms, v.21 n.3-4, p.359-370, October 2002
Eldar Fischer , Ilan Newman, Testing versus estimation of graph properties, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
Hana Chockler , Orna Kupferman, -Regular languages are testable with a constant number of queries, Theoretical Computer Science, v.329 n.1-3, p.71-92, 13 December 2004
Eldar Fischer , Arie Matsliah, Testing graph isomorphism, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.299-308, January 22-26, 2006, Miami, Florida
Artur Czumaj , Christian Sohler, Estimating the weight of metric minimum spanning trees in sublinear-time, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Eldar Fischer , Ilan Newman, Testing of matrix properties, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.286-295, July 2001, Hersonissos, Greece
Alon , Asaf Shapira, Testing satisfiability, Journal of Algorithms, v.47 n.2, p.87-103, July
Ioannis Giotis , Venkatesan Guruswami, Correlation clustering with a fixed number of clusters, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1167-1176, January 22-26, 2006, Miami, Florida
Michal Parnas , Dana Ron, Testing metric properties, Information and Computation, v.187 n.2, p.155-195, 15 December
Christian Borgs , Jennifer Chayes , Lszl Lovsz , Vera T. Ss , Balzs Szegedy , Katalin Vesztergombi, Graph limits and parameter testing, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Ccile Germain-Renaud , Dephine Monnier-Ragaigne, Grid result checking, Proceedings of the 2nd conference on Computing frontiers, May 04-06, 2005, Ischia, Italy
Robert Krauthgamer , Ori Sasson, Property testing of data dimensionality, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
Eldar Fischer , Guy Kindler , Dana Ron , Shmuel Safra , Alex Samorodnitsky, Testing juntas, Journal of Computer and System Sciences, v.68 n.4, p.753-787, June 2004
Beate Bollig, A large lower bound on the query complexity of a simple boolean function, Information Processing Letters, v.95 n.4, p.423-428, 31 August 2005
Alon , Asaf Shapira, Linear equations, arithmetic progressions and hypergraph property testing, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
Michal Parnas , Dana Ron, Testing metric properties, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.276-285, July 2001, Hersonissos, Greece
Y. Kohayakawa , V. Rdl , L. Thoma, An optimal algorithm for checking regularity: (extended abstract), Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.277-286, January 06-08, 2002, San Francisco, California
Artur Czumaj , Christian Sohler, Soft kinetic data structures, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.865-872, January 07-09, 2001, Washington, D.C., United States
Eli Ben-Sasson , Oded Goldreich , Prahladh Harsha , Madhu Sudan , Salil Vadhan, Robust pcps of proximity, shorter pcps and applications to coding, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Cristina Bazgan , W. Fernandez de la Vega , Marek Karpinski, Polynomial time approximation schemes for dense instances of minimum constraint satisfaction, Random Structures & Algorithms, v.23 n.1, p.73-91, August
Eldar Fischer , Eric Lehman , Ilan Newman , Sofya Raskhodnikova , Ronitt Rubinfeld , Alex Samorodnitsky, Monotonicity testing over general poset domains, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
Eldar Fischer , Ilan Newman , Ji Sgall, Functions that have read-twice constant width branching programs are not necessarily testable, Random Structures & Algorithms, v.24 n.2, p.175-193, March 2004
P. Drineas , A. Frieze , R. Kannan , S. Vempala , V. Vinay, Clustering Large Graphs via the Singular Value Decomposition, Machine Learning, v.56 n.1-3, p.9-33
Harry Buhrman , Lance Fortnow , Ilan Newman , Hein Rhrig, Quantum property testing, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
Eli Ben-Sasson , Madhu Sudan , Salil Vadhan , Avi Wigderson, Randomness-efficient low degree tests and short PCPs via epsilon-biased sets, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Nikhil Bansal , Avrim Blum , Shuchi Chawla, Correlation Clustering, Machine Learning, v.56 n.1-3, p.89-113
Gereon Frahling , Christian Sohler, Coresets in dynamic geometric data streams, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
Abraham D. Flaxman , Alan M. Frieze, The diameter of randomly perturbed digraphs and some applications, Random Structures & Algorithms, v.30 n.4, p.484-504, July 2007
Ravi Kumar , Ronitt Rubinfeld, Algorithms column: sublinear time algorithms, ACM SIGACT News, v.34 n.4, December
W. Fernandez de la Vega , Marek Karpinski , Claire Kenyon , Yuval Rabani, Approximation schemes for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
V. Rdl , M. Schacht, Property testing in hypergraphs and the removal lemma, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
Viraj Kumar , Mahesh Viswanathan, Conformance testing in the presence of multiple faults, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
Michael A. Bender , Dana Ron, Testing properties of directed graphs: acyclicity and connectivity, Random Structures & Algorithms, v.20 n.2, p.184-205, March 2002
Alon , Asaf Shapira, Every monotone graph property is testable, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
Michal Parnas , Dana Ron , Ronitt Rubinfeld, Tolerant property testing and distance approximation, Journal of Computer and System Sciences, v.72 n.6, p.1012-1042, September 2006
Artur Czumaj , Funda Ergn , Lance Fortnow , Avner Magen , Ilan Newman , Ronitt Rubinfeld , Christian Sohler, Sublinear-time approximation of Euclidean minimum spanning tree, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
Ccile Germain-Renaud , Nathalie Playez, Result checking in global computing systems, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA
Alon , Asaf Shapira, Testing subgraphs in directed graphs, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Oded Goldreich , Madhu Sudan, Locally testable codes and PCPs of almost-linear length, Journal of the ACM (JACM), v.53 n.4, p.558-655, July 2006
Oded Goldreich, Property testing in massive graphs, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
Fast approximate probabilistically checkable proofs, Information and Computation, v.189 n.2, p.135-159, March 15, 2004
Fast approximate PCPs, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.41-50, May 01-04, 1999, Atlanta, Georgia, United States
M. Kiwi, Algebraic testing and weight distributions of codes, Theoretical Computer Science, v.299 n.1-3, p.81-106,
Artur Czumaj , Christian Sohler, Testing hypergraph colorability, Theoretical Computer Science, v.331 n.1, p.37-52, 15 February 2005
Asaf Shapira, A combinatorial characterization of the testable graph properties: it's all about regularity, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Nina Mishra , Dana Ron , Ram Swaminathan, A New Conceptual Clustering Framework, Machine Learning, v.56 n.1-3, p.115-151
approximation algorithms;computational learning theory;graph algorithms