Earthmover Resilience and Testing in Ordered Structures
From MaRDI portal
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.
Recommendations
Cites work
- L_p-testing
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- Approximate testing of visual properties
- Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays
- Efficient removal lemmas for matrices
- Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
- Estimating parameters associated with monotone properties
- Estimating the distance to a hereditary graph property
- Graph limits and parameter testing
- scientific article; zbMATH DE number 3641497 (Why is no real title available?)
- scientific article; zbMATH DE number 1418269 (Why is no real title available?)
- Locally testable codes and PCPs of almost-linear length
- Lower bounds for testing forbidden induced substructures in bipartite-graph-like combinatorial objects
- Property testing and its connection to learning and approximation
- Robust Characterizations of Polynomials with Applications to Program Testing
- Sample-based high-dimensional convexity testing
- Spot-checkers
- Testability and repair of hereditary hypergraph properties
- Testing k-monotonicity
- Testing graphs for colorability properties*
- Testing of matrix-poset properties
- Testing properties of graphs and functions
- Testing versus Estimation of Graph Properties
- The earth mover's distance as a metric for image retrieval
- The power and limitations of uniform samples in testing properties of figures
- Three theorems regarding testing graph properties
- Tolerant property testing and distance approximation
- Tolerant testers of image properties
- Tolerant versus intolerant testing for Boolean properties
Cited in
(4)
This page was built for publication: Earthmover Resilience and Testing in Ordered Structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5121906)
