Testing Implies Distance Estimation with Polynomial Loss

Abstract

A tester decides whether a graph has a property or is far from having it. A distance estimator asks for more: it must approximately determine how many edges need to be changed. A property is said to be testable if there is a tester with a number of queries bounded independently of the graph's order for each conceivable distance. Similarly, if a property admits an estimator with a number of queries bounded independently of the graph's order, it is said to be estimable. Fischer and Newman proved that, in the dense graph model, every testable property is also estimable. We show that the passage from testing to estimation requires only a polynomial increase in query complexity. This resolves a long-standing open problem in property testing, previously tackled by Fiat and Ron, by Hoppen, Kohayakawa, Lang, Lefmann, and Stagni, and by Gishboliner, Kushnir, and Shapira.

Geometric parameter sequences for Q-polynomial distance-regular graphs
Jae-Ho Lee, Jongyook Park, Ian Seong
arXiv19 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
On the Peak Estimation of Scalar Polynomial Systems via Integrability
Karolína Sehnalová
arXiv19 Oct 2026PreprintCC BY 4.0Full textDynamical systems Optimisation & controlarXiv
Total Variation Distance Estimation through Domain Reduction
Arnab Bhattacharyya, Graham Cormode, Yucheng Fu +1
arXiv1 Oct 2026PreprintCC BY 4.0Full textProbabilityarXiv
On the estimation of the Gromov-Hausdorff distance
Emin Abdullaev
arXiv29 Oct 2026PreprintarXiv licenceFull textGeometry & topologyarXiv
Polynomial-time classical simulation of boson and fermion sampling under thermal loss
Armando Angrisani, Hela Mhiri
arXiv5 Nov 2026PreprintarXiv licenceFull textMathematical physics Optics & photonicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{carenini2026testing,
  title = {{Testing Implies Distance Estimation with Polynomial Loss}},
  author = {Gaia Carenini and Cameron Seth},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.04276},
  eprint = {2611.04276},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.04276},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Testing Implies Distance Estimation with Polynomial Loss
AU  - Gaia Carenini
AU  - Cameron Seth
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.04276
UR  - https://arxiv.org/abs/2611.04276
AB  - A tester decides whether a graph has a property or is far from having it. A distance estimator asks for more: it must approximately determine how many edges need to be changed. A property is said to be testable if there is a tester with a number of queries bounded independently of the graph's order for each conceivable distance. Similarly, if a property admits an estimator with a number of queries bounded independently of the graph's order, it is said to be estimable. Fischer and Newman proved that, in the dense graph model, every testable property is also estimable. We show that the passage from testing to estimation requires only a polynomial increase in query complexity. This resolves a long-standing open problem in property testing, previously tackled by Fiat and Ron, by Hoppen, Kohayakawa, Lang, Lefmann, and Stagni, and by Gishboliner, Kushnir, and Shapira.
ER  -

Abstract

Related

Cite