A distance-approximation algorithm for a graph property P in the adjacency-matrix model is given an approximation parameter epsilon and query access to the adjacency matrix of a graph G=(V,E). It is required to output an estimate of the distance between G and the closest graph G'=(V,E') that satisfies P, where the distance between graphs is the size of the symmetric difference between their edge sets, normalized by |V|^2.

In this talk I will introduce "property covers" as a framework for using distance-approximation algorithms for "simple" properties to design distance-approximation algorithms for more "complex" properties.  Applying this framework allows us to obtain efficient distance-approximation algorithms for several natural properties. The complexities of the algorithms essentially match the corresponding known results for testing these properties and provide an exponential improvement on previously known results.

Based on joint work with Nimrod Fiat