---
res:
  bibo_abstract:
  - "Property testing is a relaxation of classical decision problems which aims at
    distinguishing between functions having a predetermined property and functions
    being far from any function having the property. In this paper we present a novel
    framework for analyzing property testing algorithms. Our framework is based on
    a connection of property testing and a new class of problems which we call abstract
    combinatorial programs . We show that if the problem of testing a property can
    be reduced to an abstract combinatorial program of small dimension , then the
    property has an efficient tester.\r\n\r\nWe apply our framework to a variety of
    problems. We present efficient property testing algorithms for geometric clustering
    problems, for the reversal distance problem, and for graph and hypergraph coloring
    problems. We also prove that, informally, any hereditary graph property can be
    efficiently tested if and only if it can be reduced to an abstract combinatorial
    program of small size.\r\n\r\nOur framework allows us to analyze all our testers
    in a unified way, and the obtained complexity bounds either match or improve the
    previously known bounds. Furthermore, even if the asymptotic complexity of the
    testers is not improved, the obtained proofs are significantly simpler than the
    previous ones. We believe that our framework will help to understand the structure
    of efficiently testable properties.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Artur
      foaf_name: Czumaj, Artur
      foaf_surname: Czumaj
  - foaf_Person:
      foaf_givenName: Christian
      foaf_name: Sohler, Christian
      foaf_surname: Sohler
  bibo_doi: 10.1137/s009753970444199x
  bibo_issue: '3'
  bibo_volume: 34
  dct_date: 2005^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/0097-5397
  - http://id.crossref.org/issn/1095-7111
  dct_language: eng
  dct_title: Abstract Combinatorial Programs and Efficient Property Testers@
...