Triangle-Freeness: Estimation Is as Easy as TestingResearch Paper
An algorithm examining a large graph may have time to inspect only a small part of its adjacency matrix. Property testing asks whether the graph has a specified property or requires a substantial number of edge changes to acquire it. Distance estimation asks how many changes are needed, to a prescribed additive accuracy. For triangle-freeness, a tester can…