# Dense Graph Property Testing “Tradeoffs”

Suggested by | Clément Canonne |
---|---|

Source | Warwick 2018 |

In the dense graph model of property testing (where the testing algorithm is granted query access to the adjacency matrix of an unknown $n$-node graph, and the distance measure is the fraction of entries of this matrix that needs to be changed for the graph to satisfy the property), *testability* was originally defined as meaning “a number of queries depending only on the proximity parameter $\varepsilon$ (but not $n$).” Many properties, such as graph partition properties, triangle-freeness, and more generally $H$-freeness, are known to be testable with a constant number of queries in this sense. Moreover, we now have a full characterization of the graph properties that admit $O_\varepsilon(1)$-query testers [AlonFNS-09].

These kinds of testers are, however, typically obtained via regularity lemmata, such as Szemerédi's Regularity Lemma, and the “constant” query complexity if often superpolynomial in $1/\varepsilon$ (more often than not, it is even a tower of 2's of height $\operatorname{poly}(1/\varepsilon)$). This is not an oversight: triangle freeness, for instance, provably does *not* have any tester with query complexity $\operatorname{poly}(1/\varepsilon)$ [Alon-02]. See for instance Section 8.5 of Goldreich's book [Goldreich-17] for a summary of the state of the art in property testing in the dense graph model.

Nevertheless, nothing *a priori* precludes these properties from having testers with query complexity $\sqrt{n}\operatorname{poly}(1/\varepsilon)$, $\operatorname{poly}(\log n, 1/\varepsilon)$, or even $\operatorname{poly}(\log^* n, 1/\varepsilon)$. What is the best possible tradeoff between $n$ and $\varepsilon$? Note that *every* property trivially has a tester with query complexity $O(n^2)$, so the question is how far down this dependence on $n$ can be brought while keeping a reasonable dependence on $\varepsilon$.

**Concrete instance of the problem:** Is there a $\operatorname{poly}(\log n, 1/\varepsilon)$-query tester for triangle freeness in the dense graph model?