{"id":"arxiv/2611.04276","url":"https://arxiv.org/abs/2611.04276","tags":["cs.DS","math.CO"],"score":0,"title":"Testing Implies Distance Estimation with Polynomial Loss","domain":"cs.DS","source":"arxiv","authors":["Gaia Carenini","Cameron Seth"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-03","reactions":{}}