Testing versus estimation of graph properties, revisited

Oded's comments

(As in Nr 383, I missed this work before, due to the same reasons.)

This work refers to testing graph properties in the dense graph model (aka the adjacency materix model). Hence, distances are measured a a fraction of the number of disagreements over the size of the adjacency matrix (i.e., the number of vertices squared).

I am most excited about the result stating that the complexity of distance approximation is at most doublly-exponential in the complexity of testing.

(I strongly object to the convention of calling a property testable or estimable when the relevant query complexity depends on the proximity parameter only. One should just use the latter term.)

The original abstract (slightly revised)

A distance estimator for a graph property P is an algorithm that given G and positive alpha and eps, distinguishes between the case that G is (alpha-eps)-close to P and the case that G is alphafar from P (in edit distance). We say that P is estimable if it has a distance estimator whose query complexity depends only on esp. Every estimable property is also testable, since testing corresponds to estimating with alpha=eps (equiv. alpha-eps=0). A central result in the area of [graph] property testing, the Fischer--Newman theorem, gives an inverse statement: every testable property is in fact estimable. The proof of Fischer and Newman was highly ineffective, since it incurred a tower-type loss when transforming a testing algorithm for P into a distance estimator. This raised the natural problem, studied recently by Fiat--Ron and by Hoppen--Kohayakawa--Lang--Lefmann--Stagni, whether one can find a transformation with a polynomial loss. We obtain the following results.

1. If P is hereditary, then one can turn a tester for P into a distance estimator with an exponential loss. This is an exponential improvement over the result of Hoppen et. al., who obtained a transformation with a double exponential loss.
2. For every P, one can turn a testing algorithm for P into a distance estimator with a double exponential loss. This improves over the transformation of Fischer--Newman that incurred a tower-type loss. Our main conceptual contribution in this work is that we manage to turn the approach of Fischer--Newman, which was inherently ineffective, into an efficient one. On the technical level, our main contribution is in establishing certain properties of Frieze--Kannan Weak Regular partitions that are of independent interest.

See arXiv 2305.05487