---
_id: '18763'
abstract:
- lang: eng
  text: "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."
author:
- first_name: Artur
  full_name: Czumaj, Artur
  last_name: Czumaj
- first_name: Christian
  full_name: Sohler, Christian
  last_name: Sohler
citation:
  ama: Czumaj A, Sohler C. Abstract Combinatorial Programs and Efficient Property
    Testers. <i>SIAM Journal on Computing</i>. 2005;34(3):580-615. doi:<a href="https://doi.org/10.1137/s009753970444199x">10.1137/s009753970444199x</a>
  apa: Czumaj, A., &#38; Sohler, C. (2005). Abstract Combinatorial Programs and Efficient
    Property Testers. <i>SIAM Journal on Computing</i>, <i>34</i>(3), 580–615. <a
    href="https://doi.org/10.1137/s009753970444199x">https://doi.org/10.1137/s009753970444199x</a>
  bibtex: '@article{Czumaj_Sohler_2005, title={Abstract Combinatorial Programs and
    Efficient Property Testers}, volume={34}, DOI={<a href="https://doi.org/10.1137/s009753970444199x">10.1137/s009753970444199x</a>},
    number={3}, journal={SIAM Journal on Computing}, author={Czumaj, Artur and Sohler,
    Christian}, year={2005}, pages={580–615} }'
  chicago: 'Czumaj, Artur, and Christian Sohler. “Abstract Combinatorial Programs
    and Efficient Property Testers.” <i>SIAM Journal on Computing</i> 34, no. 3 (2005):
    580–615. <a href="https://doi.org/10.1137/s009753970444199x">https://doi.org/10.1137/s009753970444199x</a>.'
  ieee: A. Czumaj and C. Sohler, “Abstract Combinatorial Programs and Efficient Property
    Testers,” <i>SIAM Journal on Computing</i>, vol. 34, no. 3, pp. 580–615, 2005.
  mla: Czumaj, Artur, and Christian Sohler. “Abstract Combinatorial Programs and Efficient
    Property Testers.” <i>SIAM Journal on Computing</i>, vol. 34, no. 3, 2005, pp.
    580–615, doi:<a href="https://doi.org/10.1137/s009753970444199x">10.1137/s009753970444199x</a>.
  short: A. Czumaj, C. Sohler, SIAM Journal on Computing 34 (2005) 580–615.
date_created: 2020-09-01T11:35:41Z
date_updated: 2022-01-06T06:53:52Z
department:
- _id: '63'
doi: 10.1137/s009753970444199x
intvolume: '        34'
issue: '3'
language:
- iso: eng
page: 580-615
publication: SIAM Journal on Computing
publication_identifier:
  issn:
  - 0097-5397
  - 1095-7111
publication_status: published
status: public
title: Abstract Combinatorial Programs and Efficient Property Testers
type: journal_article
user_id: '15415'
volume: 34
year: '2005'
...