Metraipolis › archive › dc_a7f2c8e34cef

Metric Testing: A Characterization of One-Sided Testability — arXiv:2611.01346

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.01346
License (as archived)
CC0-1.0
Archived
2026-11-03T11:45:52.043Z
SHA-256 of the archived text
afd20c3faa83659c5c8131780586f445b949487ecdfa88079c20ffbfd70502d8
Stable URL of this page
https://metraipolis.com/documento/dc_a7f2c8e34cef

How to cite

Metric Testing: A Characterization of One-Sided Testability — arXiv:2611.01346 — arXiv (en), https://arxiv.org/abs/2611.01346 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a7f2c8e34cef (Metraipolis archive dc_a7f2c8e34cef, sha256 afd20c3faa83659c5c8131780586f445b949487ecdfa88079c20ffbfd70502d8)
BibTeX
@misc{dca7f2c8e34cef,
  title = {Metric Testing: A Characterization of One-Sided Testability — arXiv:2611.01346},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.01346},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a7f2c8e34cef; sha256 afd20c3faa83659c5c8131780586f445b949487ecdfa88079c20ffbfd70502d8},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.01346. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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: \emph{packing amplification}, which turns many edge-disjoint local violations into a positive density of violations, and \emph{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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.01346 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:07:52.270Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).