Earthmover Resilience and Testing in Ordered Structures

DOI10.4230/LIPIcs.CCC.2018.18zbMath1441.68152arXiv1801.09798MaRDI QIDQ5121906

Omri Ben-Eliezer, Eldar Fischer

Publication date: 22 September 2020

Full work available at URL: https://arxiv.org/abs/1801.09798

zbMATH Keywords

property testingordered structuresdistance estimationcharacterizations of testabilityearthmover resilience

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Ordered sets (06A99) Randomized algorithms (68W20)

Related Items (2)

Efficient removal lemmas for matrices ⋮ Unnamed Item

Uses Software

• EMD

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing properties of graphs and functions
• Spot-checkers
• Estimating the distance to a hereditary graph property
• The earth mover's distance as a metric for image retrieval
• Testing of matrix-poset properties
• Tolerant property testing and distance approximation
• Graph limits and parameter testing
• Testability and repair of hereditary hypergraph properties
• Property testing and its connection to learning and approximation
• Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
• Locally testable codes and PCPs of almost-linear length
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Lower bounds for testing forbidden induced substructures in bipartite-graph-like combinatorial objects
• Three theorems regarding testing graph properties
• Tolerant testers of image properties
• Estimating parameters associated with monotone properties
• The Power and Limitations of Uniform Samples in Testing Properties of Figures
• Testing graphs for colorability properties*
• Robust Characterizations of Polynomials with Applications to Program Testing
• Efficient Removal Lemmas for Matrices
• Sample-Based High-Dimensional Convexity Testing.
• Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• L _p -testing
• Testing versus Estimation of Graph Properties
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: Earthmover Resilience and Testing in Ordered Structures