Abstract
A graph G on n vertices is εfar from property P if one should add/delete at least ε n² edges to turn G into a graph satisfying P. A distance estimator for P is an algorithm that given G and α, ε > 0 distinguishes between the case that G is (αε)close to ? and the case that G is αfar from ?. If P has a distance estimator whose query complexity depends only on ε, then P is said to be estimable.
Every estimable property is clearly also testable, since testing corresponds to estimating with α = ε. A central result in the area of property testing is the FischerNewman theorem, stating that an inverse statement also holds, that is, that every testable property is in fact estimable. The proof of Fischer and Newmann was highly ineffective, since it incurred a towertype loss when transforming a testing algorithm for P into a distance estimator. This raised the natural problem, studied recently by FiatRon and by HoppenKohayakawaLangLefmannStagni, whether one can find a transformation with a polynomial loss. We obtain the following results.
 We show that 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.
 We show that 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 FischerNewman that incurred a towertype loss. Our main conceptual contribution in this work is that we manage to turn the approach of FischerNewman, which was inherently ineffective, into an efficient one. On the technical level, our main contribution is in establishing certain properties of FriezeKannan Weak Regular partitions that are of independent interest.
BibTeX  Entry
@InProceedings{gishboliner_et_al:LIPIcs.APPROX/RANDOM.2023.46,
author = {Gishboliner, Lior and Kushnir, Nick and Shapira, Asaf},
title = {{Testing Versus Estimation of Graph Properties, Revisited}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
pages = {46:146:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772969},
ISSN = {18688969},
year = {2023},
volume = {275},
editor = {Megow, Nicole and Smith, Adam},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18871},
URN = {urn:nbn:de:0030drops188713},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.46},
annote = {Keywords: Testing, estimation, weak regularity, randomized algorithms, graph theory, FriezeKannan Regularity}
}
Keywords: 

Testing, estimation, weak regularity, randomized algorithms, graph theory, FriezeKannan Regularity 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) 
Issue Date: 

2023 
Date of publication: 

04.09.2023 