Metric Testing: A Characterization of One-Sided Testability
cs.DM, cs.DS
Submitted: 2026-10-31
Updated: 2026-10-31
License: http://creativecommons.org/licenses/by/4.0/
The gist: We give a unified framework for one-sided testability (constant-query testing) of metric families.
Abstract
We give a unified framework for one-sided testability (constant-query testing) of metric families. For a broad class of families defined by fixed local predicates, we prove that testability is equivalent to two structural properties: packing amplification, which turns many edge-disjoint local violations into a positive density of violations, and completion stability, which allows locally consistent partial matrices with few missing entries to be cheaply completed. This characterization yields a common proof strategy and simpler proofs of classical testability results for ultrametrics, tree pseudometrics, Euclidean pseudometrics in fixed dimension, and several others. Our framework also gives new quantitative bounds for metric testing: a nonadaptive one-sided upper bound for matrices with entries in the bounded range [1,C], and two-sided nonadaptive and adaptive lower bounds for general metrics.
Sources
- Testing hereditary properties of ordered graphs and matrices
- Nearly Tight Bounds on Testing of Metric Properties
- Generalized Metric Repair on Graphs
- Metric embedding with outliers
Related papers
- Low-Temperature Sampling via Equilibrium Disagreements
- An Improved Bound for Testing k-Colorability
- Temporal Cliques Admit Linear Spanners
- Multiway Partition is FPT for Connectivity Functions
- Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
- Constrained intersection representations and forbidden patterns