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.