Abstract Combinatorial Programs and Efficient Property Testers

testing algorithms. Our framework is based on a connection of property
testing with a generalization of linear programming which we call
Abstract Combinatorial Programming. We show that if the problem of
testing a property can be reduced (this reduction should preserves
some structure) into an abstract combinatorial of small dimension,
then the property has an efficient tester.

Our framework can be applied to a variety of problems. We use it to
obtain efficient property testing algorithms for clustering problems,
for graph and hypergraph coloring problems, and for the reversal
distance problems. We also show that any heridatary graph property can
be tested with the complexity independent of the size of the input
graph if and only if it can be reduced to an abstract combinatorial
program of constant size.

All our testers are analyzed in our framework in a unified way and the
obtained complexity bounds either match or improve the previously
known bounds. We believe that our framework will help in better
understanding the structure of efficiently testable properties.

Joint work with C. Sohler (University of Paderborn, Germany)