Testing versus estimation of graph properties, revisited
Open Access
- 26 April 2024
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 65 (3) , 460-487
Abstract
A graph on vertices is ‐far from property if one should add/delete at least edges to turn into a graph satisfying . A distance estimator for is an algorithm that given and distinguishes between the case that is ‐close to and the case that is ‐far from . If has a distance estimator whose query complexity depends only on , then 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 Fischer–Newman theorem, stating that an inverse statement also holds, that is, that every testable graph 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 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. We show that if ???? is hereditary, then one can turn a tester for ???? 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 ????, one can turn a testing algorithm for ???? 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.Keywords
All Related Versions
Funding Information
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung (200021_196965)
- European Research Council (863438)
This publication has 31 references indexed in Scilit:
- Bounds for graph regularity and removal lemmasGeometric and Functional Analysis, 2012
- Regularity Lemmas for Graphs2010
- Generalizations of the removal lemmaCombinatorica, 2009
- Szemerédi’s Lemma for the AnalystGeometric and Functional Analysis, 2007
- Estimating the distance to a monotone functionRandom Structures & Algorithms, 2007
- Tolerant property testing and distance approximationJournal of Computer and System Sciences, 2006
- Three theorems regarding testing graph propertiesRandom Structures & Algorithms, 2003
- Efficient Testing of Large GraphsCombinatorica, 2000
- Quick Approximation to Matrices and ApplicationsCombinatorica, 1999
- On graphs with small subgraphs of large chromatic numberGraphs and Combinatorics, 1985