Abstract Combinatorial Programs and Efficient Property Testers

A. Czumaj, C. Sohler, SIAM Journal on Computing 34 (2005) 580–615.

Download
No fulltext has been uploaded.
Journal Article | Published | English
Author
;
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. We 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. Our 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.
Publishing Year
Journal Title
SIAM Journal on Computing
Volume
34
Issue
3
Page
580-615
LibreCat-ID

Cite this

Czumaj A, Sohler C. Abstract Combinatorial Programs and Efficient Property Testers. SIAM Journal on Computing. 2005;34(3):580-615. doi:10.1137/s009753970444199x
Czumaj, A., & Sohler, C. (2005). Abstract Combinatorial Programs and Efficient Property Testers. SIAM Journal on Computing, 34(3), 580–615. https://doi.org/10.1137/s009753970444199x
@article{Czumaj_Sohler_2005, title={Abstract Combinatorial Programs and Efficient Property Testers}, volume={34}, DOI={10.1137/s009753970444199x}, number={3}, journal={SIAM Journal on Computing}, author={Czumaj, Artur and Sohler, Christian}, year={2005}, pages={580–615} }
Czumaj, Artur, and Christian Sohler. “Abstract Combinatorial Programs and Efficient Property Testers.” SIAM Journal on Computing 34, no. 3 (2005): 580–615. https://doi.org/10.1137/s009753970444199x.
A. Czumaj and C. Sohler, “Abstract Combinatorial Programs and Efficient Property Testers,” SIAM Journal on Computing, vol. 34, no. 3, pp. 580–615, 2005.
Czumaj, Artur, and Christian Sohler. “Abstract Combinatorial Programs and Efficient Property Testers.” SIAM Journal on Computing, vol. 34, no. 3, 2005, pp. 580–615, doi:10.1137/s009753970444199x.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar