Testing Implies Distance Estimation with Polynomial Loss
Source: arxiv.org/abs/2611.04276
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.04276
curl -X POST /api/v1/records/arxiv/2611.04276/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.04276/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'