__
TR97-056 | 1st December 1997 00:00
__

#### Combinatorial Property Testing (a survey).

**Abstract:**
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.

__
Comment #1 to TR97-056 | 4th September 1998 08:49
__
#### On Testing Monotonicity. Comment on: TR97-056.

**Abstract:**
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).