License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2018.18
URN: urn:nbn:de:0030-drops-88718
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8871/
Ben-Eliezer, Omri ;
Fischer, Eldar
Earthmover Resilience and Testing in Ordered Structures
Abstract
One of the main challenges in property testing is to characterize those properties that are testable with a constant number of queries. For unordered structures such as graphs and hypergraphs this task has been mostly settled. However, for ordered structures such as strings, images, and ordered graphs, the characterization problem seems very difficult in general.
In this paper, we identify a wide class of properties of ordered structures - the earthmover resilient (ER) properties - and show that the "good behavior" of such properties allows us to obtain general testability results that are similar to (and more general than) those of unordered graphs. A property P is ER if, roughly speaking, slight changes in the order of the elements in an object satisfying P cannot make this object far from P. The class of ER properties includes, e.g., all unordered graph properties, many natural visual properties of images, such as convexity, and all hereditary properties of ordered graphs and images.
A special case of our results implies, building on a recent result of Alon and the authors, that the distance of a given image or ordered graph from any hereditary property can be estimated (with good probability) up to a constant additive error, using a constant number of queries.
BibTeX - Entry
@InProceedings{beneliezer_et_al:LIPIcs:2018:8871,
author = {Omri Ben-Eliezer and Eldar Fischer},
title = {{Earthmover Resilience and Testing in Ordered Structures}},
booktitle = {33rd Computational Complexity Conference (CCC 2018)},
pages = {18:1--18:35},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-069-9},
ISSN = {1868-8969},
year = {2018},
volume = {102},
editor = {Rocco A. Servedio},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8871},
URN = {urn:nbn:de:0030-drops-88718},
doi = {10.4230/LIPIcs.CCC.2018.18},
annote = {Keywords: characterizations of testability, distance estimation, earthmover resilient, ordered structures, property testing}
}
|
Keywords: |
|
characterizations of testability, distance estimation, earthmover resilient, ordered structures, property testing |
|
Collection: |
|
33rd Computational Complexity Conference (CCC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.06.2018 |
