#### Milestone Year

### 1996

#### Property Testing: Ultra-fast approximate decisions

Can one determine whether or not a given object
has a predetermined property without inspecting all of it?
For natural properties (which contain no redundancy),
the answer is negative, but when introducing
a suitable relaxation the answer may become positive.
The relaxation is that one is only required to distinguish objects
that have the property from objects that are "far" from
any object that has the property.

A systematic study of such approximate decision algorithms
was initiated by WIS scientists and a collaborator,
with a focus on properties of graphs.
They showed that many natural graph properties can be tested in
this sense by probing the graph at a number of locations that
is independent of the size of the graph. The number of probes
only depends on the proximity parameter which determines
when two graphs are considered far apart.

Subsequently, WIS scientists made numerous important contributions
to the study of property testing.