We consider the question of determining whether
a given object has a predetermined property or is ``far'' from any
object having the property.
Specifically, objects are modeled by functions,
and distance between functions is measured as the fraction
of the domain on which the functions differ.
We consider (randomized) algorithms which may query the function
at arguments of their choice, and seek algorithms which query the
function at relatively few places.
We focus on combinatorial properties, and specifically on graph properties.
The two standard representations of graphs --
by adjacency matrices and by incidence lists --
yield two different models for testing graph properties.
In the first model, most appropriate for dense graphs,
distance between $N$-vertex graphs is measured as the fraction
of edges on which the graphs disagree over $N^2$.
In the second model, most appropriate for bounded-degree graphs,
distance between $N$-vertex $d$-degree graphs is measured as the fraction
of edges on which the graphs disagree over $dN$.
To illustrate the two models, we survey results regarding the complexity
of testing whether a graph is Bipartite.
For a constant distance parameter,
a constant number of queries suffice in the first model,
whereas ${\widetilde\Theta}(\sqrt{N})$ queries are necessary
and sufficient in the second model.
The conjecture mentioned in section 1.3 has been resolved.
Thus, we present a (randomized) test for monotoncity of Boolean functions:
Given the ability to query an unknown
function $f:\bitset^n\mapsto\bitset$ at arguments of its choice,
the test always accepts a monotone $f$,
and rejects with high probability any function which is $/\e$-far
from being monotone. The complexity of the test is $\poly(n/\e)$.
The analysis of our algorithm relates two natural
combinatorial quantities
that can be measured with respect to a Boolean function;
one being global to the function and the other being local to it.
We also consider the problem of testing monotonicity
based only on random examples labeled by the function.
We show an $\Omega(\sqrt{2^n/\e})$ lower bound on the number
of required examples, and provide a matching upper bound
(via an algorithm).
